Closed-Form Fibonacci Numbers via Generating Functions & Linear Algebra

[00:00:00]Because of its recursive nature, computing the Fibonacci sequence via brute force is computationally expensive. However, the Fibonacci numbers have a simple and beautiful closed form expression written in terms of the golden ratio and the conjugate golden ratio.

[00:00:16]In this video, we are going to derive it from first principles, learning two powerful mathematical techniques along the way, generating functions and value decompositions. First, let's zoom in on the Fibonacci numbers. The zero Fibonacci number F0 is zero.

[00:00:36]The first Fibonacci number F1 is one.

[00:00:39]And by definition, the rest are given by the sum of the two preceding Fibonacci numbers.

[00:00:46]Because of this, they grow insanely fast.

[00:00:51]But that's not the problem. Let's take a look at what happens when we compute the Fibonacci numbers recursively.

[00:00:58]f_sub_0 and f_sub_1 are given. These are our terminating conditions.

[00:01:04]To find f_sub_2, we compute f_sub_1 and f_sub_0.

[00:01:10]To find f_sub_3, we compute f_sub_2 and f_sub_1.

[00:01:15]To find f_sub_4, we compute f_sub_3 and f_sub_2 and so on. When computing the Fibonacci numbers recursively, the number of function calls also grows insanely fast.

[00:01:28]How fast? Let's see. F0 and F_sub_1 require only one call as they are terminating conditions.

[00:01:38]F_sub_2 requires three calls. F_sub_3 requires five. F_sub_4 requires nine. F5 requires 15 and so on. In general, fn requires 2 * fn + one minus one function call. This is a problem in practice.

[00:02:00]How to solve this?

[00:02:02]First attempt finding an explicit formula via generating functions.

[00:02:09]But what are generating functions?

[00:02:12]Suppose that we have a sequence a n which we slap onto a power series as coefficients.

[00:02:18]The resulting expression is called the generating function of a n.

[00:02:23]There are all sorts of potential issues raised by the convergence properties of power series, but we won't deal with them.

[00:02:32]For our purposes, a generating function is a clos line on which we hang up a sequence of numbers for display. As Herbert Wolf phrases it in his book generating functionality which is the book on the subject we are only interested in the combinatorial properties of generating functions.

[00:02:52]Let's see an example. The generating function of the binomial coefficients.

[00:02:58]If we take n / k multiply it by x to the k and sum over k we obtain the polomial 1 + x to the n.

[00:03:09]This is given by the famous Newton's binomial theorem.

[00:03:13]Another example 1 / n factorial whose generating function is our good old friend the exponential function.

[00:03:24]One more example the most important one for our purposes the geometric series.

[00:03:31]If we take q to the n, multiply it by x to the n and sum over n, we obtain the rational function 1 / 1 - q * x.

[00:03:44]Q is called the quotient of the series.

[00:03:48]Yes, I know convergence and whatever, but let's suspend our mathematical precision and go rack and roll with generating functions.

[00:03:57]The generating function we want to study is the Fibonacci generating function defined by f ofx.

[00:04:05]How can we find an explicit formula for fn with the help of f ofx?

[00:04:12]Simple. If the generating functions for the sequences a n and bn are equal, then a n and bn must be equal as well.

[00:04:23]Let's get to it. We start by unwrapping the definition of f ofx. Writing out the terms one by one. f ofx= f0 plus f_sub_1 * x + f_sub_2 * x^2 and so on.

[00:04:45]Let's focus our attention on the third term f_sub_2 * x 2.

[00:04:50]We can use the recursion here and write it as f_sub_0 + f_sub_1 * x^ 2.

[00:04:57]Similarly, we can write the fourth term f_sub_3 * x cub as f_sub_2 + f_sub_1 * x cub.

[00:05:08]We can do this for all subsequent terms.

[00:05:12]For simplicity, let's unwrap the parenthesis and write f ofx in a more suggestive form.

[00:05:25]Now the part f0 * x^2 + f_sub_1 * x cubed and so on can be written as x^2 * f_sub_0 + f_sub_1 * x and so on.

[00:05:42]Similarly, f_sub_1 * x^2 + f_sub_2 * x cub and so on can be written as x * f_sub_1 * x + f_sub_2 * x^ 2 and so on.

[00:05:59]Lucky for us, both power series in the parenthesis equal f ofx where we use the fact that f0 equals to zero.

[00:06:12]Thus, we obtain the functional equation f ofx = f_sub_0 plus f_sub_1x + x * fx + x^2 * fx.

[00:06:27]We can simplify this even further. As f0 equals zero and f_sub_1 = 1, we get that f ofx = x + x * f(x) + x^2 * f(x).

[00:06:46]By arranging all the terms with f ofx on one side of the equation, we arrive at f ofx minus x * fx - x^2 * fx = x.

