Solve the recurrence $T(n) = 2T(n-1) + n$ Solve the recurrence  $T(n) = 2T(n-1) + n$
where $T(1) = 1$ and $n\ge 2$.
The final answer is $2^{n+1}-n-2$
Can anyone arrive at the solution?
 A: Induction: For $n=1$, $T(1)=1=2^{1+1}-1-2$. Suppose $T(n-1)=2^n-n+1-2=2^n-n-1$. Then $T(n)=2T(n-1)+n=2^{n+1}-2n-2+n=2^{n+1}-n-2$ which completes the proof.
A: Hint: substitute $T(n)=G(n)-n-2$
A: This recurrence $$T(n) = 2T(n-1) + n$$ is difficult because it contains $n$. Let $D(n) = T(n) - T(n-1)$ and compute $D(n+1) = 2D(n) + 1$ this recurrence is not so difficult. Of course $D(1) = 4 - 1 = 2 + 1$.
The sequence $D(n)$ goes: $2 + 1$, $2^2 + 2 + 1$, $2^3 + 2^2 + 2 + 1$. $D(n) = 2^{n+1}-1$.
Now $$T(n) = \sum_{i=1}^n D(i) = 2 \sum_{i=1}^n 2^{i} - \sum_{i=1}^n 1 = 2^{n+1}-2-n.$$
A: Let's use the method of annihilators to turn this into a third-order, homogeneous recurrence, and then solve with a characteristic equation.  First, we write the recurrence so $n$ is the least index:
$$T(n) - 2T(n-1)= n \implies T(n+1)-2T(n) = n+1$$
Then, we rewrite the recurrence in terms of the shift operator $E$:
$$(E-2)T(n) = n+1$$
Applying the $(E-1)$ operator to both sides of the equation, we have:
$$(E-1)^2(E-2)T(n) = (E-1)^2(n+1)$$
Now, since $(E-1)^2(n+1) = 0$ (it annihilates that term), we have:
$$(E-1)^2(E-2)T(n) = 0$$
The characteristic equation is, then $(r-1)^2(r-2)=0$, so our roots are $r=1$ (with multiplicity $2$) and $r=2$.  So, the recurrence has the form:
\begin{align*}
T(n) &= c_1\cdot 2^n + c_2 \cdot n1^n + c_3 \cdot 1^n\\
&= c_1\cdot 2^n + nc_2 + c_3
\end{align*}
Using the recurrence relation, we compute $T(1) = 1, T(2) = 4, T(3) = 11$ and can now solve for $(c_1, c_2, c_3)$, which gives the solution $(2, -1, -2)$.
A: Some of the solutions presented here are very arcane. Building on the hint given be @Norbert, we consider the generalized problem
$${{T}_{n}}=A{{T}_{n-1}}+Bn,\quad{{T}_{1}}\,\,\,\text{specified}$$
Let $ {{T}_{n}}={{f}_{n}}+pn+q$ so that
$${{f}_{n}}=A{{f}_{n-1}}+n\left[Ap+B-p \right]+\left[ -Ap+Aq-q \right] $$
Then choose $p$ and $q$ so as to eliminate the quantities in brackets, i.e.,
$$p=-\frac{B}{A-1};\quad q=-\frac{AB}{{{\left( A-1 \right)}^{2}}} \\ 
 {{f}_{n}}=A{{f}_{n-1}} \\ $$
