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

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$

• $2T_{n-1}+2=2(T_{n-1}+1)=2U_{n-1}.$ Aug 30 '18 at 16:49
• Is it $U_n = 2U_{n-1}$ or $U_{n+1} = 2U_{n-1}$? Aug 30 '18 at 16:53
• When it says, let $U_n = T_n + 1$, what they really mean is that $U_k = T_k + 1$ for any $k$, so you not only have $U_n = T_n + 1$, but also $U_{n-1} = T_{n-1} + 1$ Aug 30 '18 at 16:54
• Your second equation does not match the text. In Concrete Mathematics, the equation written is $T_n+1=2T_{n-1}+2$. Aug 30 '18 at 17:09

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.

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}