Problem about number representations To multiply two numbers, such as 37 and 22, set up a table according to the following pattern.  
\begin{array}{|c|c|}
\hline
37&22 \\ \hline
 18&44  \\ \hline
 9&88   \\ \hline
 4&176  \\ \hline  
 2&352  \\ \hline
 1&704  \\ \hline
\end{array}
The first column is formed by successive halvings (fractional remainders are discarded whenever they occur) and the second by successive doublings. If the elements of the second column standing opposite odd numbers in the first are added together, the result is 22+88+704=814= 22*37. Use the binary represenation to show that this rule is general.
So do I have to draw the same table and use the same pattern but with binary numbers?
 A: Yes.   That is what you have to do.   Then think about why it is true.   Here, to get you started:
$$\begin{array}{|r:r|}
\hline
{10\,0101}&{1\,0110} & \star \\ \hdashline
 \\ \hdashline
&& \star   \\ \hdashline
 \\ \hdashline  
\\ \hdashline
1 & 10\,1100\,0000 & \star\\ \hdashline
\end{array}$$
Fill in the rest then think about it.   What is happening here?
A: Hint $\ $ The algorithm amounts to computing integer products $\,n\times b\,$ by iteratively applying the following rewrite rules to reduce $\,n\,$ down to the trivial (base) case $\,n=1$.
$$\begin{eqnarray} (2a+\!1)\times b \,&=&\, a\times 2b\, \color{#c00}{+\, b}\ \ && \rm{i.e. when}\,\  2a\!+\!1\,\ is\ \ \color{#c00}{odd}\\
(2a+\!0)\times b \,&=&\, a\times 2b\ \ && \rm{i.e. when}\,\  2a\!+\!0\,\ is\ \ {even}\\
\end{eqnarray}$$
Remark $\ $ Such multiplication by repeated doubling is just the multiplicative analog of exponentiation by repeated squaring, i.e. 
$$\qquad\begin{eqnarray} b^{2a+1} \,&=&\, (b^2)^a \color{#c00}{\times\, b}\ \ && \rm{i.e. when}\,\  2a\!+\!1\,\ is\ \ \color{#c00}{odd}\\
b^{2a+0} \,&=&\, (b^2)^a \ && \rm{i.e. when}\,\  2a\!+\!0\,\ is\ \ {even}\\
\end{eqnarray}$$
This may be clearer if you view the radix representation in nested Horner form (as arises when it is computed by repeatedly dividing by $2$ with remainder), i.e.
$$ n\, =\, d_0 + 2 (d_1 + 2( d_2 + \cdots + d_n)) $$
