Evaluate $T(n)=2T(n-1)+1$ 
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$?
 A: 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.
A: 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$.
A: 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.
