×

# 2's Problem

Please help me to prove that "Every natural number can be uniquely represented in sum of power's of 2". Example 5=2^2 + 2^0.

Note by X Zero
3 years, 8 months ago

Sort by:

It follows from that for any
$n$ we can find $k$ such that $2^k\le n<2^{k+1}$.We will proceed with induction.For $n=1$ we see $1=2^0$.This is the only way to express it.Suppose it is true for all $i< n$.We show for $n$.We show for $n$.Now as before we can find $k$ as per the equation $2^k\le n<2^{k+1}$.So we see this $k$ is unique.Now consider $n-2^k$ and since this is $<n$ it has a unique representation.So every positive integer has one such representation.btw this is actually proving that each number in decimal system has a unique representation in the binary system. · 3 years, 8 months ago

Also, since $$n - 2^k < 2^{k+1} - 2^k = 2^k,$$ the representation of $$n - 2^k$$ doesn't contain $$2^k.$$ Then it follows that each number can be represented as a sum of unique powers of $$2.$$ · 3 years, 8 months ago

I almost wanted to claim that the statement is wrong as it's currently worded (since $$5 = 2^0 + 2^0 + 2^0 + 2^0 + 2^0$$ too), but you already put it here. :) · 3 years, 8 months ago