# 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.

-

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)$.

-
Great, that'll do it. I'll accept it as soon as the site lets me :) –  recursive recursion Jun 15 '14 at 21:44
@recursiverecursion Happy to help. –  Ayman Hourieh Jun 15 '14 at 21:47

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.

-

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.$$

-