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
    Why would we assume $H(n)=2$? I'm having trouble wrapping my head around that.2012-12-11
  • 0
    That's how proofs by induction go. You prove a base case, then you show that if it holds true in some situation it then must also hold true in the next situation. $H(n)=2$ is the induction hypothesis.2012-12-11
  • 0
    I get the induction part, but just to be sure: So it's not because $2n$ is a multiple of $n$? I was thinking because $H(2n)=2$ and $2n$ is a multiple of $n$, then we can assume $H(n)=2$.2012-12-11
  • 0
    It has nothing to do with $2n$ being a multiple of $2$. We're trying to prove $H(n)=2$, by induction. The base case, $H(1)=2$, is false; but if we are careless enough to forget to check that base case, then we would proceed to take $H(n)=2$ as the induction hypothesis, and we would think we had constructed a legitimate proof.2012-12-11
  • 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