Exercise 6. Use the recurrence relation for the Fibonacci numbers to find the generating function for the Fibonacci sequence. Solution.