Proof of Russian Peasant Multiplication

Write $m$ in binary. The lines where the number is odd corresponds to the bits that are $1$ in the binary expansion. In your example of $18 \times 37$ we have $18=10010_2=2^1+2^4,$ so $18 \times 37=(2+16) \times 37$, which are exactly the terms you added.

After reading Ross Millikan's reply I decided to write a complete proof. This is my attempt:

A binary number is a way of expressing a number in powers of two, taking the form:

$$m = d_n2^{n-1}+d_{n-1}2^{n-2}+d_{n-2}2^{n-3}+...+d_{1}2^{0}$$

Where $n$ is the number of digits in the binary number. Therefore:

$$m\times n = \left[d_n2^{n-1}+d_{n-1}2^{n-2}+d_{n-2}2^{n-3}+...+d_{1}2^{0}\right]\times n$$

For example:

$$=18\times 37$$ $$\quad\;\;\;\;= \left[2^4+2\right]\times 37$$ $$\quad\;\;\;= \left[16+2\right]\times 37$$ $$\;= 592+74$$ $$666$$

The below table is a way of using this identity to multiply two numbers $m$ and $n$:

$$\begin{array}{c} \text{Index}&&m&&\text{If col. 1 is odd, }n\times 2^{Index}&\\ \hline 0 && m\\ 1 && \bigl\lfloor \frac{m}{2} \bigr\rfloor\\ 2 && \bigl\lfloor \frac{m}{4} \bigr\rfloor\\ 3 && \bigl\lfloor \frac{m}{8} \bigr\rfloor\\ 4 && \bigl\lfloor \frac{m}{16} \bigr\rfloor\\ 5 && \bigl\lfloor \frac{m}{32} \bigr\rfloor\\ \end{array}$$

Where the first column is the sequence of integers, the denominator in the second column is the sequence $a_n = 2a_{n-1}\text{ where }a_1=2$. The summation of the third column is the product $m\times n$.

Which is equivalent to these steps: repeat the below steps until the left column == 1:

• Halve the last number in the first column
• Write the result below (discard the remainder)
• Double the last number in the first column.
• Write the result below.

Now, for every even number in the first column, delete the adjacent number in the second column. Add the remaining numbers in the second column.