Now, in order for $p$ and $q$, and hence the sequence to be integers, it must be that $A=2$. Clearly, the solution for $f$ is $f_n=2^{n-1}f_1$ and the general solution is given by
$$
\begin{align}
T
&=(T_1-p-q)2^{n-1}+pn+q\\
&=(T_1+3B)2^{n-1}-B(n+2)
\end{align}
$$
This result is in agreement with the others presented herein and has been tested numerically against the recurrence formula for arbitrary positive and negative integer values of $T_1$ and $B$.
A: \begin{align}
T(n) & = 2 T(n-1) + n = 2(2T(n-2) + n-1) + n = 4T(n-2) + 2(n-1) + n\\
& = 8 T(n-3) + 4(n-2) + 2(n-1) + n = 2^k T(n-k) + \sum_{j=0}^{k-1} 2^j (n-j)\\
& = 2^{n-1} T(1) + \sum_{j=0}^{n-2}2^j (n-j) = 2^{n-1} + \sum_{j=0}^{n-2}2^j (n-j)
\end{align}
\begin{align}
\sum_{j=0}^{n-2}2^j (n-j) & =  n \sum_{j=0}^{n-2}2^j - \sum_{j=0}^{n-2} j2^j = n(2^{n-1}-1) - \dfrac{n \cdot 2^n - 3 \cdot 2^n + 4}2\\
& = n(2^{n-1}-1) - (n \cdot 2^{n-1} -3 \cdot 2^{n-1} + 2) = 3 \cdot 2^{n-1} -n - 2
\end{align}
Hence,
$$T(n) = 2^{n-1} + 3 \cdot 2^{n-1} -n - 2 = 2^{n+1} - n - 2$$
EDIT (Adding details)
First note that $\displaystyle \sum_{j=0}^{n-2}2^j$ is sum of a geometric progression and can be summed as shown below.$$\sum_{j=0}^{k} x^j = \dfrac{x^{k+1} -1}{x-1}$$
$\displaystyle \sum_{j=0}^{n-2} j2^j$ is a sum of the form $\displaystyle \sum_{j=0}^{k} jx^j$
$$\sum_{j=0}^{k} jx^j = x \sum_{j=0}^{k} jx^{j-1} = x \dfrac{d}{dx} \left( \sum_{j=0}^k x^j\right) = x \dfrac{d}{dx} \left( \dfrac{x^{k+1} - 1}{x-1}\right) = x \left( \dfrac{kx^{k+1} - (k+1) x^k +1}{(x-1)^2} \right)$$
A: By subtraction
$$
\begin{array}{rrcl}
& T(n)-2T(n-1) &=& n \\
& T(n-1) - 2T(n-2) &=& n-1 \\
\hline
& T(n)-3T(n-1)+2T(n-2) &=& 1
\end{array}$$
Again, by subtraction
$$
\begin{array}{rrcl}
& T(n)-3T(n-1)+2T(n-2) &=& 1 \\
& T(n-1)-3T(n-2)+ 2T(n-3) &=& 1 \\
\hline
& T(n)-4T(n-1)+5T(n-2)-2T(n-3) &=& 0
\end{array}$$
Characteristic equation of the recursion is
$$x^3-4x^2+5x-2 = 0$$
Roots of the equation are $x_1 = x_2 = 1$ and $x_3 = 2$
So, general solution of the recursion is $$T(n) = C_1\cdot 1^n + C_2\cdot n\cdot 1^n + C_3\cdot 2^n$$ or $$T(n) = C_1 + C_2\cdot n + C_3\cdot 2^n$$
now, from $T(1) = 1$ we get $T(2) = 4$ and $T(3) = 11$.
So, we get system 
$$
\begin{array}{ccccccc}
C_1  &+&C_2 &+& 2C_3 &=& 1 \\
C_1 &+&2C_2&+&4C_3 & =& 4 \\
C_1 & +& 3C_2 &+& 8C_3 &=& 11
\end{array}$$
From this system we get that $C_1 = -2$, $C_2 =-1$, and $C_3 = 2$, so particular solution of the recursion is $$T(n) =2\cdot2^n-n-2,$$ or $$T(n) = 2^{n+1}-n-2.$$
A: T(n)=2T(n-1)+n -----(1) 
T(n-1)=2T(n-2)+n-1 ------(2)
T(n-2)=2T(n-3)+n-2 ------(3)
Substitute (3) in (2) and then (2) in (1)
T(n-1)=$2^2T$(n-3)+2(n-2)+(n-1)
T(n)= $2^3$T(N-3)+$2^2$(n-2)+2(n-1)+n
=> T(k)=$2^k$T(n-k) + $2^{k-1}$(n-(k-1))+........+$2^0$n
Now, since T(1)=1, let n-k=1 => k=n-1
T(n)=$2^{n-1}$T(1) + $2^{n-2}$(2) + $2^{n-3}$(3) + $2^{n-n}$(n) --------(4)
Multiply Equation (4) with 2
T(n)=$2^{n}$+$2^{n-1}$ + $2^{n-2}$ + $2^{n-3}$+...... + 2n ----------- (5)
Subtract Equation (5) with (4)
T(n)=$2^{n}$+$2^{n-1}$+$2^{n-2}$+$2^{n-3}$+........+2 -n
Using sum of GP terms, we get :
[ $2^{1}$($2^{n}$-1) - n ]/ (2-1)
= $2^{n+1}$ -2 -n
A: Here's a generating-function approach to both derive and prove the desired formula.
Write $T(n)$ as $T_n$, and let $f(z) = \sum_{n=1}^\infty T_n z^n$ be the ordinary generating function. Now use the recurrence relation and initial condition to obtain
$$T_1 z^1 + \sum_{n=2}^\infty (T_n-2T_{n-1}) z^n = z + \sum_{n=2}^\infty n z^n,$$
equivalently,
$$f(z)-2z f(z)=z + \left(z\sum_{n=1}^\infty n z^{n-1} - z\right) = z D_z \left(\sum_{n=1}^\infty z^n\right)=z D_z\left(\frac{1}{1-z}\right)=\frac{z}{(1-z)^2}.$$
Solving for $f(z)$ yields
$$f(z) = \frac{z}{(1-2z)(1-z)^2}.$$
Now use partial fraction decomposition to obtain
$$
f(z) = \frac{2}{1-2z}-\frac{1}{1-z}-\frac{1}{(1-z)^2}
= \sum_{n=0}^\infty \left(2 \cdot 2^n - 1 - (n+1)\right)z^n,
$$
which implies that
$$T_n = 2 \cdot 2^n - 1 - (n+1) = 2^{n+1} - n - 2.$$
