Solve the recurrence $T(n) = 2T(n-1) + 2n - 1$

Question

I need help with recurrence equation: for $n\geq 2$, $$T(n) = 2T(n-1) + 2n - 1$$ with the initial condition $T(1) = 1.$

Can somebody solve this equation step by step?

Answer 1

i) Solve the homogeneous recurrence $T(n)=2T(n-1)$. (Ans: $T_o(n)=C\cdot 2^n$ with $C\in\mathbb{R}$).

ii) Find a particular solution of the form $An+B$ with $A,B\in\mathbb{R}$. (Ans: $T_p(n)=-2n-3$)

iii) Add all together (Ans: $T(n)=T_o(n)+T_p(n)$)

iv) Find $C$ such that $T(1)=1$. (Ans: $C=3$)

Finally, the solution is $T(n)=3\cdot 2^n-2n-3$.

Answer 2

Hint:

1. Divide both sides by $2^n$.

2. Telescoping, obtain the sum $\displaystyle \sum_{j=2}^n\frac{2j-1}{2^j}$.

Answer 3

Taking $T(n+1) = 2T(n) + 2n + 1$ and $T(n) = 2T(n-1) + 2n - 1$ and subtracting the second to the first we get $x_n=2x_{n-1}+2$ where $x_n=T(n+1)-T(n)$. Doing the same to the second recurrence relation we get $y_n=2y_{n-1}$ with $y_n=x_{n+1}-x_n$. At this point it is easy to see that $y_n=2^ny_1=3\cdot 2^n$ since $y_1=3$. Hence $x_n=x_{n-1}+3\cdot 2^{n-1}=x_1+3(2+...+2^{n-1})=3\cdot 2^n-2$ since $x_1=4$. Finally $T(n)=T(n-1)+3\cdot 2^{n-1}-2=T(1)+3(2+...+2^{n-1})-2(n-1)=3\cdot 2^n-2n-3$.