# Closed Form

• September 23rd 2009, 08:16 AM
vexiked
Closed Form
How could one write a closed form function of the following..

F(0) = 0
F(1) = 1
F(2) = 4
F(n) = 3 * (F(n-1) – F(n-2)) + F(n-3) + 3

Computing
f(3) = 3 * (4-1) + 0 + 3 = 12
f(4) = 3 * (12-4) + 1 + 3 = 28
f(5) = 3 * (28-12) + 4 + 3 = 55

I am not seeing a pattern here any help would be appreciated.
• September 23rd 2009, 10:23 AM
Bruno J.
Consider $G(x)=F_1x+F_2x^2+...$. You have :

$G(x)/x=F_1+F_2x+F_3x^2+...=1+F_2x+F_3x^2+...$

$(G(x)/x-1)/x = F_2+F_3x+F_4x^2... = 4+F_3x+F_4x^2...$

$((G(x)/x-1)/x-4)/x = F_3+F_4x + F_5x^2 +...$

Now $((G(x)/x-1)/x-4)/x = \sum_{j=0}^\infty F(j+3)x^j = \sum_{j=0}^\infty (3F(j+2)-3F(j+1)+F(j)+3)x^j$

$= 3(G(x)/x-1)/x-3G(x)/x+G(x)+\frac{3}{1-x}$.

Solve for $G(x)$ and express it as partial fractions; the coefficient of $x^n$ will be $F_n$.