2
$\begingroup$

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$
  • $\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$ Possible duplicate of Solving or approximating recurrence relations for sequences of numbers $\endgroup$ – David Richerby Jan 10 at 13:05
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$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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