[00:07:04]One last step. Now we can factor out f ofx and divide both sides by the polomial term 1 - x - x^2 which gives the closed form expression fx = x over 1 - x - x^2.

[00:07:25]We are at the finish line. I'm not going to spell out all the details, but with the magic of partial fraction decomposition, we obtain that f ofx is a linear combination of two familiar terms. The generating functions of geometric series. The quotient of the first term is 1 +<unk> 5 / 2 otherwise known as the golden ratio. The quotient of the second term is 1 minus<unk> 5 / 2, otherwise known as the conjugate golden ratio.

[00:07:58]Note that the golden ratio minus the conjugate golden ratio is 1 / the square root of 5.

[00:08:06]Now we can interchange the operations with the infinite sum to arrive at our desired formula.

[00:08:13]Can you recall the most useful property of generating functions?

[00:08:17]two generating functions are equal if and only if the underlying sequences are the same. Now you can see where we are going with this.

[00:08:27]With the help of generating functions, we obtained the welldeserved result, the non-recursive formula for Fibonacci numbers.

[00:08:36]Even though generating functions are powerful and fun to use, I have to admit we did a bunch of sketchy stuff to get here. I'm a mathematical analyst at heart and I can't just overlook issues like rearranging the terms of an infinite sum or interchanging it with operations.

[00:08:54]So what's the solution?

[00:08:57]I'll show you another way. This time with linear algebra.

[00:09:02]Let's talk about the Fibonacci matrix.

[00:09:06]Let F be a simple 2x2 matrix. The first row is one one while the second row is one zero.

[00:09:16]If we square F, we obtain the matrix 2 1 and 1 1.

[00:09:24]The cube of F is 3 2 and 2 1.

[00:09:31]Let's see a couple more powers. Here's F to the 4 and here's F to the 5.

[00:09:41]Do you see the general pattern? The nth power of f contains the Fibonacci numbers f n + one fn and fn fn minus one.

[00:09:56]Here's a property of f that hints at what we are about to do. F is invariant to matrix transposition. That is it is symmetric.

[00:10:08]You guessed right. We are going to apply the spectra theorem for real symmetric matrices otherwise known as the value de composition theorem. It states that if a is a real and symmetric square matrix then there exists a p such that a equ= p * diagonal matrix time the inverse of p where the diagonal matrix contains the values of a.

[00:10:35]This is an extremely powerful theorem which we are applying to a simple problem. In mathematical terms, we are about to shoot a bird with a cannon.

[00:10:45]Let's call this diagonal matrix D to simplify the towering computations that we are about to do.

[00:10:52]Now let's square our matrix A using the value decomposition.

[00:10:58]As matrix multiplication is associative, we can eliminate the ps in the middle obtaining that a²= p * d² * the inverse of p.

[00:11:14]Continuing this process, we get that a to the n = p * d to the n * the inverse of p.

[00:11:25]Fortunately for us, computing the nth power of a diagonal matrix is simple. We just have to raise the diagonal elements to the n.

[00:11:36]Now recall that the nth power of the Fibonacci matrix is given by the Fibonacci numbers.

[00:11:43]Using the value decomposition of f, we'll eventually arrive at the nonrecursive formula for the Fibonacci numbers.

[00:11:52]Let's get to work. To compute the igen values of f, we have to solve a quadratic equation given by the determinant of f - x * the identity matrix.

[00:12:04]This determinant is given by x^2 - x - 1.

[00:12:11]By plugging the coefficients into the quadratic solution formula, we see that the roots of x^2 - x -1 are given by the golden ratio and the conjugate golden ratio.

[00:12:26]After crunching some numbers and matrices, we obtain the value decomposition of f by raising it to the n's power. We can already see the formula emerging.

[00:12:40]After making some room on the screen for the incoming computation, we begin by unwrapping the first matrix product.

[00:12:48]Now we can easily compute the top left element of the final product. We don't care about the others.

[00:12:56]By comparing the result of our computation with the nth power of f, we get the desired formula.

[00:13:03]Here it is once more in its full glory.

[00:13:08]Even though the non-recursive formula directly computes the nth Fibonacci number, it involves working with floats which introduces numerical issues.

[00:13:18]In practice, we are better off computing the powers of f.

[00:13:23]However, if you think about it for a second, this is quite a remarkable formula.

[00:13:29]First, it establishes a precise relation between the golden ratio and the Fibonacci numbers.

[00:13:36]Second, even though the golden ratio and its conjugate are irrational numbers, the result is an integer.

[00:13:44]In addition, it teaches us a valuable lesson on power series and symmetric matrices. When calculus, algebra, and combinatorics intersect, powerful tools emerge.

[00:13:58]Thanks for watching and see you in the next video. Cheers.