Question

Problem 4. Recall that F(x) 20+1x+1x2+2x3+3x4 +... 1-x -x2 is the ordinary generating function for the Fibonacci sequence Part A. Find explicit ordinary generating functions for 2m, n 2m n(0, n 2m+ 1 1 And HnF2n Part B. Finding a generating function for Kn F2 is trickier. Start with the equations Add these to develop a recurrence for K, and use that recurrence along with appropriate initial conditions, to construct the ordinary generating function K(x)-E:00 Knxn

solve part a and b it is from from Topics in Combinatorics

Answer 1

solution:

The generating function of the Fibonacci sequence is the power series

"The generating function of the Fibonacci sequence is the power series s(x) = summation^infinity_k = n F_k x^k. this series has a simple and interesting closed form solution for

This series has a simple and interesting closed-form solution for:

This solution can be proven by using the Fibonacci recurrence to expand each coefficient in the infinite sum defining s(x):

Solving the equation s(x) = x + xs(x) + x2s(x) for s(x) results in the closed form solution.
In particular, math puzzle-books note the curious value, or more generally

for all integers.
Conversely,