Concrete Mathematics: how to prove 1.14 using induction In chapter 1, (1.14), the authors uses induction to prove $A(n) = 2^m$ where
$$
\begin{eqnarray}
A(1) & = & 1 \\
A(2n) & = & 2A(n), \text{for } n \ge 1 \\
A(2n + 1) & = & 2A(n), \text{for } n \ge 1 \\
\end{eqnarray}$$
As usual, $n = 2^m + 1$ and $0 \le l \lt 2^m$, for $n \ge 1$.
Can somebody show me the exact steps how to use induction to prove $A(2^m+l)=2^m$?
Thank you.
 A: The base case is $n=1$, $m=l=0$, where indeed $A(1)=1=2^0$.
The induction step goes like this (note that $m\ge1$ for $n>1$):
Assume $n>1$ and the claim holds for all natural numbers  $<n$. 


*

*If $l$ is even, say $l=2k$, then $0\le k<2^{m-1}$ and $$A(n)=A(2^m+l)=A(2^m+2k)=A(2\cdot (2^{m-1}+k))=2A(2^{m-1}+k)=2\cdot 2^{m-1}=2^m$$

*If $l$ is odd, say $l=2k+1$, then $0\le k<2^{m-1}$ and $$A(n)=A(2^m+l)=A(2\cdot (2^{m-1}+k)+1)=2A(2^{m-1}+k)=2\cdot 2^{m-1}=2^m$$
Hence at any rate $A(n)=2^m$.
A: The key thing to note is that the induction is not on $n \mapsto n+1$ but on the class of numbers of $n: 2^{m-1}\le N < 2^{m}$ and on $m-1 \mapsto m$.
So if we assume that for $2^{m-1} \le n < 2^{m}$ that $A(n) = 2^{m-1}$.  Then we are asked to prove for $2^{m}\le n < 2^{m+1}$ that $A(n) = 2^{m}$.
In other words we aren't doing induction on $n$; we are doing it on $m-1$.
And the trick is that if $2^{m} \le n = 2^m + l < 2^{m+1}$ then $l < 2^m$ and either $l = 2k$ or $l = 2k+1$ for some $k < 2^{m-1}$.  
So $A(n) = \begin{cases}A(2^m + 2k)&\text{if l is even}\\A(2^m + 2k + 1)&\text{if l is odd}\end{cases}$
$ = 2A(2^{m-1} + k)$.  
And we are assuming, in our induction step on $m-1$, that if  $2^{m-1} \le n'= 2^{m-1} + k < 2^{m}$ then we have $A(n') = 2^{m-1}$.
.... So $A(n)=A(2^m +\begin{cases}2k\\2k+1\end{cases})=2A(2^{m-1} + k) = 2*2^{m-1} = 2^{m}$. 
For a more formal and complete answer, see Hagen van Eitzen's excellent and accepted answer.
(The purpose of this post is not to give a different/same answer but to hopefully clarify and isolate where  a Proof By Induction might have a confusing or misleading component on just which statement and which variable is to be "inducted".)
