1 00:00:00,380 --> 00:00:04,881 I want to be able to write down unending sequences of numbers. 2 00:00:04,881 --> 00:00:11,063 [SOUND]. 3 00:00:11,063 --> 00:00:15,990 If I want to give you a sequence of numbers to analyze, how do I do that? 4 00:00:15,990 --> 00:00:21,200 It's not enough for me just to list off a finite number of terms. 5 00:00:21,200 --> 00:00:25,400 I somehow have to provide you with all of the terms at once. 6 00:00:25,400 --> 00:00:27,970 Well, one thing I could do is give you a formula. 7 00:00:27,970 --> 00:00:32,000 Like a sub N equals n squared. 8 00:00:32,000 --> 00:00:36,327 And this formula would define the sequence of perfect squares. 9 00:00:36,327 --> 00:00:46,122 If I star with index 1, the sequence starts 1, 4, 9, 16, 25, and so on. 10 00:00:46,122 --> 00:00:50,440 I can just give you the sequence by giving you this formula. 11 00:00:50,440 --> 00:00:56,220 Sometimes it can be quite hard to give a formula for the nth term of the sequence. 12 00:00:56,220 --> 00:01:01,617 We could instead think recursively. What I mean, is that I could give 13 00:01:01,617 --> 00:01:06,840 you a formula that references previous terms in the sequence. 14 00:01:06,840 --> 00:01:12,696 For example, we might begin a sequence with a 0 term that I'll define to 15 00:01:12,696 --> 00:01:18,820 be equal to 0, and an F sub 1 term, which I'll define to be equal to 1. 16 00:01:18,820 --> 00:01:24,930 And then I'll define future terms by referring to past terms. 17 00:01:24,930 --> 00:01:27,286 So, in this example, 18 00:01:27,286 --> 00:01:33,500 F sub n will be defined as F sub n minus 1 plus F sub n minus 2. 19 00:01:33,500 --> 00:01:34,860 That's just an example. 20 00:01:34,860 --> 00:01:39,470 Let's see how this works. Let's say, I want to compute F sub 2. 21 00:01:39,470 --> 00:01:40,220 Well how do I do that? 22 00:01:41,230 --> 00:01:45,190 Well, I can use this formula but replace with n with 2. 23 00:01:45,190 --> 00:01:52,295 And in that case, I get F sub 2 is F sub two minus 1 plus F sub 24 00:01:52,295 --> 00:01:57,290 2 minus 2. But F sub 2 minus 1 is F sub 1. 25 00:01:57,290 --> 00:02:00,130 And F sub 2 minus 2 is F sub 0. 26 00:02:00,130 --> 00:02:02,740 And what's F sub 1? 27 00:02:02,740 --> 00:02:05,360 Well, I know these two facts, I know that F sub 1 is 1. 28 00:02:05,360 --> 00:02:12,310 And I know that F sub 0 is 0. And consequently F sub 2 is 1. 29 00:02:12,310 --> 00:02:16,896 And we could keep going. Let's compute F sub 3. 30 00:02:18,840 --> 00:02:23,988 Replacing n with 3, I find that F sub 3 is F 31 00:02:23,988 --> 00:02:29,345 sub 3 minus 1 plus F sub 3 minus 2. But F sub 32 00:02:29,345 --> 00:02:35,370 3 minus 1 is F sub 2. And F sub 3 minus 2 is F sub 1. 33 00:02:35,370 --> 00:02:39,570 Now I just computed F sub 2 a minute ago, F sub 2 is 1. 34 00:02:39,570 --> 00:02:44,106 So that tells me that F sub 3, which is F sub 35 00:02:44,106 --> 00:02:50,550 2 plus F sub 1, is 1 plus F sub 1 is 1, and 1 plus 1 is 2. 36 00:02:50,550 --> 00:02:56,210 So F sub 3 is 2. And we can keep going. 37 00:02:56,210 --> 00:03:01,782 Well, let's compute F sub 4. So, if I want to compute F sub 4, I 38 00:03:01,782 --> 00:03:09,152 replace n with 4 and I find that F sub 4 is F sub 4 minus 1 plus F sub 39 00:03:09,152 --> 00:03:13,606 4 minus 2. 4 minus 1 is 3. 40 00:03:14,720 --> 00:03:17,100 And 4 minus 2 is 2. 41 00:03:17,100 --> 00:03:19,885 So F sub 4 is F sub 3 plus F sub 2. 42 00:03:19,885 --> 00:03:22,920 Alright, each term is the sum of the previous two terms. 43 00:03:24,010 --> 00:03:24,830 Now, what's F sub 3? 44 00:03:24,830 --> 00:03:28,500 Well, I just computed F sub 3 a moment ago. 45 00:03:28,500 --> 00:03:33,410 F sub 3 was F sub 2 plus F sub 1, which was 2. 46 00:03:33,410 --> 00:03:34,598 So F sub 47 00:03:34,598 --> 00:03:36,190 3 is 2. 48 00:03:36,190 --> 00:03:41,580 And I computed F sub 2 a couple moments ago, and I found that it was 1. 49 00:03:41,580 --> 00:03:46,950 So F sub 4 is 3. We're maybe beginning to see a pattern. 50 00:03:46,950 --> 00:03:51,870 1, 2, 3, but that pattern does not continue. 51 00:03:51,870 --> 00:03:53,070 Let's check. 52 00:03:53,070 --> 00:03:59,664 F sub 5 is F sub 4 plus F sub 3. F sub 4, 53 00:03:59,664 --> 00:04:03,440 I just computed was 3, and F sub 3, I 54 00:04:03,440 --> 00:04:07,150 computed a little while ago to be 2. 55 00:04:07,150 --> 00:04:10,960 And 3 plus 2 is 5. So F sub 5 is 5. 56 00:04:10,960 --> 00:04:19,570 What's F sub 6? Well, F sub 6 is F sub 5 plus F sub 4. 57 00:04:19,570 --> 00:04:24,682 It just computed F sub 5 and that was 5 and F 58 00:04:24,682 --> 00:04:31,280 sub 4 was 3, and 5 plus 3 is 8. So F sub 6 is 8. 59 00:04:31,280 --> 00:04:34,130 This sequence has a name. 60 00:04:34,130 --> 00:04:38,100 So this particular example is called the Fibonacci Sequence. 61 00:04:38,100 --> 00:04:43,680 It starts 0, 1, and then each term is the sum of the previous two. 62 00:04:43,680 --> 00:04:50,093 So the next term is 1, 0 plus 1, the next term is 2, the next 63 00:04:50,093 --> 00:04:56,800 term is 3, the next term is 5 The next term is 8, and so on. 64 00:04:56,800 --> 00:04:59,390 This isn't to say that the only way to talk 65 00:04:59,390 --> 00:05:04,140 about the Fibonacci sequence is by giving a recursive formula. 66 00:05:04,140 --> 00:05:07,676 We're going to see later on in this course, that it's possible 67 00:05:07,676 --> 00:05:12,360 to write down an explicit formula for the nth Fibonacci number. 68 00:05:12,360 --> 00:05:15,220 But that's not really the main point here. The, the main point is that, 69 00:05:15,220 --> 00:05:17,196 when you're thinking about sequences or you 70 00:05:17,196 --> 00:05:19,910 want to provide someone else with a sequence. 71 00:05:19,910 --> 00:05:23,890 You don't have to give a formula just in terms of the index. 72 00:05:23,890 --> 00:05:28,960 Your formula for the nth term can do more than just refer to n. 73 00:05:28,960 --> 00:05:34,715 Indeed, a formula like this one can refer to previous terms in the sequence. 74 00:05:34,715 --> 00:05:44,715 [NOISE]