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