# Solve recurrence T(n)=2T(n-1)+n for n greater than 1 and T(1)=1 [duplicate]

Problem statement: Solve $$T(n)$$ for $$T(n)=2T(n-1)+n$$, $$n > 1$$, and $$T(1)=1$$.

My attempt: I tried back substituting but I am unable to find a general pattern: \begin{align*} T(n) &=2^2 T(n-2)+3n-2 \\ &=2^3 T(n-3)+7n-10 \\ &=2^4 T(n-4)+15n-34 \\ &=\cdots \end{align*}

## marked as duplicate by David Richerby, Discrete lizard♦, Juho, Thomas Klimpel, Luke MathiesonFeb 3 at 0:29

• Are you familiar with (solving recurrences using) generating functions? – dkaeae Jan 10 at 9:49
• Yes, but what will be T(0) , the initial condition? As that expression right of T(n) is only valid for n>=2 – Epsilon zero Jan 10 at 10:10
• You can always "shift" the function $T$ by setting $T_1(n) = T(n + 1)$ and solving the recurrence for $T_1$ instead. – dkaeae Jan 10 at 10:37

Hint: \begin{align*} T(n) &= 2T(n-1) + n \\ &= 2^2 T(n-2) + (2n + n) - 2 \\ &= 2^3 T(n-3) + (2^2n + 2n + n) - (2^2 \cdot 2 - 2) \\ &= 2^4 T(n-4) + (2^3n + 2^2n + 2n + n) - (2^3 \cdot 3 + 2^2 \cdot 2 + 2^1 \cdot 1) \\ &= \cdots \end{align*}

If you are familiar with the required methods, you can also solve it using generating functions (and, e.g., techniques from here or chapter 7 of "Concrete Mathematics" by Graham, Knuth, et al.).

A different general method to solve these recurrences is to frame them as a matrix multiplication :

$$\left( \begin{matrix}T_{n+1}\\ n+1 \\ 1\end{matrix} \right) = \left( \begin{matrix}2T_{n}+n+1\\ n+1 \\ 1\end{matrix} \right) = \underbrace{\left( \begin{matrix}2&1&1 \\ 0&1&1 \\ 0&0&1\end{matrix} \right)}_M \left( \begin{matrix}T_{n}\\ n \\ 1\end{matrix} \right)$$

Now you have: $$\left( \begin{matrix}T_{n}\\ n \\ 1\end{matrix} \right) = M^n \left( \begin{matrix}1\\ 1 \\ 1\end{matrix} \right)$$

You can get $$M^n$$ in $$O(log(n))$$ time through exponentiation.

• Furthermore, by finding the Jordan form of $M$, you can extract the closed form solution. – Yuval Filmus Jan 10 at 14:14

Another option is to consider the related sequence $$S(n) = T(n)/2^n$$, which satisfies the recurrence $$S(n) = S(n-1) + \frac{n}{2^n},$$ whose solution is simply $$S(n) = S(1) + \sum_{m=2}^n \frac{m}{2^m}.$$ The sum can be evaluated in many ways, for example (adding the $$m=1$$ term) $$\sum_{m=1}^n \frac{m}{2^m} = \sum_{m=1}^n \sum_{k=1}^m \frac{1}{2^m} = \sum_{k=1}^n \sum_{m=k}^n \frac{1}{2^m} = \sum_{k=1}^n \left(\frac{1}{2^{k-1}} - \frac{1}{2^n} \right) = 2 - \frac{n+2}{2^n}.$$ This shows that $$S(n) = 2 - \frac{n+2}{2^n}, \quad T(n) = 2^{n+1} - n - 2.$$ Indeed, one calculates that $$T(1) = 2^2-1-2 = 1$$, and $$T(n) - 2T(n-1) = 2^{n+1} - n - 2 - 2(2^n - n - 1) = n.$$