2
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ $2T_{n-1}+2=2(T_{n-1}+1)=2U_{n-1}.$ $\endgroup$ Aug 30 '18 at 16:49
  • $\begingroup$ Is it $U_n = 2U_{n-1}$ or $U_{n+1} = 2U_{n-1}$? $\endgroup$
    – ArsenBerk
    Aug 30 '18 at 16:53
  • 2
    $\begingroup$ 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$ $\endgroup$ Aug 30 '18 at 16:54
  • $\begingroup$ Your second equation does not match the text. In Concrete Mathematics, the equation written is $T_n+1=2T_{n-1}+2$. $\endgroup$ Aug 30 '18 at 17:09
  • 1
    $\begingroup$ Please, don't add links to online version of copyrighted material, $\endgroup$
    – egreg
    Aug 30 '18 at 17:20
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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