2
$\begingroup$

This question already has an answer here:

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*}$$

$\endgroup$

marked as duplicate by David Richerby, Discrete lizard, Juho, Thomas Klimpel, Luke Mathieson Feb 3 at 0:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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.).

$\endgroup$
2
$\begingroup$

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.

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

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. $$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.