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.
On
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".)
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$.
Hence at any rate $A(n)=2^m$.