MHB Solving Recurrence Relations using Fibonacci Sequence

AI Thread Summary
The discussion focuses on solving recurrence relations using the Fibonacci sequence. It begins with defining the generating function F(z) for Fibonacci numbers and seeks a closed formula for it. The second part introduces a new recurrence relation for the sequence an, involving Fibonacci numbers, and requests a closed formula for its generating function A(z). Participants express confusion about the connection between the generating function and the recurrence relation, with one member confirming they have solved part (a) and seeking help for parts (b) and (c). The conversation emphasizes the importance of verifying convergence in generating functions.
stanyeo1984
Messages
13
Reaction score
0
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.
 
Physics news on Phys.org
stanyeo1984 said:
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
 
topsquark said:
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 F0 = 0 and
F1 = 1, and the recurrence relation Fn= Fn-1 + Fn-2 for n >= 2.

(a) Let F(z) = F0 +F1z + F2z2 + F3z3 + ··· be the generating function of the
Fibonacci numbers. Derive a closed formula for F(z).

(b) Consider the recurrence relation an = 19 (F0an-1 + F1an-2 + · · · + Fn-1a0), 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.
 
stanyeo1984 said:
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 + F2z2 + F3z3 + ··· be the generating function of the
Fibonacci numbers. Derive a closed formula for F(z).

(b) Consider the recurrence relation an = 19 (F0an-1 + F1an-2 + · · · + Fn-1a0), 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.

I've solved part a

anyone can solve (b) and (c)?
part b does not look like fibonacci sequence.
 
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.

2qltwzc.png
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top