I'm studying a combinatorics text (Cameron) in preparation for taking discrete math this upcoming semester. I've taken a fair amount of math in college, through Calculus II, but this is my first 500+ level math course.
In chapter 2 of the Cameron book, the author introduces an algorithm for multiplication called Russian Peasant Multiplication. I want to prove that this algorithm will always result in the product of two numbers.
I've been chewing on the proof for a while now, and just can't seem to get any traction. Thanks in advance for any help.
Description of Algorithm
I'll try to explain the algorithm clearly. The goal of the algorithm is to find the product of two numbers $m$ and $n$. The below table is filled out for $m$ and $n$:
$$\begin{array}{c}
m&&n&\\ \hline
\bigl\lfloor \frac{m}{2} \bigr\rfloor&& 2n \\
\bigl\lfloor \frac{m}{4} \bigr\rfloor&& 4n \\
\bigl\lfloor \frac{m}{8} \bigr\rfloor&& 8n \\
\bigl\lfloor \frac{m}{16} \bigr\rfloor&& 16n \\
\bigl\lfloor \frac{m}{32} \bigr\rfloor&& 32n \\
\end{array}$$
The sequence of numbers in both columns is the sequence $a_n = 2a_{n-1}\text{ where }a_1=2$. The columns are extended down until the value in the left column is equal to the number one. After filling out the table, the product is found by adding the values of the right column where the left column is an odd number.
For example, to multiply 18 and 37 with the algorithm:
$$\begin{array}{c}
m&&n&\\ \hline
18 && 37 \\
9 && 74 \\
4 && 148 \\
2 && 296 \\
1 && 592 \\
\end{array}$$
To find the product, cross out values of the left column where the value of the right column is even:
$$\begin{array}{c}
m&&n&\\ \hline
\require{enclose}
\enclose{horizontalstrike}{18} && \enclose{horizontalstrike}{37} \\
9 && 74 \\
\enclose{horizontalstrike}{4} && \enclose{horizontalstrike}{148} \\
\enclose{horizontalstrike}{2} && \enclose{horizontalstrike}{296} \\
1 && 592 \\
\end{array}$$
And add the remaining numbers in the right column to get the result: $18\times37=74+592=666$
Alternate Description of Algorithm
As an aside, here is a shorter way to describe the algorithm, 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.
What I've done so Far
I haven't been able to get much of anywhere on the proof. One thing I did was create a bit of a different way of arriving at the same outcome:
$$\begin{array}{c}
m&&n&&\text{index}&&\text{remainder}&&\text{if remainder == 1, }n\times2^{Index}&\\ \hline
18 && 37 && 0 && 0 \\
9 && 74 && 1 && 1 && 74\\
4 && 148 && 2 && 0 \\
2 && 296 && 3 && 0 \\
1 && 592 && 4 && 1 && 592\\
\end{array}$$
Which brings to light the relationship between this algorithm and binary numbers (the fourth column in the above table is the product in binary, read bottom to top).
I also wrote some Python functions to help me explore the problem, Github repo.
Best Answer
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.