Solve the recurrence $T(n) = 2T(n-1)+n^2$

Question

Solve the recurrence $$T(1) = 1, T(2) = 1, T(3) = 1,T(n) = 2T(n-1)+n^2, n > 3$$

I have now, $$T(n) = 2T(n-1)+^2 $$ $$= 2(2T(n-2)+(n-1)^2+n^2$$ $$=4T(n-2)+2(n-1)^2+n^2$$ $$....$$ $$2^iT(n-i)+\sum_{k=0}^{i-1}=2^{k}(n-k)^2$$ $$2^{n-1}T(1)+\sum_{k=0}^{n-2}=2^{k}(n-k)^2=2^{n-1}+\sum_{k=0}^{n-2}2^k(n-k)^2$$

Can anyone help.

The @all

Answer 1

Less words, more facts. Let

$$ f(z) = \sum_{n\geq 1} T(n)\,z^n.\tag{1}$$ The recurrence relation hence gives: $$\begin{eqnarray*} f(z) &=& 2\sum_{n\geq 4} T(n-1)\,z^{n} + (z+z^2+z^3)+\sum_{n\geq 4}n^2 z^n\\&=&2z\sum_{n\geq 3}T(n)\,z^n+(z+z^2+z^3)+\frac{z^4 (16 - 23 z + 9 z^2)}{(1-z)^3}\\&=&2z\left(f(z)-z-z^2\right)+(z+z^2+z^3)+\frac{z^4 (16 - 23 z + 9 z^2)}{(1-z)^3}\tag{2}\end{eqnarray*}$$ and it follows that: $$ f(z) = \frac{z \left(1-4 z+5 z^2+15 z^3-25 z^4+10 z^5\right)}{(1-z)^3 (1-2z)}\tag{3}$$ so, by partial fraction decomposition, we have:

$$ \forall n>2,\qquad T(n) = 7\cdot 2^{n-1}-(n+2)^2-2. \tag{4}$$

Answer 2

This is a non-homogeneous linear recurrence relation. There is a standard procedure for solving these when the non-homogeneous term has a particular form, namely a polynomial, an exponential, or the product of a polynomial and an exponential.

In your equation, the non-homogeneous term is $F(n)=n^2$.

The first step is to find the general solution to the associated homogeneous equation, obtained by replacing the non-homogeneous term with 0.

In your equation, the associated homogeneous equation is $T(n)=2T(n-1)$. Suppose the general solution is $u_c(n)$ (also called the complementary function).

The second step is to propose a solution based on the homogeneous term.

Since your non-homogeneous term is a polynomial of degree 2, you propose a general polynomial of degree 2. So your proposed solution in this case is $u_p(n)=an^2+bn+c$.

The third step is to substitute the proposed solution into the non-homogeneous equation and use the resulting equation to find $a,b,$ and $c$.

The fourth step is to construct the general solution to your equation equation from $u_c(n)$ and $u_p(n).$ This is $T(n)=u_p(n)+u_c(n)$.

As I mentioned, this is a fairly standard method, and can probably be found in most textbooks that cover linear recurrence relations.

Answer 3

A linear recurrence of first order, which can always be "solved" (as long as finding closed forms of some ugly sums is possible).

The general form is:

$$ a_{n + 1} = f(n) a_n + g(n) $$

where $a_0$ is given.

Divide by the summing factor:

$$ S_n = \prod_{0 \le k \le n} f(k) $$

Note this is valid as long as $f(k) \ne 0$ over the relevant range.

Thus:

$\begin{align} \frac{a_{n + 1}}{S_n} - \frac{a_n}{S_{n - 1}} &= \frac{g(n)}{S_n} \\ \sum_{0 \le k \le n - 1} \left( \frac{a_{k + 1}}{S_k} - \frac{a_k}{S_{k - 1}} \right) &= \sum_{0 \le k \le n - 1} \frac{g(k)}{S_k} \\ \frac{a_n}{S_{n - 1}} - a_0 &= \sum_{0 \le k \le n - 1} \frac{g(k)}{S_k} \\ a_n &= a_0 S_{n - 1} + s_{n - 1} \sum_{0 \le k \le n - 1} \frac{g(k)}{S_k} \end{align}$

In your particular case $f(n) = 2$ and $g(n) = (n + 1)^2$, $S_n = 2^n$, so that:

$\begin{align} T(n) &= 2^{n - 1} T(0) + 2^{n - 1} \sum_{0 \le k \le n - 1} \frac{(k + 1)^2}{2^k} \\ &= 2^{n - 1} T(0) + 2^n \sum_{0 \le k \le n - 1} \frac{(k + 1)^2}{2^{k + 1}} \\ &= 2^{n - 1} T(0) + 2^{n - 1} \sum_{0 \le k \le n} \frac{k^2}{2^{k - 1}} \end{align}$

The resulting sum is somewhat tricky. We know that:

$\begin{align} \sum_{0 \le k \le n} z^k &= \frac{1 - z^{n + 1}}{1 - z} \\ \frac{\mathrm{d}}{\mathrm{d} z} \left( z \frac{\mathrm{d}}{\mathrm{d} z} \sum_{0 \le k \le n} z^k \right) &= \sum_{0 \le k \le n} k^2 z^{k - 1} \\ &= \frac{1 + (n z - n - 1) z^n}{(1 - z)^2} \end{align}$

Evaluate this at $z = 1/2$ to get your sum:

$$ 2^{-n + 1} (2^{n + 1} - n - 2) $$

so the final result is:

$$ T(n) = 2^{n - 1} T(0) + 2^{n + 1} - n - 2 $$