1 00:00:00,000 --> 00:00:03,166 When induction isn't 
enough. So sometimes 2 00:00:03,166 --> 00:00:05,700 we have a problem 
where the statement 3 00:00:05,700 --> 00:00:07,766 feels like it should be 
proved by induction, just 4 00:00:07,766 --> 00:00:11,766 simple ordinary induction on the statement itself, 5 00:00:11,766 --> 00:00:15,100 but sometimes it's 
maybe not so obvious 6 00:00:15,100 --> 00:00:17,066 how to do this. 7 00:00:17,066 --> 00:00:18,266 8 00:00:18,266 --> 00:00:19,833 So it turns 
out… 9 00:00:19,833 --> 00:00:21,766 maybe a little bit 
of a spoiler here 10 00:00:21,766 --> 00:00:24,633 it turns out that weak induction, or the 
Principle of Mathematical Induction 11 00:00:24,633 --> 00:00:27,000 and strong induction, which 
we'll see on the next slide, 12 00:00:27,000 --> 00:00:30,900 it turns out they are equivalent. You can 
actually prove that they imply each other. 13 00:00:30,900 --> 00:00:33,100 This proof is 
not easy - well 14 00:00:33,100 --> 00:00:36,400 one direction is easy the other direction 
is actually a little bit tricky to word, 15 00:00:36,400 --> 00:00:37,400 16 00:00:37,400 --> 00:00:41,466 but it does emphasize that all things 
could be proved with weak induction 17 00:00:41,466 --> 00:00:42,733 18 00:00:42,733 --> 00:00:45,533 but just the statement that you 
have to prove is actually trickier. 19 00:00:45,533 --> 00:00:46,666 20 00:00:46,666 --> 00:00:50,266 In this case, anyways all that meta 
aside, let's look at this example. 21 00:00:50,266 --> 00:00:52,866 So let x n be a sequence defined by x1 is 4, 22 00:00:52,866 --> 00:00:56,633 x2 is 68, and xm is defined recursively as 23 00:00:56,633 --> 00:01:00,200 2 times x m minus 1 plus 
15 times x m minus 2, 24 00:01:00,200 --> 00:01:03,300 for all m greater than 
or equal to 3, okay? 25 00:01:03,300 --> 00:01:05,566 So this is what you call 
a recursive definition, or 26 00:01:05,566 --> 00:01:07,733 recursive statement, 
all of these things. 27 00:01:07,733 --> 00:01:10,966 Recursion statement, all of these things mean the same thing. 28 00:01:10,966 --> 00:01:13,466 x m is defined in terms 
of previous terms. 29 00:01:13,466 --> 00:01:16,466 So if I wanted to determine 
x3, I would plug in 30 00:01:16,466 --> 00:01:19,300 I would plug in 3 into here, 
which would give me 2x2, 31 00:01:19,300 --> 00:01:23,233 so it'll be 2 times 68, 
plus 15 times x sub 32 00:01:23,233 --> 00:01:27,500 3 minus 1, so it's x sub 1, that's 4 
so 15 times 4 which would be 60 33 00:01:27,500 --> 00:01:29,900 and add the two together 
and get the number. 34 00:01:29,900 --> 00:01:31,533 35 00:01:31,533 --> 00:01:34,066 What are we going to prove? We're 
going to prove here that x n is equal to 36 00:01:34,066 --> 00:01:39,300 2 times minus 3 to the n, plus 10, 
times 5 to the power of n minus 1. 37 00:01:39,300 --> 00:01:41,300 And we're going to try to 
do this by induction, okay? 38 00:01:41,300 --> 00:01:43,300 the base case 
for n equals 1, 39 00:01:43,300 --> 00:01:45,766 we plug it in and we 
see that it works. 40 00:01:45,766 --> 00:01:51,300 x1 is 4, 4 is the same as 
2 times minus 3 plus 10. 41 00:01:51,300 --> 00:01:53,166 And that's 
the formula. 42 00:01:53,166 --> 00:01:57,600 The inductive hypothesis, we're going 
to assume that x k is equal to this 43 00:01:57,600 --> 00:01:59,300 expression 44 00:01:59,300 --> 00:02:02,966 and we're going to assume this is 
true for some k in the natural numbers. 45 00:02:02,966 --> 00:02:04,133 46 00:02:04,133 --> 00:02:07,066 Now for k plus 1, well what 
do we do? Well okay 47 00:02:07,066 --> 00:02:09,500 we have 
x k plus 1... 48 00:02:09,500 --> 00:02:11,600 and now... 49 00:02:11,600 --> 00:02:15,300 we have a couple of problems here. 
We either have that k plus 1 is 2, 50 00:02:15,300 --> 00:02:17,900 right, because again 
all we know is that 51 00:02:17,900 --> 00:02:22,166 k is a natural number 
so k plus 1 is at least 2, 52 00:02:22,166 --> 00:02:25,966 if k plus 1 is 2, then we'd 
have to do another case. 53 00:02:25,966 --> 00:02:29,766 So we might need multiple base 
cases, it's something to think about. 54 00:02:29,766 --> 00:02:32,266 But let's just assume that we could prove the 55 00:02:32,266 --> 00:02:36,700 k equals 1 case… sorry the 
k plus 1 equals 2 case. 56 00:02:36,700 --> 00:02:39,300 So let's assume that we can 
prove that P2 is true as well. 57 00:02:39,300 --> 00:02:39,733 58 00:02:39,733 --> 00:02:43,633 So take that for granted so that let’s assume that k plus 1 is at least 3. 59 00:02:43,633 --> 00:02:46,400 We can 
use the 60 00:02:46,400 --> 00:02:47,700 61 00:02:47,700 --> 00:02:51,000 recursion statement, 
the recursive relation 62 00:02:51,000 --> 00:02:54,333 between x k plus 1 
and its previous terms. 63 00:02:54,333 --> 00:02:56,300 So let's just suppose 
that this is true, 64 00:02:56,300 --> 00:02:59,733 and even if this was true we 
can substitute x k for this value, 65 00:02:59,733 --> 00:03:03,833 and we can expand, but the problem 
is we still have this x k minus 1 term. 66 00:03:03,833 --> 00:03:04,700 67 00:03:04,700 --> 00:03:08,000 And what's happening is that 
our induction hypothesis, or 68 00:03:08,000 --> 00:03:10,133 inductive hypothesis 
is too weak. 69 00:03:10,133 --> 00:03:13,366 It's not strong enough to give 
us the result that we want. 70 00:03:13,366 --> 00:03:15,933 So in order to do 
this, we need… 71 00:03:15,933 --> 00:03:18,800 well use one or two ways. 
One, we can reword 72 00:03:18,800 --> 00:03:21,966 the statement that we're 
trying to prove, that's harder, 73 00:03:21,966 --> 00:03:24,566 or the easier way is to use 
something called strong induction. 74 00:03:24,566 --> 00:03:28,366 So that's what we're going to see now. 
The Principle of Strong Induction. 75 00:03:28,366 --> 00:03:31,066 Again, this is an axiom. As I 
said this is equivalent to the 76 00:03:31,066 --> 00:03:33,166 Principle of Mathematical Induction. 77 00:03:33,166 --> 00:03:35,300 It's not so easy to prove, 
but you can do so. 78 00:03:35,300 --> 00:03:37,300 It's also equivalent to the Well 
Ordering Principle which we 79 00:03:37,300 --> 00:03:39,300 saw last week in 
last week's video. 80 00:03:39,300 --> 00:03:42,766 That's an axiom I like a lot, 
I think it's pretty interesting 81 00:03:42,766 --> 00:03:45,800 and has a lot of cool consequences. 
Same as induction, 82 00:03:45,800 --> 00:03:47,200 83 00:03:47,200 --> 00:03:50,000 but it's worded in 
a very easy way. 84 00:03:50,000 --> 00:03:52,566 Anyways the Principle of Strong Induction. So if 85 00:03:52,566 --> 00:03:55,400 or a sequence of statements P1, P2, 86 00:03:55,400 --> 00:03:57,466 and so on and so forth, 
we have the following: 87 00:03:57,466 --> 00:04:00,466 that P1 all the way 
up to P b are true 88 00:04:00,466 --> 00:04:02,333 89 00:04:02,333 --> 00:04:03,966 (“are” true? “Is” true? 90 00:04:03,966 --> 00:04:05,866 Probably “is” true), 91 00:04:05,866 --> 00:04:07,566 or some b inside 
the natural numbers, 92 00:04:07,566 --> 00:04:10,233 and P1, P2 all the way up to Pk 93 00:04:10,233 --> 00:04:11,200 94 00:04:11,200 --> 00:04:14,633 are true implies that that Pk plus 1 is true 95 00:04:14,633 --> 00:04:17,666 for all k inside the 
natural numbers, 96 00:04:17,666 --> 00:04:21,333 then we know that Pn is true 
for all natural numbers n. 97 00:04:21,333 --> 00:04:23,866 So what is this really saying? 
Okay so I can read a slide, 98 00:04:23,866 --> 00:04:25,733 but what is 
this saying? 99 00:04:25,733 --> 00:04:27,466 100 00:04:27,466 --> 00:04:31,300 So what this is saying is, 
instead of assuming that just 101 00:04:31,300 --> 00:04:34,433 Pk is true and proving 
that Pk plus 1 is true, 102 00:04:34,433 --> 00:04:38,466 we're going to assume that 
all of the terms from P1 to… 103 00:04:38,466 --> 00:04:41,433 all the statements from P1 to Pk are true. 104 00:04:41,433 --> 00:04:44,000 So if we think about this in the 
domino analogy, it's no longer that 105 00:04:44,000 --> 00:04:48,166 we're just assuming that the kth domino 
falls implies that the k plus first domino falls, 106 00:04:48,166 --> 00:04:51,533 we're assuming that the first k 
dominoes have already fallen 107 00:04:51,533 --> 00:04:54,633 and that that implies that the k plus first domino has fallen. 108 00:04:54,633 --> 00:04:56,066 109 00:04:56,066 --> 00:04:59,000 That's the idea behind the 
Principle of Strong Induction. 110 00:04:59,000 --> 00:05:03,033 Now it turns out because you're 
proving multiple base cases possibly, 111 00:05:03,033 --> 00:05:06,400 you can also take k to be at least b here. 112 00:05:06,400 --> 00:05:07,500 113 00:05:07,500 --> 00:05:10,966 So again b is just 
some natural number. 114 00:05:10,966 --> 00:05:11,633 115 00:05:11,633 --> 00:05:14,766 Again so in the Principal of Mathematical 
Induction, you always have b equals 1, 116 00:05:14,766 --> 00:05:18,466 we only prove the first case and then the 117 00:05:18,466 --> 00:05:23,966 second implication step, we 
have Pk implies Pk plus 1. 118 00:05:23,966 --> 00:05:27,766 Here we have P1, P2 all the 
way up to Pk imply Pk plus 1. 119 00:05:27,766 --> 00:05:30,100 Now typically you don't 
use all of the cases. 120 00:05:30,100 --> 00:05:30,733 121 00:05:30,733 --> 00:05:32,733 Sometimes it helps to 
know they're all true. 122 00:05:32,733 --> 00:05:35,733 Sometimes you only need 
a couple of previous steps. 123 00:05:35,733 --> 00:05:37,066 Either way is fine. 124 00:05:37,066 --> 00:05:38,233 125 00:05:38,233 --> 00:05:40,166 But that's the idea behind the 
Principle of Strong Induction. 126 00:05:40,166 --> 00:05:42,666 Now if you want to see an example, 
I'm not going to do an example here 127 00:05:42,666 --> 00:05:45,466 because they do take a 
decent amount of time 128 00:05:45,466 --> 00:05:47,366 and they are 
quite convoluted, 129 00:05:47,366 --> 00:05:50,333 but I do have other videos on the 
Math 135 Resources Page where 130 00:05:50,333 --> 00:05:52,800 you can check out if you want to 
see an example of strong induction. 131 00:05:52,800 --> 00:05:55,566 I also explain how to know 
when to use strong induction, 132 00:05:55,566 --> 00:05:57,433 and when to use 
weak induction. 133 00:05:57,433 --> 00:05:59,633 Pretty much I always start 
the proof by induction, 134 00:05:59,633 --> 00:06:03,066 and if I get stuck or if I need multiple 
base cases or if I need to go back 135 00:06:03,066 --> 00:06:07,300 a couple of steps before, instead of just 
k I need k minus 1 and k minus 2 being true, 136 00:06:07,300 --> 00:06:11,300 something like that, then I'll go back and 
change my proof to be strong induction. 137 00:06:11,300 --> 00:06:12,433 138 00:06:12,433 --> 00:06:15,933 So I usually just leave a couple 
of blanks just in case I need to 139 00:06:15,933 --> 00:06:18,566 prove something 
with strong induction. 140 00:06:18,566 --> 00:06:20,933 Okay so that's the 
Principle of Strong Induction. 141 00:06:20,933 --> 00:06:25,133 Maybe one last little topic 
here that fits in nicely, 142 00:06:25,133 --> 00:06:28,533 the Fibonacci sequence. This is a 
beautiful sequence in mathematics 143 00:06:28,533 --> 00:06:32,633 and we define it as follows: we 
let f1 equal 1, and f at 2 equal 1, 144 00:06:32,633 --> 00:06:35,300 and we're going to define 
every term after that to be 145 00:06:35,300 --> 00:06:37,333 the sum of the 
previous two terms. 146 00:06:37,333 --> 00:06:38,633 So this defines the sequence 147 00:06:38,633 --> 00:06:43,300 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 
89, and so on and so forth. 148 00:06:43,300 --> 00:06:44,866 149 00:06:44,866 --> 00:06:47,766 It's a cool sequence, it appears 
in lots of applications. 150 00:06:47,766 --> 00:06:51,966 One of my favorite things to tell 
students is to go online and look up 151 00:06:51,966 --> 00:06:55,033 a YouTube video by 
a band called Tool 152 00:06:55,033 --> 00:06:57,166 and the song is 
called Lateralus 153 00:06:57,166 --> 00:07:00,133 and it uses the Fibonacci sequence in a 154 00:07:00,133 --> 00:07:03,300 really cool way. I think 
it's a really neat song, 155 00:07:03,300 --> 00:07:05,633 and it's also a good 
song in its own right. 156 00:07:05,633 --> 00:07:08,500 So check that out if 
you're interested in 157 00:07:08,500 --> 00:07:12,600 music or if you want to see some cool applications of the Fibonacci sequence. 158 00:07:12,600 --> 00:07:15,966 There are lots, that's just 
one of my favorites 159 00:07:15,966 --> 00:07:17,733 that I'll mention to you. 160 00:07:17,733 --> 00:07:20,800 Again this is one of these 
things you should just know. 161 00:07:20,800 --> 00:07:21,466 162 00:07:21,466 --> 00:07:24,400 You should know the Fibonacci sequence. Every term is defined as - 163 00:07:24,400 --> 00:07:26,733 every term after the first 
two, which are both 1’s, 164 00:07:26,733 --> 00:07:31,300 is defined as just the sum of the previous 
two terms. You should know the sequence. 165 00:07:31,300 --> 00:07:34,766 We've seen a lot of - we’ve seen a couple of proofs in class 166 00:07:34,766 --> 00:07:37,700 of induction statements that 
use the Fibonacci sequence. 167 00:07:37,700 --> 00:07:40,600 Again, beautiful, 
beautiful.. 168 00:07:40,600 --> 00:07:43,300 it's just a beautiful topic. It's a beautiful sequence.