3
$\begingroup$

I'm working through the Concrete Mathematics textbook (by Ronald Graham, Donald Knuth, and Oren Patashnik), and am confused about problem 1.7, which is below:

Let $H(n) = J(n + 1) - J(n)$. Equation (1.8) tells us that $H(2n) = 2$, and $H(2n+1) = J(2n+2)-J(2n+1) = (2J(n+1)-1)-(2J(n)+1) = 2H(n)-2$, for all $n \geq 1$. Therefore it seems possible to prove that $H(n) = 2$ for all $n$, by induction on n. What's wrong here?

Equation 1.8 is below:

$J(1) = 1; $
$J(2n) = 2J(n) − 1$, for $n \geq 1;$
$J(2n + 1) = 2J(n) + 1$ for $n \geq 1$.

I understand that $H(n)=2$ is not true, because the base case for $H(1) \neq 2$, but I don't understand why we would ever think $H(n)=2$, since $H(2n+1) \neq 2$. Any help? This is my first post, so apologies if my question is not appropriate.

1 Answers 1

2

Look at $H(2n+1)=2H(n)-2$ This implies that if $H(n)=2$ then $H(2n+1)=2$. Since every number is $2n$ or $2n+1$, and we know $H(2n)=2$, we might jump to the conclusion that $H(n)=2$ for all $n$.

  • 0
    Ah, as the question says, "Therefore it seems possible to prove that$H(n)=2$for all n, by induction on n." Thanks for your help.2012-12-11