<s>[INST] 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.
 [/INST] 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.
</s>