2

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.

cinsk
  • 123
  • "the authors" What authors? What book? – fleablood Jun 18 '19 at 20:52
  • In the book, "Concrete Mathematics". I guess that my post actually include all information to prove that. – cinsk Jun 18 '19 at 20:53
  • What do you mean "As usual $n = 2^m + 1$ and $0 \le l < 2^m$ for $n \ge 1$"?. If $n = 24$ then $n \ne 2^m + 1$ for any possible $m$. – fleablood Jun 18 '19 at 20:55
  • @fleablood As usual, it is hard to distinguish between $l$ and $1$ ... Apparently the OP fell for that as well when blindly copying the problem statement – Hagen von Eitzen Jun 18 '19 at 21:00
  • When you are asked to mention a book, please take the habit to mention its authors (Graham, Knuth, Patachnik ) ; moreover, you can have its pdf online https://www.csie.ntu.edu.tw/~r97002/temp/Concrete%20Mathematics%202e.pdf – Jean Marie Jun 18 '19 at 21:03

2 Answers2

3

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$.

Hagen von Eitzen
  • 374,180
2

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".)

fleablood
  • 124,253