# Thread: Recursion and Closed Formulas

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

2. For the first one, I'd do it with generating functions - the generating function for $\displaystyle 0 + 1x + 3x^2 + 0x^3 + 1x^4 + 3x^5 + ...$ is $\displaystyle \frac {x + 3x^2}{1-x^3}$.
So $\displaystyle a_n = [x^n] \frac {x + 3x^2}{1-x^3}$. By that I mean the coefficient of $\displaystyle x^n$ in the sequence generated by $\displaystyle \frac {x + 3x^2}{1-x^3}$.

The second one is just a regular homogeneous recursion. Find the characteristic polynomial ($\displaystyle x^2 - x - 3$). Find its roots: these are $\displaystyle \frac {1 \pm \sqrt{13}}{2}$. Then solve the system:
$\displaystyle a_0 = 0 = x + y$
$\displaystyle a_1 = 1 = x(\frac {1 + \sqrt{13}}{2}) + y(\frac {1 - \sqrt{13}}{2})$.
The closed formula is $\displaystyle a_n = x(\frac {1 + \sqrt{13}}{2})^n + y(\frac {1 - \sqrt{13}}{2})^n$.

3. 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?