Concrete Mathematics book I don't understand conversion in (1.1) to (1.3)

Question

I started reading the book Concrete Mathematics 2nd edition and there is a conversion I don't understand(is in page 4 of the book, equation(1.3)), it says:

We have 2 equations:

$T_0 + 1 = 1$

$T_{n+1} = 2T_{n-1} + 2$

Now, if we let $U_n = T_n + 1$, we have

$U_0 = 1$; //I understand this substitution

$U_n = 2U_{n-1}$ //this is the substitution(on the right side) it has no sense to me

It should be(according to me):

Since $2T_{n-1} + 2$ can be expressed as $2T_{n-1} + 1 + 1$

the conversion should be:

$2U_{n-1}+1$

thanks for your help guys

Answer 1

Looking at the book, the recurrence presented was,

$$T_{n}=2T_{n-1}+1$$

What is actually written down is,

$$T_{n}+1=2T_{n-1}+2$$

Which nicely shows that,

$$T_{n}+1=2(T_{n-1}+1)$$

---

A general trick is to look for a particular solution to the recurrence and then look at the solution to the homogenous equation.

There exists a constant solution to the recurrence,

$$T_{n}=2T_{n-1}+1$$

$$-1=2(-1)+1$$

Subtracting the second equation (which shows the constant solution is $-1$) from the first gives,

$$T_{n}+1=2(T_{n-1}+1)$$

With $U_{n}=T_{n}+1$ we have,

$$U_{n+1}=2U_{n}$$

Which is nothing but the corresponding homogenous recurrence relation.

Answer 2

You're reading wrongly what the book says: the recurrence before (1.3) is \begin{align} &T_0+1=1 \\ &T_n+1=2T_{n-1}+2 \end{align} which stems from the recurrence (1.1), namely \begin{align} &T_0=0 \\ &T_n=2T_{n-1}+1 \end{align} You are reading the second line in the first display as $$ \color{red}{T_{n+1}=2T_{n-1}+2}\quad\leftarrow\text{wrong!} $$ which is quite different and not what is in the book.

If $U_n=T_n+1$, then we obviously get \begin{align} &U_0=1 \\ &U_n=2U_{n-1} \end{align}