Can someone help me with a well explained inductive proof of this? I have read many different ones but they don't really make sense to me and I need to know how to do this for my final.
Prove the following by induction: Existence of the Binary Number System, i.e.
Every Natural Number, $n$, can be expressed as the sum of distinct powers of 2.
For example: $21=1\cdot2^4+0\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0$, or simply: $21=2^4+2^2+2^0$You will need to use a fact that we proved in class the 1st day induction was presented, i.e. $$\sum_{k=1}^n2^{k-1}=2^0+2^1+2^2+\cdots+2^{n-1}=2^n-1$$ (possibly more than once)
When you're trying to prove it for $n+1$ you will need to consider 2 or 3 separate cases about $n+1$, depending on your specific approach (there are some options).
First we check that $1$ is a sum of powers of $2$. We write $1=2^0$, which checks it.
Then we assume that all numbers smaller than $n$ are sums of different powers of $2$. Under this assumption we must show that $n$ itself is a sum of different powers of $2$.
If $n$ is even then $n/2$ is natural and $<n$. Therefore $n/2$ is a sum of different powers of $2$. Multiplying by $2$ that sum we get a new sum of different powers of $2$ that adds up to $n$.
If $n=2k+1$ is odd. Then $k<n$ is a sum of different powers of $2$. Multiplying this sum by $2$ as before we get that $2k$ is a sum of different powers of $2$.
Now we add $1$ to this sum that gives $2k$. Notice that it is not possible that the sum that gives $2k$ as sum of powers of $2$ had a $1$ among its summands. Therefore by adding $1$ we are not introducing any repetitions in the summands. Done!
Notice that we didn't used the hint. This is because we used the seemingly stronger inductive scheme of assuming that the statement was true for all numbers smaller than $n$ instead of only assuming it is true for $n-1$. This form of induction is more convenient for this problem (and many others).