finding the explicit function of a recursive sequence

Question

So I have the recursive sequence $f(0) = 0, f(n+1) = 2f(n)+ (n+1)^2$, and I'm not quite sure how to make it explicit. Substituting $n$ for $n+1$ cleans it up a little, yielding $f(n) = 2f(n-1) + n^2$, but I'm not quite sure what to do after that. It seems to be a lot harder than it looks. Any help would be appreciated.

Answer 1

Divide both sides by $2^n$ to get $$ \frac{f(n)}{2^n} = \frac{f(n-1)}{2^{n-1}} + \frac{n^2}{2^n}. $$

Let $g(n) = f(n)/2^n$. This gives $$ g(n) = g(n-1) + \frac{n^2}{2^n}. $$

It follows that $$ g(n) = \sum_{k=0}^n \frac{k^2}{2^k}. $$

This sum has a closed form. See this question for how to find it. Once done, multiply by $2^n$ to get a closed form for $f(n)$.

Answer 2

Here is a generating functions solution.

Let $$ F(x) = \sum_{n \ge 0} f(n) x^n. $$ Then the recurrence $f(n) = 2 f(n-1) + n^2 \;\; (n \ge 1)$ becomes $$ F(x) = 2xF(x) + \sum_{n \ge 1} n^2 x^n + f(0) $$ or $$ F(x) = 2xF(x) + \frac{x(1 + x)}{(1 - x)^3}. $$ Solving, $$ F(x) = \frac{x + x^2}{(1 - x)^3(1 - 2x)} $$ The partial fraction decomposition of this is $$ F(x) = \frac{6}{1-2x} - \frac{3}{1-x} - \frac{1}{(1-x)^2} - \frac{2}{(1-x)^3} $$ which gives us the general formula for $f(n)$: $$ f(n) = 6 \cdot 2^n - 3 - (n+1) - (n+2)(n+1) = \boxed{6 \cdot 2^n - n^2 - 4n - 6}. $$ You can check directly that this verifies the initial value $f(0) = 0$ and the recurrence.

Answer 3

Here is another method. First, you look for a polynomial satisfying the recurrence (though this polynomial will not satisfy the initial condition.) So if $P$ is the polynomial, you want $$ P(n+1) = 2P(n) + (n+1)^2 $$ Since $P(n+1) - 2P(n)$ must have the same degree as $P$, and since $(n+1)^2$ has degree $2$, $P$ must have degree $2$. So, $P(x) = ax^2 + bx + c$. Solving the above equation for $a,b, c$ gives $a = -1$, $b = -4$, $c = -6$, so $$ P(x) = -x^2 - 4x - 6. $$ Now, let $g(n) = f(n) - P(n)$. Because we chose $P$ to satisfy the same recurrence as $f$, the recurrence for $g$ is simply $$ g(n+1) = 2g(n) $$ Hence, $$ g(n) = 2^n g(0) = 2^n(f(0) - P(0)) $$ and the desired formula for $f(n)$ is $$ f(n) = g(n) + P(n) = [f(0) - P(0)] 2^n - P(n) = 6 \cdot 2^n - n^2 - 4n - 6. $$