Converting decimal(base 10) numbers to binary by repeatedly dividing by 2

A friend of mine had a homework assignment where he needed to convert decimal(base 10) numbers to binary. I helped him out and explained one of the ways I was taught to do this.

The way I showed him was to repeatedly divide the number by 2 and then take the remainder, the binary number will be the remainders read from bottom to top.

ex:  Convert 22 to a binary representation

22 / 2 = 11 R 0
11 / 2 = 5  R 1 
5  / 2 = 2  R 1
2  / 2 = 1  R 0
1  / 2 = 0  R 1

answer = 10110

After I showed him the algorithm and an example, he set off to do the rest of his problems. Today he sent me an email and asked me why this method works. I was sort of shocked by that question, I have never given a second thought to why this works, I only did as I was told knowing that if I performed this algorithm I would always get the right answer in binary.

I thought about it for awhile and still can't seem to figure out WHY this method works, any help would be appreciated. This isn't for an assignment, merely my curiosity and frustration at not asking this question before.

Thanks

Edit

Do you mind explaining how you went from:

$$n=e_0\times 2^0 + e_1\times 2^1 + \cdots + e^k\times 2^k$$

to

$$n=e_0 + 2\Bigl(e_1 + e_2\times 2 + \cdots + e_k\times 2^{k-1}\Bigr),$$

I am not following the transition to the closed form.

Solution 1:

Remember the meaning of base 10 notation; when you write a number as $$d_nd_{n-1}\cdots d_2d_1d_0$$ where $d_i$ is the $i$th digit (from right to left), what you are saying is that the number is equal to: $$ d_0\times 10^0 + d_1\times 10^1 + d_2\times 10^2 + \cdots + d_n\times 10^n.$$ So, for example, $5381$ represents the number $$1\times 10^0 + 8\times 10^1 + 3\times 10^2 + 5\times 10^3 = 1 + 80 + 300 + 5000.$$

Writing a number in binary (base 2) is meant to represent the number in exactly the same way, but with powers of $2$ in stead of powers of 10: the expression $$e_k\cdots e_3e_2e_1e_0{}_{[2]}$$ represents the number $$n=e_0\times 2^0 + e_1\times 2^1 + e_2\times 2^2 + e_3\times 2^3 + \cdots + e_k\times 2^k.$$

Since every summand except the first one is a multiple of $2$, we can write: $$\begin{align*} n&=e_0\times 2^0 + e_1\times 2^1 + \cdots + e_k\times 2^k\\ &=e_0 + \left(e_1\times 2\right) + \left(e_2\times 4\right) + \cdots \left(e_k\times 2^{k}\right)\\ &= e_0 + \left( 2 \times e_1\right) + \left( 2\times (e_2\times 2)\right) + \cdots + \left(2\times(e_k\times 2^{k-1})\right)\\ &= e_0 + 2\Bigl(e_1 + (e_2\times 2) + \cdots + (e_k\times 2^{k-1})\Bigr). \end{align*}$$ That means that when you divide $n$ by $2$ you get a remainder of $e_0$ (the right-most digit of the base 2 expression of $n$), and a quotient of $$q_1=e_1\times 2^0 + e_2\times 2^1 + \cdots + e_k\times 2^{k-1}.$$ Now you can determine the next binary digit of $n$ by repeating the process with $q_1$: we write $$q_1 = e_1 + 2\Bigl(e_2 + e_3\times 2 + \cdots + e_k\times 2^{k-2}\Bigr),$$ so the remainder of dividing $q_1$ by $2$ is the penultimate digit of the binary expression of $n$, and the quotient is $q_3$, with $$q_3 = e_2 + e_3\times 2 + \cdots + e_k\times 2^{k-2}.$$

Lather, rinse, and repeat until the remainder quotient is $0$.

Solution 2:

It becomes crystal clear if you rewrite it as follows

$\rm\qquad\qquad 22\ =\ {\color{red} 0}\ +\ 2\ (11)$

$\rm\qquad\qquad\quad\ \ = \ {\color{red} 0}\ +\ 2\ ({\color{green} 1}\ +\ 2\ (5))$

$\rm\qquad\qquad\quad\ \ = \ {\color{red} 0}\ +\ 2\ ({\color{green} 1}\ +\ 2\ ({\color{magenta} 1}\ +\ 2\ (2)))$

$\rm\qquad\qquad\quad\ \ = \ {\color{red} 0}\ +\ 2\ ({\color{green} 1}\ +\ 2\ ({\color{magenta} 1}\ +\ 2\ ({\color{brown} 0}\ +\ 2\ (1))))$

$\rm\qquad\qquad\quad\ \ = \ {\color{red} 0}\cdot 2^0 + {\color{green} 1}\cdot 2^1 + {\color{magenta} 1}\cdot 2^2 + {\color{brown} 0}\cdot 2^3 + 1\cdot 2^4\ $ expanded to normal form: polynomial in $2$

$\rm\qquad\qquad\quad\ \ = \ 1{\color{brown} 0}{\color{magenta} 1}{\color{green} 1}{\color{red} 0}\ $ in binary notation (reverse the above color-codified binary digits)

Therefore the binary digits arise simply by iterating the process of division by 2, with remainder. See also my posts on Horner's method.