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?
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?
\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)$
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.
Hint: substitute $T(n)=G(n)-n-2$
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.$
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)$.
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$.