Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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

share|improve this answer
    
Great, that'll do it. I'll accept it as soon as the site lets me :) –  recursive recursion Jun 15 at 21:44
    
@recursiverecursion Happy to help. –  Ayman Hourieh Jun 15 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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.