I've decided to dive in Concrete Mathematics despite only doing a couple of years of undergraduate maths many years ago. I'm looking to work through all the material whilst plugging gaps in my knowledge no matter how large they are.
However, solving recurrence relation 1.1 - The Towers of Hanoi is causing me issues.
The recurrence relation is as follows:
$T_0 = 0$
$T_n=2T_{n-1}+1$ for $n>0$
To find the closed form the book adds 1 to both sides of the equations to get:
$T_0+1=1$
$T_n+1=2T_{n-1}+2$
Then we let $U_n=T_n+1$. Now I get lost. How do I get from the line above to the second line below after the substitution of $U_n$. It seems like I'm missing something simple.
$U_0=1$
$U_n=2U_{n-1}$
Then the book goes on to say:
It doesn't take genius to discover that the solution to this recurrence is just $U_n=2^n$; hence $T_n=2^n-1$.
Again, I'm lost, how do I get to $U_n=2^n$?
A bit disheartening considering this is meant to be so easy.
Any help is appreciated. Thanks.
You’re just missing a little algebra. You have $U_n=T_n+1$ for all $n\ge 0$, so $U_{n-1}=T_{n-1}+1$, and therefore $2T_{n-1}+2=2(T_{n-1}+1)=2U_{n-1}$. Combine this with $T_n+1=2T_{n-1}+2$, and $U_n=T_n+1$, and you get $U_n=2U_{n-1}$, with $U_0=1$.
Now notice that $U_n$ is just doubling each time $n$ is increased by $1$:
$$\begin{align*} U_1&=2U_0\\ U_2&=2U_1=2^2U_0\\ U_3&=2U_2=2^3U_0\\ U_4&=2U_3=2^4U_0 \end{align*}$$
The pattern is clearly going to persist, so we conjecture that $U_n=2^nU_0$ for each $n\ge 0$. This is certainly true for $n=0$. Suppose that it’s true for some $n\ge 0$; then $$U_{n+1}=2U_n=2\cdot2^nU_0=2^{n+1}U_0\;,$$ and the conjecture follows by mathematical induction.
Now we go back and use the fact that $U_0=1$ to say that $U_n=2^n$ for each $n\ge 0$, and hence $T_n=U_n-1=2^n-1$.
In my answer to this question I solved another problem using this technique; you might find the explanation there helpful.