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.