Solve the recurrence `T_n=2T_(n-1)+1` with `T_0=4` using the iteration method. Simplify algebraically.

So as to not interrupt the flow of the work below too much, we first state that `1+2+2^2+2^3+...+2^(n-1)` is a geometric series with first term `1` and common ratio `2.` According to the formula for the first `n` terms of this geometric sequence, we get

`1+2+2^2+...+2^(n-1)=2^(n)-1`                               (1)

Now we list the first few terms of the recursive sequence `T_n` and see if there is a pattern.

`T_0=4`

`T_1=2*T_0+1`

`T_2=2*T_1+1=2(2*T_0+1)+1=2^2*T_0+2+1`

`T_3=2*T_2+1=2(2^2*T_0+2^1+1)+1=2^3*T_0+2^2+2+1`

`T_4=2*T_3+1=2(2^3*T_0+2^2+2+1)+1=2^4*T_0+2^3+2^2+2+1,`

and so on, so using equation (1), it appears (this isn't a proof, but once we know the formula a proof by induction isn't far off) that the general term is

`T_n=2^n*T_0+2^(n-1)+2^(n-2)+...+2+1`

`=2^n*T_0+2^n-1`

`=2^n(T_0+1)-1`

`=5*2^n-1.`

` `