Decreasing Recurrence Relation

Question

Can someone solve this recurrence? $$ T(n) = 2T(n-1) + n^2 $$

Answer 1

HINT:

Let $T(m)=S(m)+am^2+bm+c$

$n^2=T(n)-2T(n-1)$

$=S(n)+an^2+bn+c-2\{S(n-1)+a(n-1)^2+b(n-1)+c\}$

$\implies n^2=S(n)-2S(n-1)-an^2+n(4a-b)+2b-c-2a$

Set $-a=2,4a-b=0=2b-c-2a$ to find $$S(n)=2S(n-1)=\cdots=2^rS(n-r)$$

Can you take it from here?

Answer 2

Set $a_n \stackrel{\rm def}{=} \frac{T(n)}{2^n}$.

Then your relation becomes $$ 2^n a_n = 2\cdot 2^{n-1} a_{n-1} + n^2 = 2^n a_{n-1} + n^2 $$ i.e. $$ a_n = a_{n-1} + \frac{1}{2^n n^2}. $$ You only have to solve this to find $T(n) = 2^n a_n$: $$ a_n = a_{n-2} + \frac{1}{2^n n^2}+ \frac{1}{2^{n-1} (n-1)^2} = \dots = a_0 + \sum_{k=1}^n \frac{1}{2^k k^2} $$

---

To find a closed-form expression for this last quantity, you can (variants of this have been considered many times on this website) consider the function $$ f\colon x\in (-1,1)\mapsto \sum_{k=1}^n\frac{x^k}{k^2} $$ (you want $f(1/2)$) and try and find $f$ as an integral, using termwise differentiation twice and using the fact that $\sum_{k=1}^n x^k = \frac{1-x^n}{1-x}$. However, this is unlikely to give you an elegant formula, as I don't think (and Mathematica does not seem to think it either) there is a nice closed form for $f(1/2)$.