1
$\begingroup$

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?

  • 0
    Have you considered induction?2012-11-18
  • 0
    Yeah but it goes a long way around. I need a simple solution.2012-11-18
  • 0
    Induction in this case is very simple. Shouldn't take more than two lines.2012-11-18
  • 0
    I'd love to see your answer.2012-11-18
  • 1
    If you know the solution, induction works. If you don;'t know a solution, equations like this work in the same way as linear differential equations. There is a generic solution $G(n)=2G(n-1)$ so $G(n) = 2^nG(0)$ and a special solution $S(n)=2S(n-1)+n$ - a solution of the form $S(n)=p(n)$ can be tried - generally with $p(n)$ of the same degree as the function of $n$ in the recurrence (in this case linear) - but of higher degree when the characteristic equation of the recurrence has a root (multiple root) equal to 1. Then $T(n)=S(n)+aG(n)$ with $a$ to fit initial condition.2012-11-18
  • 0
    @VISHNUVIVEK Sure.2012-11-18
  • 0
    @MarkBennet Thanks Mark..2012-11-19

6 Answers 6

8

\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)$$

  • 0
    Hey Marvis, your answer seems the best one. (1) But how did you expand the summation in the fourth line. Is there any formula? (2) And in the last step, why did you add 2^(n-1). Where did it come from?2012-11-19
  • 0
    @VISHNUVIVEK (1) I have added the details for the summations. (2) If you look at the third line you have $$T(n) = 2^{n-1} + \sum_{j=0}^{n-2}2^j (n-j)$$ Hence, there is a $2^{n-1}$ term in $T(n)$.2012-11-19
  • 0
    Technically speaking, this is not a proof. The problem lies in the lack of justification of the fifth equal sign (the one just before $2^kT(n-k)+\cdots$).2012-11-19
  • 0
    @did True. At some stage induction has to be used. But I guess that is not what exactly OP is interested in. The OP wants in some sense a universal trick to solve these recurrence equations.2012-11-19
4

Hint: substitute $T(n)=G(n)-n-2$

  • 0
    could you please elaborate.2012-11-18
  • 1
    hmmm... do you know what substitution is?2012-11-18
  • 1
    Have you actually tried what is suggested?2012-11-18
  • 0
    It makes sense, but the answer won't be given during exam. So, I don't think it's a good idea to go from the answer.2012-11-18
  • 2
    Then you should take into account comment of Mark Bennet given to your question. It shows the main idea. In fact you haven't mentioned that you need general method for solving such questions at exams, you just asked the way to solve this recurrence2012-11-18
  • 0
    Please see my generalized solution on this page based on the your hint. What can I say? Thank you.2017-09-21
4

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.

  • 0
    thankyou Nameless..but this is not quite the method I was looking for..2012-11-19
  • 3
    @VISHNUVIVEK *but this is not quite the method I was looking for*... Are we supposed to guess *the method you were looking for*?2012-11-19
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.$$

  • 0
    Hey Sperners, you've assumed D(n)=T(n)−T(n−1). Can you tell me a reason why you've assumed like that.2012-11-19
  • 0
    @VISHNUVIVEK, I define $D$ this way to get a recurrence without $n$ in it.2012-11-19
1

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

1

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

  • 0
    How dare you generalize. (+1)2017-10-29
  • 0
    @SimplyBeautifulArt I live for it. I get tired of answering the same question over and over again.2017-10-30