Solving Recurrence Relations using Fibonacci Sequence

[stanyeo1984]

Recall that the Fibonacci sequence is defined by the initial conditions F0 = 0 and
F1 = 1, and the recurrence relation Fn = Fn−1 + Fn−2 for n > 2.
(a) Let F(z) = F0 + F1z + F2z
2 + F3z
3 + · · · be the generating function of the
Fibonacci numbers. Derive a closed formula for F(z).
(b) Consider the recurrence relation an = 19 (F0 an−1 + F1 an−2 + · · · + Fn−1 a0),
n > 1 with a0 = 9. Derive a closed formula for the generating function A(z)
of the sequence an.
(c) Find an explicit formula for an.

 

[topsquark]

Recall that the Fibonacci sequence is defined by the initial conditions F0 = 0 and
F1 = 1, and the recurrence relation Fn = Fn−1 + Fn−2 for n > 2.
(a) Let F(z) = F0 + F1z + F2z
2 + F3z
3 + · · · be the generating function of the
Fibonacci numbers. Derive a closed formula for F(z).

What is your series? First you say "Let F(z) = F0 + F1z + F2z" but then what do the next two lines have to do with it? "2 + F3z, 3 + ... What do these lines mean?

-Dan

 

[stanyeo1984]

What is your series? First you say "Let F(z) = F0 + F1z + F2z" but then what do the next two lines have to do with it? "2 + F3z, 3 + ... What do these lines mean?

-Dan

Recall that the Fibonacci sequence is defined by the initial conditions F₀ = 0 and
F₁ = 1, and the recurrence relation F_n= F_n-1 + F_n-2 for n >= 2.

(a) Let F(z) = F₀ +F₁z + F₂z² + F₃z³ + ··· be the generating function of the
Fibonacci numbers. Derive a closed formula for F(z).

(b) Consider the recurrence relation a_n = 19 (F₀a_n-1 + F₁a_n-2 + · · · + F_n-1a₀), n >= 1 with a₀= 9. Derive a closed formula for the generating function A(z) of the sequence a_n.

(c) Find an explicit formula for a_n.

 

[scott1204]

Recall that the Fibonacci sequence is defined by the initial conditions F₀ = 0 and
F₁ = 1, and the recurrence relation F_n= F_n-1 + F_n-2 for n >= 2.

(a) Let F(z) = F₀ +F₁z + F₂z² + F₃z³ + ··· be the generating function of the
Fibonacci numbers. Derive a closed formula for F(z).

(b) Consider the recurrence relation a_n = 19 (F₀a_n-1 + F₁a_n-2 + · · · + F_n-1a₀), n >= 1 with a₀= 9. Derive a closed formula for the generating function A(z) of the sequence a_n.

(c) Find an explicit formula for a_n.

I've solved part a

anyone can solve (b) and (c)?
part b does not look like fibonacci sequence.

 

[johng1]

Hi all,
Here's a solution. Notice as usual with generating functions no attention is paid to convergence, but as usual at the end you can go back and verify the steps for z values where the generating functions converge.