# Explicit formula for a recursion

How can you express the following recursion explicitly? \begin{cases} T_0 = 1\\ T_n = 1 + 2\cdot T_{n-1}\\ \end{cases}

-
Very similar to math.stackexchange.com/questions/755571/…. See my answer there. –  lhf May 16 '14 at 13:32

There is a standard method for solving this kind of thing, which you should easily find if you use the math.se search box.

However in the present case we can calculate the successive values $$1,\,3,\,7,\,15,\,31,\ldots\ ;$$ this is enough to guess that $T(n)=2^{n+1}-1$, which can then be proved by induction.

-

Let $T_n=a_n+c$, where $c$ is a constant that will be chosen later. Then our recursion can be rewritten as $$a_n+c=2(a_{n-1}+c)+1.$$ It follows that $$a_n=2a_{n-1} +c+1.$$ If we choose $c=-1$, the recurrence becomes $$a_n=2a_{n-1},$$ with $a_0=2$. Thus $a_n=2^{n+1}$ and therefore $T_n=2^{n+1}-1$.

Remark: The above trick can be used on $T_n=pT_{n-1}+q$, where $p\ne 1$, and analogues can be used in somehat more complicated situations.

-

Let $T_n = U_n - 1$ for all $n$. Then the recursion written in terms of $U$ is $$U_n - 1 = 1 + 2(U_{n-1} - 1) = 2 U_{n-1} - 1,$$ or $$U_n = 2 U_{n-1},$$ with initial condition $U_0 = T_0 + 1 = 2$. So $U_n = 2^{n+1}$ by inspection, and the rest is straightforward.

-
What's the motivation for $T_n = U_n - 1$? –  200_success May 16 '14 at 17:01

$T_n = 1+2T_{n-1}$. Shift the index. $T_{n+1} = 1+2T_n$. Subtract.

$T_{n+1}-T_n = 2T_n-2T_{n-1}$ or $T_{n+1}-3T_n+2T_{n-1} = 0$.

Now solve it like a general linear recurrence by finding the characteristic polynomial and so on.

-
From $T_{n+1}-T_n = 2T_n-2T_{n-1}$ we get $T_{n+1}-T_n = 2^n(T_1-T_0)$. –  lhf May 16 '14 at 14:20