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

Expert Answers

An illustration of the letter 'A' in a speech bubbles

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.






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






` `

Approved by eNotes Editorial Team