[MUSIC] Let us prove this proposition. The right hand side of it equals, C over 1- phi q + D over 1- psi q. And this is C(1- Psi q) + D (1- phi q), divided by (1- phi q)(1- psi q). And, This is equal to (C + D) q ( C psi + D phi), divided by (1- phi q)(1- psi q), and so their denominator is equal to 1- q- q squared. And this should be equal to, q divided by 1- q- q squared, which means that C + D, So C + D in the numerator, should be equal to 0. And C psi + D phi, times negative one, is equal to one. So, C psi + D phi = -1. And, we can solve this system of equations. And get that, C=1 over the square root of 5. And, D is equal to negative C, so -1 over square root of 5. So we have found C and D such that, phi of q is equal to C over 1- phi q + D over 1- psi q. So, phi of q is 1 over the square root of 5, times 1 over 1- phi q- 1 over 1 minus psi q. So we have presented the generating function for, the Fibonacci sequence, as the sum of two fractions of the form, so the coefficient times 1 over 1- phi q and 1 over 1- psi q. And these are, generating functions for geometric progressions. This means that, the nth Fibonacci number can be presented as, the sum of the corresponding terms of two geometric progressions. So we continue this equality. So this is 1 over the square root of 5 times 1 + phi q + phi squared q squared + etc.)- 1 over square root of 5 (1 + psi q + psi squared q squared + etc.). So, we recall the Binet formula, which says that the nth Fibonacci number fn is equal to 1 over the square root of 5, Phi to the power n- psi to the power n) where phi and psi are given here. So we recover the Binet formula, by using generating functions. So let me repeat what happened. First we wrote down the functional equation for, Fibonacci generating function. And from this equation, we found the presentation of phi of q, as the ratio of two polynomials. So we represented phi of q as a rational function. Then, we represented our rational function as, the sum of two fractions of the following type. And we have found these coefficients by, solving a system of layer equations. Each of these fractions, is the generating function for a geometric progression, with common ratios phi and psi respectively. So, our generating function for Fibonacci numbers, is equal to the sum of these two generating functions. This means that, the nth term of the Fibonacci sequence, is equal to the sum of the corresponding named nth terms of these geometric progressions, with common ratios phi and psi. And this is exactly the Binet formula. [MUSIC]