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.


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

| cite | improve this answer | |
  • $\begingroup$ Why would we assume $H(n)=2$? I'm having trouble wrapping my head around that. $\endgroup$ – dylam Dec 11 '12 at 22:43
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Dec 11 '12 at 22:49
  • $\begingroup$ 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$. $\endgroup$ – dylam Dec 11 '12 at 22:57
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Dec 11 '12 at 23:31
  • $\begingroup$ 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. $\endgroup$ – dylam Dec 11 '12 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.