1 00:00:00,180 --> 00:00:01,381 Fibonacci. 2 00:00:01,381 --> 00:00:07,380 [MUSIC] 3 00:00:07,380 --> 00:00:10,520 Long time ago, we met the Fibonacci numbers. 4 00:00:10,520 --> 00:00:14,350 So that's a sequence that goes, we'll start with 0, and then 5 00:00:14,350 --> 00:00:17,820 1, and then each subsequent term is the sum of the previous two. 6 00:00:17,820 --> 00:00:19,320 So 0 plus 1, is 1. 7 00:00:19,320 --> 00:00:28,610 1 plus 1 is 2, 1 plus 2 is 3, 2 plus 3 is 5, 3 plus 5 is 8, 5 8 00:00:28,610 --> 00:00:32,490 plus 8 is 13, and then it keeps on going. I'd like 9 00:00:32,490 --> 00:00:37,470 a formula for the Fibonacci numbers. So in this case a sub 0 10 00:00:37,470 --> 00:00:42,830 is 0, a sub 1 is 1. A sub 2 is 1, 11 00:00:42,830 --> 00:00:47,840 a sub 3, 0, 1, 2, 3, that's 2. A 12 00:00:47,840 --> 00:00:52,830 sub 4 is 3 and a sub 5, at 13 00:00:52,830 --> 00:00:57,770 0, 1, 2, 3, 4, 5, a sub 5 i s 5. And what we're looking for is 14 00:00:57,770 --> 00:01:01,770 a formula for the nth terms of term of n, right? 15 00:01:01,770 --> 00:01:03,970 I want to know that a sub n. 16 00:01:03,970 --> 00:01:08,635 Is equal to something, but I want the something to involve n's. 17 00:01:08,635 --> 00:01:12,470 Or maybe you're thinking don't we already have a formula? 18 00:01:12,470 --> 00:01:16,430 You're right, I mean there's this formula, a sub n is 19 00:01:16,430 --> 00:01:19,040 a sub in minus 1 plus a sub n minus 2. 20 00:01:19,040 --> 00:01:23,120 This is the formula that we use to define the Fibonacci 21 00:01:23,120 --> 00:01:27,360 sequence, right. Each term is the sum of the previous two. 22 00:01:27,360 --> 00:01:29,660 The trouble has it, this isn't a very useful formula, right. 23 00:01:29,660 --> 00:01:33,200 To calculate the thousandth term using this formula, I'd 24 00:01:33,200 --> 00:01:37,620 have to calculate the 999th term and the 998th term. 25 00:01:37,620 --> 00:01:39,390 I'm really looking for some kind of formula 26 00:01:39,390 --> 00:01:41,610 that just involves you know, the usual kinds 27 00:01:41,610 --> 00:01:44,120 of math functions I'm used to, maybe powers 28 00:01:44,120 --> 00:01:47,170 multiplying, adding, subtracting, dividing, that sort of thing. 29 00:01:47,170 --> 00:01:48,170 And the number 30 00:01:48,170 --> 00:01:48,760 n, right? 31 00:01:48,760 --> 00:01:51,220 I don't want a formula that depends on my 32 00:01:51,220 --> 00:01:54,500 calculating all the previous terms to calculate the next term. 33 00:01:54,500 --> 00:01:55,750 Is that even possible? 34 00:01:55,750 --> 00:01:59,180 I mean how am I going to go about finding such a formula. 35 00:01:59,180 --> 00:02:00,300 Here's the trick. 36 00:02:00,300 --> 00:02:06,964 The trick is to assemble the Fibonacci sequence into a power series. 37 00:02:06,964 --> 00:02:10,770 what I mean we should think about this function, function f 38 00:02:10,770 --> 00:02:13,528 of x and it will be the sum, n goes from 39 00:02:13,528 --> 00:02:16,940 0 to infinite of a sub n x to the 40 00:02:16,940 --> 00:02:20,850 n but here these a sub n's are the Fibonacci numbers. 41 00:02:20,850 --> 00:02:23,840 So, a sub 0 is 0, I'm not going to write that 42 00:02:23,840 --> 00:02:27,660 but a sub 1, the first Fibonacci is 1, so it's x. 43 00:02:27,660 --> 00:02:33,100 A sub 2, nice Fibonacci number is also 1, so plus x squared, a sub 3, the 44 00:02:33,100 --> 00:02:38,820 third Fibonacci number is 2. So 2x cubed, next Fibonacci 45 00:02:38,820 --> 00:02:43,590 number is 3, so 3x to the fourth, the next Fibonacci 46 00:02:43,590 --> 00:02:47,030 is 5, so 5x to the fifth then I'll keep on going. 47 00:02:47,030 --> 00:02:49,990 Now I can set up an equation that f satisfies. 48 00:02:49,990 --> 00:02:50,800 Well, here's how it goes. 49 00:02:50,800 --> 00:02:57,800 I'm going to multiply f of x by x, so x times f of x is what, 50 00:02:57,800 --> 00:03:04,260 well I multiply this by x, the x gives me an x squared, the x squared 51 00:03:04,260 --> 00:03:10,500 gives me an x cubed, the 2x cubed gives me a 2x to the 4th. 52 00:03:10,500 --> 00:03:14,350 The 3x to the 4th gives me a 3x to the 5th and we keep on going. 53 00:03:15,440 --> 00:03:20,370 And then I'm going to multiply this by x squared. 54 00:03:20,370 --> 00:03:24,110 So that's x squared times f of x, well then x 55 00:03:24,110 --> 00:03:29,400 times x squared gives me an x cubed, x squared times 56 00:03:29,400 --> 00:03:31,300 x squared gives me an x to the fourth. 57 00:03:32,840 --> 00:03:38,740 2x cubed times x squared gives me a 2x to the fifth, and I'm going to keep on going. 58 00:03:38,740 --> 00:03:40,720 Now, I'll do some subtraction. 59 00:03:40,720 --> 00:03:46,970 So I've got f of x minus x times f of x minus x squared times f of x. 60 00:03:46,970 --> 00:03:47,355 [UNKNOWN] 61 00:03:47,355 --> 00:03:50,160 And that's equal to well, the x survives. 62 00:03:50,160 --> 00:03:53,041 X squared minus x squared, that cancels, 2x 63 00:03:53,041 --> 00:03:56,615 cubed minus x cube, minus x cube, that cancels. 64 00:03:56,615 --> 00:04:00,895 3x to the fourth, minus 2x to the fourth, minus x to the fourth, that cancels. 65 00:04:00,895 --> 00:04:05,650 5x to the fifth, minus 3x to the fifth minus 2x to, that cancels. 66 00:04:05,650 --> 00:04:09,265 Well, everything cancels, and that's not coincidence, right? 67 00:04:09,265 --> 00:04:12,810 The defining feature of the sequence of numbers, the coefficient 68 00:04:12,810 --> 00:04:18,090 a sub n, in the Fibonacci's sequence, so each number is the sum of previous 2. 69 00:04:18,090 --> 00:04:22,252 5 is 3 plus 2, the next number over here is what? 70 00:04:22,252 --> 00:04:23,430 It's 8. 71 00:04:23,430 --> 00:04:26,300 And 8 is 5 plus 3, right? 72 00:04:26,300 --> 00:04:29,130 Because each term in the Fibonacci sequence is the 73 00:04:29,130 --> 00:04:32,090 sum of the previous two, I've rigged it so that 74 00:04:32,090 --> 00:04:37,510 f of x minus x f of x minus x squared f of x is just equal to x. 75 00:04:37,510 --> 00:04:37,910 What does that 76 00:04:37,910 --> 00:04:39,170 even mean? 77 00:04:39,170 --> 00:04:43,230 So totally ignoring issues of convergence, you know I really. 78 00:04:43,230 --> 00:04:48,390 Just thinking about this entirely formally, what I've got is that f of x 79 00:04:48,390 --> 00:04:55,120 minus x times f of x, minus x squared times f of x is just x. 80 00:04:55,120 --> 00:04:57,200 Where f is the function, given my 81 00:04:57,200 --> 00:05:00,410 power series, use coefficients, of the Fibanocci numbers. 82 00:05:00,410 --> 00:05:02,930 Now, I'll factor out an f of x. 83 00:05:02,930 --> 00:05:09,810 F of x times 1 minus x minus x squared is equal to x. 84 00:05:09,810 --> 00:05:10,090 [LAUGH] 85 00:05:10,090 --> 00:05:15,190 Now divide both sides by this. So, f of x is x 86 00:05:15,190 --> 00:05:21,200 over 1 minus x minus x squared. Okay, okay, here's the plan. 87 00:05:21,200 --> 00:05:24,600 I'm going to find another power series for that rational function. 88 00:05:24,600 --> 00:05:28,750 And then I'm going to equate the two power series, the new power series that I 89 00:05:28,750 --> 00:05:30,590 found, and the old power series, the 90 00:05:30,590 --> 00:05:33,540 coefficients of which are just the Fibonacci numbers. 91 00:05:33,540 --> 00:05:35,340 It turns out that when those two power 92 00:05:35,340 --> 00:05:38,160 series are equal, their coefficients are equal. 93 00:05:38,160 --> 00:05:41,290 And that way, I'll get a formula for the Fibonacci numbers. 94 00:05:41,290 --> 00:05:43,390 Now I'm going to rewrite this function, in I think 95 00:05:43,390 --> 00:05:46,760 what initially will seem like a much more complicated way. 96 00:05:46,760 --> 00:05:49,770 first I'm going to define this other number, it's 97 00:05:49,770 --> 00:05:52,450 actually traditionally called phi, that's the golden ratio. 98 00:05:52,450 --> 00:05:57,062 Phi is 1 plus the square root of 5 over 2. 99 00:05:57,062 --> 00:06:01,440 All right, so that's the number phi, and I'm going to use phi to rewrite 100 00:06:01,440 --> 00:06:02,640 this function f. 101 00:06:02,640 --> 00:06:06,660 So it turns out that after quite a lengthy calculation, you convince yourself. 102 00:06:06,660 --> 00:06:14,270 That this is 1 over the square root of 5, divided by 1 minus 103 00:06:14,270 --> 00:06:20,110 x times phi, plus negative 1 over the square root of 5 104 00:06:20,110 --> 00:06:25,880 divided by 1 minus. X times not phi but 1 minus phi. 105 00:06:27,770 --> 00:06:29,440 How is that better? 106 00:06:29,440 --> 00:06:31,960 It looks like I just made a total mess of things. 107 00:06:31,960 --> 00:06:36,540 Well, the trick now is that I can write these each is power series. 108 00:06:36,540 --> 00:06:36,710 [LAUGH] 109 00:06:36,710 --> 00:06:41,070 Here we go. This is 1 over square root of 5. 110 00:06:41,070 --> 00:06:47,330 Times 1 over 1 minus x times phi plus 111 00:06:47,330 --> 00:06:54,440 negative 1 over the square root of 5 times 1 over 1 minus x times 1 minus phi. 112 00:06:55,960 --> 00:06:58,740 But I have a power series for 1 over 1 minus something. 113 00:06:58,740 --> 00:06:58,950 Right? 114 00:06:58,950 --> 00:07:02,204 So this is 1 over the square root of 5. 115 00:07:04,750 --> 00:07:10,330 Times the sum n goes from 0 to infinity of 116 00:07:10,330 --> 00:07:16,160 x times phi to the nth power plus negative 1 117 00:07:16,160 --> 00:07:22,550 over the square root of 5 times the sum n goes from 0 to infinity. 118 00:07:22,550 --> 00:07:29,940 Of x times 1 minus phi to the nth power. And I'll write this as a single series. 119 00:07:29,940 --> 00:07:36,520 Okay, so this is 1 over the square root of 5 times the 120 00:07:36,520 --> 00:07:43,210 sum, n goes from 0 to infinity, I'll write this as phi to the n times x to the n. 121 00:07:43,210 --> 00:07:48,460 Plus negative 1 over the square root of 5 times the sum n goes 122 00:07:48,460 --> 00:07:53,750 from 0 to infinity of 1 minus phi to the n times x to the n. 123 00:07:55,000 --> 00:07:55,245 And 124 00:07:55,245 --> 00:07:56,110 [UNKNOWN] 125 00:07:56,110 --> 00:07:58,700 I'm going to write this just as a single power series, I'm going to 126 00:07:58,700 --> 00:08:04,140 collect together the coefficients here in front of x to the n. 127 00:08:04,140 --> 00:08:08,900 So this is the sum, n goes from 0 to 128 00:08:08,900 --> 00:08:14,050 infinity of 1 over the squared root of 5 times phi to the n, 129 00:08:15,590 --> 00:08:21,440 minus 1 over the square root of 5 times 1 minus phi to the n. 130 00:08:21,440 --> 00:08:25,940 All of this. Times x to the n. 131 00:08:25,940 --> 00:08:27,660 I can simplify that a bit. 132 00:08:27,660 --> 00:08:33,220 Yeah, I could write this as the sum, n goes from 0 to infinity. 133 00:08:33,220 --> 00:08:38,690 Of phi to the n minus 1 minus phi to the n over the square 134 00:08:38,690 --> 00:08:44,010 root of 5, times x to the nth power. And here's the punchline. 135 00:08:44,010 --> 00:08:46,810 Well, admittedly we haven't been concerned about conversions 136 00:08:46,810 --> 00:08:49,150 at all, but at least remember where this came from. 137 00:08:49,150 --> 00:08:51,200 I mean we derived this through a series 138 00:08:51,200 --> 00:08:55,930 of perhaps unjustified operations but we started with just 139 00:08:55,930 --> 00:08:58,190 this power series where these coefficients were the 140 00:08:58,190 --> 00:09:01,689 Fibonacci numbers, and I've got a new power series. 141 00:09:03,000 --> 00:09:05,350 And the upshot of what I'm hoping here is that these 142 00:09:05,350 --> 00:09:09,060 two power series are equal then their coefficients must be equal. 143 00:09:09,060 --> 00:09:09,175 And 144 00:09:09,175 --> 00:09:09,900 [LAUGH] 145 00:09:09,900 --> 00:09:14,660 it happens that this, is a formula for this. 146 00:09:14,660 --> 00:09:17,910 This is a formula for the end Fibonacci number. 147 00:09:17,910 --> 00:09:21,840 For real that is a formula for the Fibonacci numbers. 148 00:09:21,840 --> 00:09:23,510 Well let's try it I mean here's the 149 00:09:23,510 --> 00:09:27,320 100th Fibonacci number it's this pretty big number 150 00:09:27,320 --> 00:09:31,990 so the idea here is that instead of trying to calculate a sub 100 by hand. 151 00:09:31,990 --> 00:09:35,190 I'm just going to plug in n equals 100 and compute 152 00:09:35,190 --> 00:09:36,700 this coefficient. 153 00:09:36,700 --> 00:09:39,470 Let's estimate that without using a calculator. 154 00:09:39,470 --> 00:09:44,075 Well, instead of writing 1.6, that's about what phi is, let's write 16 10ths. 155 00:09:45,300 --> 00:09:45,769 [LAUGH], 156 00:09:45,769 --> 00:09:50,660 instead of writing 16 10ths, let's approximate phi by 16 10ths written this 157 00:09:50,660 --> 00:09:54,530 way 2 to the fourth or 16 so 2 to the fourth over 10. 158 00:09:54,530 --> 00:09:56,580 But if I write it that way it kind of makes it a little bit 159 00:09:56,580 --> 00:10:01,670 easier to do the estimation because 2 to the 4th over 10 to the 100th power. 160 00:10:01,670 --> 00:10:06,890 Well that's 2 to the 4 100th over 10 to the 100th but now 161 00:10:06,890 --> 00:10:11,070 2 to the 4 100th I can write that as 2 to the 10th to 162 00:10:11,070 --> 00:10:12,450 the 40th. 163 00:10:12,450 --> 00:10:16,740 And that's a smart move, because two and the 10th, I happen to know, is one 164 00:10:16,740 --> 00:10:21,680 1024, so 2 to the t10th is practically 10 to the 3rd, it's about a thousand. 165 00:10:22,940 --> 00:10:27,960 But 10 to the 3rd to the 40th, well that's 10 to the 100 and 20th. 166 00:10:27,960 --> 00:10:28,974 So all together 167 00:10:28,974 --> 00:10:29,520 [LAUGH], 168 00:10:29,520 --> 00:10:32,718 the 100th Fibonacci number is in about 10 to 169 00:10:32,718 --> 00:10:36,540 the 120th power divided by 10 to the 100th power, 170 00:10:36,540 --> 00:10:36,930 [LAUGH] 171 00:10:36,930 --> 00:10:39,504 all together then, I can guess that the 172 00:10:39,504 --> 00:10:43,650 100 Fibonacci number is about 10 to the 20th. 173 00:10:43,650 --> 00:10:46,310 Is that even close to being accurate. 174 00:10:46,310 --> 00:10:49,080 Well, the actual retail value if you remember, 175 00:10:49,080 --> 00:10:52,540 here it is, here's the 100th Fibonacci number. 176 00:10:52,540 --> 00:10:55,465 And although it's kind of a pain to count the digits, 177 00:10:55,465 --> 00:11:00,780 that 100 Fibonacci number is approximately 3.54 times 10 to the 20th. 178 00:11:00,780 --> 00:11:02,250 Rock on Rockstar. 179 00:11:02,250 --> 00:11:07,100 We've estimated the 100 Fibonacci's number, all with nothing but our wits. 180 00:11:07,100 --> 00:11:11,970 Now this technique of analysing a sequence by building the associated power series. 181 00:11:11,970 --> 00:11:14,710 That technique has a name. And this sort of trick. 182 00:11:14,710 --> 00:11:19,570 Where I analyse a sequence of numbers. In this case, the Fibonacci sequence. 183 00:11:19,570 --> 00:11:22,968 By building a power series and then playing around with it like this 184 00:11:22,968 --> 00:11:23,652 [INAUDIBLE] 185 00:11:23,652 --> 00:11:26,720 formal way. This is called, generating functions. 186 00:11:26,720 --> 00:11:31,330 One reason why this is a powerful technique, is that it lets you carry 187 00:11:31,330 --> 00:11:36,200 a problem from one area of mathematics into a whole another area of mathematics. 188 00:11:36,200 --> 00:11:38,790 We started with a very combinatorial feeling problem, 189 00:11:38,790 --> 00:11:41,910 a discrete problem, a problem about sequences and 190 00:11:41,910 --> 00:11:44,500 by applying this method of generating functions we 191 00:11:44,500 --> 00:11:48,200 transported that problem into the realm of calculus. 192 00:11:48,200 --> 00:11:48,680 And I think 193 00:11:48,680 --> 00:11:52,170 this shows that mathematics at its deepest levels. 194 00:11:52,170 --> 00:11:54,630 Is not a collection of disconnected subjects. 195 00:11:54,630 --> 00:11:58,975 Mathematics is a single, unified whole, and all of these different areas of 196 00:11:58,975 --> 00:12:08,975 mathematics are connected together.