Evaluate $T(n)=2T(n-1)+1$

Question

Evaluate $$T(n)=2T(n-1)+1$$ $T(1)=1$

$$T(n)=2T(n-1)+1$$ $$T(n-1)=2T(n-2)+1$$ $$T(n-2)=2T(n-3)+1$$

So $$T(n)= 2(2(2T(n-3)+1)+1)+1...=2^{k}T(n-k)+2^{k-1}+2^{k-2}+...+1$$

for $$2^{k-1}+2^{k-2}+...+1=\frac{1(2^{k-1}-1)}{2-1}=2^{k-1}-1$$

$$T(n)=2^{k}T(n-k)+2^{k-1}-1$$

How to approach this? use $T(n-k)=1$ to get $T(n)=2^k+2^{k-1}-1$?

Answer 1

If $T(n)=2^n-1$, $T(n)=2T(n-1)+1$ and $T(1)=1$ is satisfied. Obviously, the $T(n)$ is unique, so this is the one and only solution to this problem.

Answer 2

You are almost there, except for an error in the geometric sum. It should be

$$2^{k-1}+2^{k-2}+...+1=\frac{1(2^{k}-1)}{2-1}=2^{k}-1$$

hence $$T(n)=2^{k}T(n-k)+2^{k}-1=2^k(T(n-k)+1)-1$$

Then let $n-k=1 \implies k= n-1$ and

$$T(n) = 2^{n-1}(T(1)+1) -1=2^{n-1}2 -1 = 2^n-1 $$

Incidentally, it would have been easier to compute numerically the first terms, guess the pattern, and then check it.

Answer 3

This is a linear first order difference equation. The solution $T_n$ can be written as $$T_n = H_n+P_n$$ where $H_n$ is the general solution of the homogeneous equation $x_n - 2 x_{n-1}=0$ and $P_n$ is a particular solution of the equation.You get immediately $H_n= c 2^n$. As for the particular solution, we can try one similar to the RHS, in this case, a choice would be $P_n= \alpha$. Plugging this into the equation, you get $\alpha = -1$. Hence, the general solution to this equation is $$ T_n = c 2^n -1. $$

Fianally, since $T_1=1$, we get $T_n = 2^{n-1} -1$.