I just want to prove we can represent all natural numbers with binary representation. So I had constructed following claim:
Claim: with $k$-length of binary representation, we can represent $2^{k}-1$ different numbers which is less than or equal to $2^{k}$
Proof
When $k = 0$, we can represent only $1$ natural number so its true.
then Assume the claim holds in case of $k = n$
then for the case of $k = n+1$, from the above assumption, $2^n-1$ different has already been represented, will add $2^n$ to each number by assigning 1 to n+1th loci of binary representation. Then we can make $2^{n+1}-2$ with this method, and one more the number $2^{n}$ should be added. So we can construct $2^{n+1}-1$ in case of $k = n+1$ also.
By mathematical induction, this will eventually go on, thus the claim holds for every natural number of $k$
1) Is the claim enough to prove that "we can represent all natural numbers with binary representation?
2) Any insufficiency or incorrect reasoning in this proof?
I need your verification.
Best Answer
This is a good start, but if I understand your method correctly, it does not quite work. It proves that you can represent infinitely many numbers— but it does not clearly show that you can represent all numbers.
For contrast, consider a similar claim:
This claim is false because if the unit bit is 0, you can only represent even numbers. However, according to your proposed proof strategy, you might argue: (a) in the base case, you have one bit and can represent one number. (b) if you have $(k+1)$ bits, you can simply add $2^k$ to each of the numbers you have represented so far to get twice as many new numbers. This is true, but it only implies that you can represent infinitely many numbers in this scheme— in fact, you can represent all the even numbers. It does not imply that you can represent all integers, however. And indeed you can't represent odd numbers this way.
If you like, you could treat your goal formally as establishing a bijection between the natural numbers $\mathbb{N}$ and binary strings $\mathbb{B}$.
Thus, you would need to show that every integer has a bitstring representation, and that bitstring representations are unique— two different bitstrings must correspond to different numbers. (I'm assuming that leading zeroes are forbidden.)
But perhaps you only want to prove that every integer has a corresponding bitstring representation, and you don't care about uniqueness.
This is easy enough to show— we just convert each number to binary! Let $n$ be a non-negative integer.
Put $n_0 = n$ and $b_0 = n\pmod{2}$. Until $n_k$ is zero, define $n_{k+1} = (n_k - b_k)/2$ and define $b_{k+1} = n_{k+1}\pmod{2}$.
Because the $n_k$ form a decreasing sequence of non-negative numbers, this process must eventually end. When it does, declare the bitstring of $n$ to be $b_k\ldots b_0$. This is the binary representation of $n$. Because you can apply this procedure to any number $n$, it proves that every number has a binary representation.
This proof does not show a few other things, namely that bitstrings are unique (each number has at most one representation), or that every bitstring corresponds to a valid number.