Explicit formula for a recursion

Question

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

Answer 1

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.

Answer 2

$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.

Answer 3

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.

Answer 4

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.