finding the explicit function of a recursive sequence 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.
 A: 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)$.
A: 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.
A: 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.
$$
