Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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