Convert Decimal to Binary - Induction

Question

I read the page 2 of Mathematical Induction, I have difficulty of understanding of

The Induction Hypothesis is “If m is the integer represented by the binary array b[1,2 . . . k], then n = 2 ^ k * t + m”

1) What is m?

2) And for t is even the m is unchangeable while for t is odd the m=m+2^k, how?

Please explain above points. Thanks

Answer 1

The author of those notes unfortunately neglects to mention how he intends a binary array to represent an integer. In fact it is the reverse of the usual representation: the array $[1101]$, for instance, represents the binary number $1011=2^3+2^1+2^0=11$. More generally, the array $[b_1\ldots b_k]$ represents the integer

$$b_1\cdot2^0+b_2\cdot 2^1+b_3\cdot 2^2+\ldots+b_k\cdot 2^{k-1}=\sum_{i=1}^k2^{i-1}b_i\;.$$

Now let’s look at how the algorithm works when $n=11$. The first line of the following table shows the values of $t$ and $k$ after they have been initialized but before the while loop has been entered. Each of the next four lines shows the values of $t,k,b[k]$, and $b[1\ldots k]$ at the end of one pass through the while loop. The output is $b[1234]=[1101]$, representing

$$1\cdot 2^0+1\cdot 2^1+0\cdot 2^2+1\cdot 2^3=1+2+8=11\;,$$

as it should.

$$\begin{array}{c|c|c|l} t&k&b[k]&b[1\ldots k]\\ \hline 11&0&-&-\\ 5&1&1&1\\ 2&2&1&11\\ 1&3&0&110\\ 0&4&1&1101 \end{array}$$

The induction is on $k$, the variable that counts passes through the while loop. The induction hypothesis $P(k)$ will be some statement about $k$, and the induction step will be to show that if $P(k)$ is true, so is $P(k+1)$. The statement $P(k)$ is:

If $m$ is the integer represented by the binary array $b[12\ldots k]$, then $n=2^kt+m$.

Let’s check that statement for each line of the table.

• Line $k=0$: The binary array in the fourth column is empty, so it represents the integer $m=0$; $k=0$, $t=n=11$, and it’s true that $11=2^0\cdot11+0$.

• Line $k=1$: The binary array in the fourth column is just $[1]$, representing $m=1$, and it’s true that $11=2^1\cdot 5+1$.

• Line $k=2$: The binary array in the fourth column is $[11]$, representing $m=3$, and it’s true that $11=2^2\cdot 2+3$.

• Line $k=3$: The binary array in the fourth column is $[110]$, also representing $m=3$, and it’s true that $11=2^3\cdot 1+3$.

• Line $k=4$: The binary array in the fourth column is $[1101]$, representing $m=11$, and it’s true that $11=2^5\cdot 0+11$.