# Recursion and Closed Formulas

• Mar 2nd 2010, 09:44 PM
FatherMike
Recursion and Closed Formulas
Hello!

I've be scanning different help forums and I have a come across two different questions involving finding closed formulas. I have attempted to answer them with no luck and now I am curious of the answer.

The questions are --> Find a closed formula for the sequence:

a) 0,1,3,0,1,3,0,1,3,0,1,3,0,.... where a0 = 0, a1 = 1, a2 = 2, a3 = 0,...

b) an = an-1 + 3an-2, where a0 = 0 and a1 = 1

Perhaps one of you could shed some light on these questions. I appreciate your time. Thank you in advance!
• Mar 2nd 2010, 10:56 PM
MollyMillions
For the first one, I'd do it with generating functions - the generating function for $0 + 1x + 3x^2 + 0x^3 + 1x^4 + 3x^5 + ...$ is $\frac {x + 3x^2}{1-x^3}$.
So $a_n = [x^n] \frac {x + 3x^2}{1-x^3}$. By that I mean the coefficient of $x^n$ in the sequence generated by $\frac {x + 3x^2}{1-x^3}$.

The second one is just a regular homogeneous recursion. Find the characteristic polynomial ( $x^2 - x - 3$). Find its roots: these are $\frac {1 \pm \sqrt{13}}{2}$. Then solve the system:
$a_0 = 0 = x + y$
$a_1 = 1 = x(\frac {1 + \sqrt{13}}{2}) + y(\frac {1 - \sqrt{13}}{2})$.
The closed formula is $a_n = x(\frac {1 + \sqrt{13}}{2})^n + y(\frac {1 - \sqrt{13}}{2})^n$.
• Mar 4th 2010, 05:21 AM
FatherMike
Thanks!

If you don't mind me asking, were you able to come up with a closed formula for the sequence generated by (x + 3x^2)/(1-x^3) .

I've tried splitting it up until different series and simplfying with no luck. I have a feeling the closed formula will involve complex numbers, but at the moment I have only found formulas that work for a0, a3, a6, etc.. (where the coefficient is 0.

For example--> (([-1 + i*sqrt(3)]/2)^n) - (([-1 - i*sqrt(3)]/2)^n)

Any ideas anyone?