Representing a natural number in the form of $\sum_{i=0}^{p}b_i2^i$

Question

for every number n $\in N^+ $, there is a unique representation of n in the form $\sum_{i=0}^{p}b_i2^i$ where p is the smallest integer sunch that $2^{p+1}>n$, p is non-negative, and $b_p,b_{p-1}....b_0 \in$ {0,1}

I used induction on this using the fact that if this is true for some m then it is is true for some (m+1)/2 and so it is true for (m+1)

But i don't get how i would use the fact $2^{p+1}>n$

Answer 1

Lemma 1: There exist one and only one way to express the integer $n \ge 1$ in the form

$\tag 1 n = m + 2^k \text{ where } \, 0 \le m \lt 2^k$
Proof
Existence:
There exists a smallest integer $k \ge 0$ such that $n \lt 2^{k+1}$ and so then $n \ge 2^{k}$. So we can set $m$ to the non-negative number $n - 2^{k}$. To conclude we need to show that $m \lt 2^k$, or
$\quad n - 2^{k} \lt 2^{k}$, or
$\quad n \lt 2^{k}+2^{k}$, or
$\quad n \lt 2^k (1+1)$, or
$\quad n \lt 2^{k+1}$, so we get the existence for a (1) representation.
Uniqueness:
Suppose now that $n$ has a (1) representation. If we can show that $n \lt 2^{k+1}$, then one can easily conclude the uniqueness. But,

$\quad n = m + 2^k \lt 2^k + 2^k = 2 \times 2^k = 2^{k+1} \qquad \blacksquare$

Observe that we do not have to rely on reductio ad absurdum in this proof.

Proposition 2: Binary representations exist and are unique.
Proof
Just keep applying (1), peeling off unique descending $k^{'}\text{s}$. The corresponding $m^{'}\text{s}$ eventually hit $0$, and then the algorithm is complete. $\qquad \blacksquare$

Example: Calculate the binary expansion of $42_\text{ Base 10}\,$:

$42 = 10 + 2^5$
$10 = 2 + 2^3$
$2 = 0 + 2^1$

Answer: 101010

This is a 'top down' method, differing from the usual 'bottoms up' Euclidean algorithm deployment.

Answer 2

If it is true for $m\leq n$, $n=\sum a_i2^i$, $n+1=\sum a_i2^i+1$, if $a_0=0$ done, if not $n+1$ is even and $(n+1)/2=\sum b_j2^j$, you have $n+1=\sum b_j2^{j+1}$.