Recursion and Closed Formulas

**FatherMike** · March 2nd 2010, 08:44 PM

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!

**MollyMillions** · March 2nd 2010, 09:56 PM

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

**FatherMike** · March 4th 2010, 04:21 AM

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?

Thread: Recursion and Closed Formulas

LinkBack

Thread Tools

Display

Recursion and Closed Formulas

Similar Math Help Forum Discussions

Closed Form of a Recursion with a Sqared Term

Proof: recursive and closed formulas

Metric Space, closed sets in a closed ball

Closed Linear Operators/Closed Graph Theorem

Continuity & inverse image of closed sets being closed

Search Tags