Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Very similar to math.stackexchange.com/questions/755571/…. See my answer there. –  lhf May 16 at 13:32

4 Answers 4

up vote 4 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
2  
What's the motivation for $T_n = U_n - 1$? –  200_success May 16 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.

share|improve this answer
    
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 at 14:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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