Question

Which one of the following expresses the ordinary generating function of the Fibonacci recurrence

Fn=Fn−1+Fn−2 when n≥2?
a) x/(1−x−x)
b) 1/(1−x−x)
c) 1+x+x^2
d) x^2/(1−x−x)

​

Answer 1

The ordinary generating function of the Fibonacci sequence is given by option (b) 1/(1-x-x^2), which can be derived by utilizing the recursive definition of the sequence and algebraic manipulation.

Step-by-step explanation:

The ordinary generating function for the Fibonacci sequence, where Fn = Fn-1 + Fn-2 for n ≥ 2, and with initial values F0 = 0 and F1 = 1, is expressed as option (b) 1/(1-x-x2). To derive it, we can write the generating function, G(x), as G(x) = F0 + F1x + F2x2 + F3x3 + ... . Utilizing the recursive definition of the Fibonacci sequence and algebraic manipulation, we would obtain the expression for G(x) that simplifies to the formula in option (b).