1 00:00:00,000 --> 00:00:02,933 In this video, we're going to talk about 2 00:00:02,933 --> 00:00:06,466 a proof by mathematical induction 3 00:00:06,466 --> 00:00:08,166 and we're going to critique it. 4 00:00:08,166 --> 00:00:12,600 We're going to try to identify some of the 
mistakes that are made in this proof. 5 00:00:12,600 --> 00:00:14,200 6 00:00:14,200 --> 00:00:17,266 This proof at some point 
was a midterm question 7 00:00:17,266 --> 00:00:19,566 and most of these mistakes 
are ones that I found on 8 00:00:19,566 --> 00:00:21,600 papers from students. 9 00:00:21,600 --> 00:00:22,500 10 00:00:22,500 --> 00:00:24,733 So here's our problem: we're going to use 11 00:00:24,733 --> 00:00:27,666 mathematical induction to prove 12 00:00:27,666 --> 00:00:30,100 that the sum from i equals 1 to n of 13 00:00:30,100 --> 00:00:32,200 i over 3 to the power of i, 14 00:00:32,200 --> 00:00:35,000 is equal to 3/4 minus 15 00:00:35,000 --> 00:00:38,466 2n plus 3 all divided by 4 
times 3 to the power of n 16 00:00:38,466 --> 00:00:40,333 for all natural numbers n. 17 00:00:40,333 --> 00:00:44,433 If you haven't done so I would suggest pausing 
the video and actually trying to see how many of 18 00:00:44,433 --> 00:00:47,633 the errors that you can find in this proof. 19 00:00:47,633 --> 00:00:49,633 20 00:00:49,633 --> 00:00:53,233 Hopefully you're done and 
I'll now discuss them. 21 00:00:53,233 --> 00:00:55,000 22 00:00:55,000 --> 00:00:57,300 So first, we start off with the proof. "We prove 23 00:00:57,300 --> 00:01:01,000 P n is true for all natural 
numbers n by induction". Well 24 00:01:01,000 --> 00:01:04,066 one thing that we haven't done 
yet is we haven't identified 25 00:01:04,066 --> 00:01:06,433 what P n is yet. 26 00:01:06,433 --> 00:01:07,533 27 00:01:07,533 --> 00:01:09,000 You should... 28 00:01:09,000 --> 00:01:13,100 you should state what the P n 
that you're trying to prove is. 29 00:01:13,100 --> 00:01:14,966 30 00:01:14,966 --> 00:01:17,000 I know that here it might 
seem very clear but 31 00:01:17,000 --> 00:01:19,333 even still, for proper writing technique, you should 32 00:01:19,333 --> 00:01:21,866 tell the reader what P n is. You 
shouldn't introduce variables 33 00:01:21,866 --> 00:01:23,866 without letting the reader know what they are. 34 00:01:23,866 --> 00:01:25,266 35 00:01:25,266 --> 00:01:28,300 So even straight out the 
gate we're off to a bad start. 36 00:01:28,300 --> 00:01:29,166 37 00:01:29,166 --> 00:01:33,066 "The base case when i equals 
1" well that's not true, right? 38 00:01:33,066 --> 00:01:35,666 I mean the base case really 
is when n is equal to 1. 39 00:01:35,666 --> 00:01:38,666 i is just the indexing variable 
that has nothing to do with the 40 00:01:38,666 --> 00:01:40,333 statement that we're trying to prove. 41 00:01:40,333 --> 00:01:42,466 I could have called i something else and 42 00:01:42,466 --> 00:01:44,133 nothing would have really changed 43 00:01:44,133 --> 00:01:47,900 as long as I made sure that the 
other instances of i matched it. 44 00:01:47,900 --> 00:01:51,233 So that's a problem. So this needs to be an n instead of an i. 45 00:01:51,233 --> 00:01:52,400 46 00:01:52,400 --> 00:01:56,033 Now in line 1 - we're already up to 2 
mistakes and we're only on line 2… 47 00:01:56,033 --> 00:02:00,166 line 1, what do we have? Well we 
have the sum from i equals 1 to 1 48 00:02:00,166 --> 00:02:02,566 of i over 3 to the i, that's okay. 49 00:02:02,566 --> 00:02:07,333 But then now we say that is equal to 3/4 
minus 2, times 1, plus 3 over 4, times 3 50 00:02:07,333 --> 00:02:10,400 but this is what we wanted to 
prove. This equal sign right here 51 00:02:10,400 --> 00:02:13,566 is the statement when n 
equals 1 is plugged in. 52 00:02:13,566 --> 00:02:14,533 53 00:02:14,533 --> 00:02:17,066 So this equal sign isn't 
really what we want. 54 00:02:17,066 --> 00:02:20,466 We want to show that this thing, 
after we do a whole bunch of work 55 00:02:20,466 --> 00:02:23,500 and get it down to 1/3, is 
actually equal to the sum. 56 00:02:23,500 --> 00:02:24,633 57 00:02:24,633 --> 00:02:27,466 So this equal sign is actually a mistake. Right? 58 00:02:27,466 --> 00:02:30,166 We should just start with 
this side get down to 1/3 59 00:02:30,166 --> 00:02:32,733 and then claim that 1/3 is equal to this, which is true. 60 00:02:32,733 --> 00:02:34,233 61 00:02:34,233 --> 00:02:36,366 So another mistake there. 62 00:02:36,366 --> 00:02:37,266 63 00:02:37,266 --> 00:02:39,333 The induction hypothesis, there are 64 00:02:39,333 --> 00:02:42,566 several mistakes here so let's talk about this. 65 00:02:42,566 --> 00:02:45,033 "Assume P k is true 66 00:02:45,033 --> 00:02:48,433 for all natural numbers between... 67 00:02:48,433 --> 00:02:51,333 from 1 less than or equal to i is less than or equal to k, 68 00:02:51,333 --> 00:02:54,533 k greater than or equal to 2. Okay... 69 00:02:54,533 --> 00:02:58,200 lots of mistakes. For one, 70 00:02:58,200 --> 00:03:01,433 i is the indexing variable right, so we 71 00:03:01,433 --> 00:03:03,633 definitely don't want to say this. 72 00:03:03,633 --> 00:03:08,333 Okay? This 1 is less than or equal to i is less 
than or equal to k. This doesn't make any sense. 73 00:03:08,333 --> 00:03:10,133 i is the indexing variable of my summation. 74 00:03:10,133 --> 00:03:12,266 It has nothing to do with 
the induction hypothesis. 75 00:03:12,266 --> 00:03:13,166 76 00:03:13,166 --> 00:03:15,333 The next thing: the person wrote, 77 00:03:15,333 --> 00:03:17,533 "for all natural numbers". Well 78 00:03:17,533 --> 00:03:21,833 you don't want to assume that 
P k is true for all natural numbers, 79 00:03:21,833 --> 00:03:24,933 that doesn't make any sense, 
right? You're trying to prove that 80 00:03:24,933 --> 00:03:26,966 P n is true for all natural numbers 81 00:03:26,966 --> 00:03:31,133 so assuming that P k is true 
for all natural numbers k 82 00:03:31,133 --> 00:03:34,600 means that you're assuming 
what you want to prove is true. 83 00:03:34,600 --> 00:03:38,633 What you really want to do is take 
one instance. So for some value 84 00:03:38,633 --> 00:03:41,633 of k, you want to assume that P k is true 85 00:03:41,633 --> 00:03:44,500 and because that value 
is arbitrary, that's where 86 00:03:44,500 --> 00:03:47,000 the induction sort of makes sense. 87 00:03:47,000 --> 00:03:48,166 88 00:03:48,166 --> 00:03:52,333 You take an arbitrary value to 
show that P k implies P k plus 1 89 00:03:52,333 --> 00:03:55,233 and because that k was 
arbitrary, you can prove that 90 00:03:55,233 --> 00:03:55,900 91 00:03:55,900 --> 00:03:58,633 P n must always be true by the 
Principle of Mathematical Induction. 92 00:03:58,633 --> 00:04:00,633 Remember that's the idea, right? 93 00:04:00,633 --> 00:04:01,666 94 00:04:01,666 --> 00:04:05,800 Third mistake is we have k is greater than 
or equal to 2, so even if you had written 95 00:04:05,800 --> 00:04:07,800 for some natural number 96 00:04:07,800 --> 00:04:11,066 k with k greater than or 
equal to 2, we're still wrong. 97 00:04:11,066 --> 00:04:12,600 Why is that now? 98 00:04:12,600 --> 00:04:13,233 99 00:04:13,233 --> 00:04:15,500 The reason why were wrong now is because the k, 100 00:04:15,500 --> 00:04:17,533 the base case for the induction… 101 00:04:17,533 --> 00:04:19,333 the smallest case in the 
induction hypothesis 102 00:04:19,333 --> 00:04:23,733 should overlap with the largest 
base case in your base cases. 103 00:04:23,733 --> 00:04:28,066 This is true for strong induction, this is true for just regular inductions as well. 104 00:04:28,066 --> 00:04:30,333 So again, what's happening 
here? Well you have 105 00:04:30,333 --> 00:04:31,500 106 00:04:31,500 --> 00:04:34,966 k is greater than or equal to 2 107 00:04:34,966 --> 00:04:38,600 and what this is sort of saying is that if 
you ended up proving that this was true, 108 00:04:38,600 --> 00:04:41,466 you would have proved 
that P 2 implies P 3 and 109 00:04:41,466 --> 00:04:44,766 P 3 implies P 4 and P 4 implies P 5 110 00:04:44,766 --> 00:04:46,966 where P is your statement of course, 111 00:04:46,966 --> 00:04:49,366 and so on and so forth. Right? 
That's what you've proved, 112 00:04:49,366 --> 00:04:51,766 but you haven't actually 
proved that P 2 is true; 113 00:04:51,766 --> 00:04:54,266 so in some sense, you 
have this long, long 114 00:04:54,266 --> 00:04:56,666 string of implications, but 
you don't know that the 115 00:04:56,666 --> 00:04:59,633 first one is true so you don't know 
that all the other ones are true. 116 00:04:59,633 --> 00:05:01,966 And again, if you think about it like a domino analogy, right, 117 00:05:01,966 --> 00:05:04,266 you know that the second domino 
will knock down the third one, and the 118 00:05:04,266 --> 00:05:07,100 third one will knock down the fourth one, and 
the fourth one will knock down the fifth one 119 00:05:07,100 --> 00:05:11,066 and so on and so forth, but you don't 
know that the second domino falls down. 120 00:05:11,066 --> 00:05:11,500 121 00:05:11,500 --> 00:05:14,233 This is why you need that 
overlap, right? If you 122 00:05:14,233 --> 00:05:16,900 say here instead "k is 
greater than or equal to 1" 123 00:05:16,900 --> 00:05:19,800 and then go through the proof 
and prove it, you proved that 124 00:05:19,800 --> 00:05:23,100 if P 1 falls, then P 2 falls, 
if P 2 falls, then P 3 falls, 125 00:05:23,100 --> 00:05:26,533 and if P 3 falls then P 4 
falls and so on and so forth. 126 00:05:26,533 --> 00:05:29,966 And we know that P 1 falls 
because that was our base case. 127 00:05:29,966 --> 00:05:33,200 The combination of all of these things 
gives you the proof that you want. 128 00:05:33,200 --> 00:05:35,333 129 00:05:35,333 --> 00:05:39,033 All that being said, let's see if the 
next line is right: "That is, assume…" 130 00:05:39,033 --> 00:05:41,066 well we're off to a bad start again. 131 00:05:41,066 --> 00:05:43,333 "P k equals" well P k is a statement, 132 00:05:43,333 --> 00:05:45,933 so P k can't equal a value 133 00:05:45,933 --> 00:05:48,500 which is what this says, so this 
equals sign doesn't make any sense. 134 00:05:48,500 --> 00:05:51,933 This P k probably just shouldn't be 
here at all in the induction hypothesis. 135 00:05:51,933 --> 00:05:53,433 136 00:05:53,433 --> 00:05:55,966 Now we have this sum 
from i equals 1 to k but 137 00:05:55,966 --> 00:05:58,833 for some reason we've 
also substituted the k in 138 00:05:58,833 --> 00:06:01,600 for the index variable i, that's not right. 139 00:06:01,600 --> 00:06:05,666 Remember the index variable depends 
on the index here. It doesn't depend on 140 00:06:05,666 --> 00:06:09,600 the index at the top it just depends on the one 
at the bottom. So when you're replacing the one, 141 00:06:09,600 --> 00:06:12,200 you're replacing the n in the 
index variable in the statement, 142 00:06:12,200 --> 00:06:15,066 you really do want just the n to become a k 143 00:06:15,066 --> 00:06:17,766 and you want to leave the i's 
alone because the i's belong to the 144 00:06:17,766 --> 00:06:20,200 index variable in your summation notation. 145 00:06:20,200 --> 00:06:22,066 146 00:06:22,066 --> 00:06:25,433 The right-hand side is correct so we 
did one out of three things correct there. 147 00:06:25,433 --> 00:06:26,300 148 00:06:26,300 --> 00:06:29,533 The induction conclusion: 
so for P k plus 1 149 00:06:29,533 --> 00:06:30,966 150 00:06:30,966 --> 00:06:33,533 what do we have? The first line...so 151 00:06:33,533 --> 00:06:36,100 this is actually a reasonable start to our proof. 152 00:06:36,100 --> 00:06:39,333 We start with the left-hand side 
of the thing we're trying to prove 153 00:06:39,333 --> 00:06:42,066 but instead of n we have a k plus 1, 154 00:06:42,066 --> 00:06:44,700 and now we're trying to go through and 
get to the end. So this is actually okay. 155 00:06:44,700 --> 00:06:47,300 Some people probably leave the 
n here and that's technically wrong 156 00:06:47,300 --> 00:06:49,300 you really do want a k plus 1 here. 157 00:06:49,300 --> 00:06:50,266 158 00:06:50,266 --> 00:06:52,900 Unless you tell the reader that you're making n k plus 1 but 159 00:06:52,900 --> 00:06:56,533 I wouldn't do it like that, I would 
do it like this. So that's okay. 160 00:06:56,533 --> 00:06:59,566 We've broken off the last term and it
looks like we've done it correctly. So you're 161 00:06:59,566 --> 00:07:04,400 taking the sum from 1 to k of i over 3 to the i, you leave that alone, 162 00:07:04,400 --> 00:07:07,933 and now you're plugging in the last term 
k plus 1 over 3 to the power of k plus 1. 163 00:07:07,933 --> 00:07:09,766 164 00:07:09,766 --> 00:07:12,233 The next line: this is a line that 
you really should explain. 165 00:07:12,233 --> 00:07:15,033 This is not immediately clear. 166 00:07:15,033 --> 00:07:17,466 What's happening here though is that 
you're using the induction hypothesis. 167 00:07:17,466 --> 00:07:21,000 You really should sell the reader "Hey I'm 
using the induction hypothesis at this point". 168 00:07:21,000 --> 00:07:22,833 169 00:07:22,833 --> 00:07:24,833 Okay now this is fine. 170 00:07:24,833 --> 00:07:27,533 The next line we attempted to 
find a common denominator but 171 00:07:27,533 --> 00:07:29,400 we've left our denominator the same. 172 00:07:29,400 --> 00:07:32,233 So we really should have 4 
times 3k plus 1 on this fraction… 173 00:07:32,233 --> 00:07:33,500 174 00:07:33,500 --> 00:07:35,133 that's a mistake… 175 00:07:35,133 --> 00:07:35,900 176 00:07:35,900 --> 00:07:39,333 Here's another mistake that a lot of people made. So this is, you know, 177 00:07:39,333 --> 00:07:41,333 these two fractions, we're taking 3/4 178 00:07:41,333 --> 00:07:44,366 minus 6k plus 9 179 00:07:44,366 --> 00:07:47,033 plus 4k plus 4. 180 00:07:47,033 --> 00:07:50,566 Really, this negative goes to both 
of the terms in the numerator. 181 00:07:50,566 --> 00:07:51,500 182 00:07:51,500 --> 00:07:54,066 The next line you've just 
written the sum of the 183 00:07:54,066 --> 00:07:58,033 things on the top however both of these terms 
should have been negative from this negative. 184 00:07:58,033 --> 00:08:02,200 When you write the fraction like this, the 
negative is actually going to all four terms. 185 00:08:02,200 --> 00:08:04,266 So now you're going to get, you 
know, you're going to get 186 00:08:04,266 --> 00:08:07,333 negative 10k minus 13 as opposed to 187 00:08:07,333 --> 00:08:11,333 minus 6k minus 9 plus 4k plus 4. 188 00:08:11,333 --> 00:08:11,900 189 00:08:11,900 --> 00:08:14,733 This is a very bad mistake to make. 
Remember that when you're doing this, you 190 00:08:14,733 --> 00:08:18,100 really want to bring the negative in 
first and then add the numerators. 191 00:08:18,100 --> 00:08:21,366 192 00:08:21,366 --> 00:08:22,900 Down here we've clearly cheated. 193 00:08:22,900 --> 00:08:26,400 There's no way to make negative 10k plus 13 look like 194 00:08:26,400 --> 00:08:29,600 negative 2 times k plus 1 plus 3. 195 00:08:29,600 --> 00:08:34,100 Don't cheat like this, it's very 
obvious that there's steps missing. 196 00:08:34,100 --> 00:08:36,700 "Therefore P k plus 1 is true." 197 00:08:36,700 --> 00:08:39,266 It's good that you have a start 
of a concluding statement 198 00:08:39,266 --> 00:08:42,166 but that's not really what... we're not done yet, right? 199 00:08:42,166 --> 00:08:45,866 Why can we conclude, therefore, that P n is true for all natural numbers n? 200 00:08:45,866 --> 00:08:49,200 That's because of the Principle 
of Mathematical Induction. 201 00:08:49,200 --> 00:08:52,566 So we really should have a full 
concluding statement that says, 202 00:08:52,566 --> 00:08:53,500 203 00:08:53,500 --> 00:08:55,833 “therefore P n is true 204 00:08:55,833 --> 00:08:59,633 for all natural numbers n by the 
Principle of Mathematical Induction." 205 00:08:59,633 --> 00:09:01,700 206 00:09:01,700 --> 00:09:03,666 Okay... 207 00:09:03,666 --> 00:09:05,266 So... 208 00:09:05,266 --> 00:09:05,866 209 00:09:05,866 --> 00:09:08,600 I think I found all mistakes in this 210 00:09:08,600 --> 00:09:12,400 proof. At least all the ones 
I intentionally made, I found. 211 00:09:12,400 --> 00:09:17,133 Now, let's try to write this up a little bit 
better, a little bit cleaner, a little bit nicer. 212 00:09:17,133 --> 00:09:19,333 By the way, grading this would 
be very difficult because 213 00:09:19,333 --> 00:09:21,433 realistically no step is correct. 214 00:09:21,433 --> 00:09:24,266 Everything looks like it's good, but 215 00:09:24,266 --> 00:09:28,966 your base case has errors, your statement at the beginning is unclear, 216 00:09:28,966 --> 00:09:31,333 your induction hypothesis is a disaster, 217 00:09:31,333 --> 00:09:33,933 your induction conclusion 
has right elements like 218 00:09:33,933 --> 00:09:36,366 you broke it up but I 
mean other than that, 219 00:09:36,366 --> 00:09:41,100 much of this is incorrect 
in terms of manipulations, 220 00:09:41,100 --> 00:09:44,133 and you don't have a concluding statement. this would be a tough proof to mark 221 00:09:44,133 --> 00:09:47,333 and giving it 0 would probably not be that unreasonable despite the fact that 222 00:09:47,333 --> 00:09:49,700 many of the ideas that you need are here. 223 00:09:49,700 --> 00:09:50,566 224 00:09:50,566 --> 00:09:52,800 Let's go to an actual proof. 225 00:09:52,800 --> 00:09:53,400 226 00:09:53,400 --> 00:09:55,366 Okay, so same question. 227 00:09:55,366 --> 00:10:00,600 I'm going to try to give you a proof that 
I've written. Hopefully it's correct, we'll see. 228 00:10:00,600 --> 00:10:04,300 So proof, we're going to start off a little 
bit better. Let P n be the statement, 229 00:10:04,300 --> 00:10:07,333 the sum from i equals 1 
to n of i over 3 to the i 230 00:10:07,333 --> 00:10:13,200 is equal to 3/4 minus 2n plus 3 all divided by 4 times 3 to the n." 231 00:10:13,200 --> 00:10:14,700 232 00:10:14,700 --> 00:10:18,166 We prove that the statement is true 
for all natural numbers n by induction. 233 00:10:18,166 --> 00:10:19,566 234 00:10:19,566 --> 00:10:22,900 So the base case when n equals 1, I have 
a "right-hand side to left-hand side" proof 235 00:10:22,900 --> 00:10:25,500 and I'm starting with the right-hand side. 236 00:10:25,500 --> 00:10:27,833 Notice, by the way, in this 
case this statement is true. 237 00:10:27,833 --> 00:10:31,166 The right-hand side is equal to this 238 00:10:31,166 --> 00:10:31,800 239 00:10:31,800 --> 00:10:33,600 difference of fractions. 240 00:10:33,600 --> 00:10:34,800 241 00:10:34,800 --> 00:10:37,300 This difference of fractions is equal to this 242 00:10:37,300 --> 00:10:41,866 and this thing is equal to this 
difference of fractions here. 243 00:10:41,866 --> 00:10:44,900 Again, arguably maybe I 
should have written it with the 244 00:10:44,900 --> 00:10:46,833 equal sign in a column 
down, like I did down here. 245 00:10:46,833 --> 00:10:50,133 The only reason why I didn't is 
because I wanted it to fit on one page. 246 00:10:50,133 --> 00:10:52,666 247 00:10:52,666 --> 00:10:56,900 So that's fine. Hopefully the "math grammar 
people" won't get too mad at me. 248 00:10:56,900 --> 00:10:58,900 249 00:10:58,900 --> 00:11:02,066 Anyway, this is equal to 3/4 
minus 5/12. Just plug it in, 250 00:11:02,066 --> 00:11:06,033 do a little bit of arithmetic, get down 
to 1/3 and 1/3 is this summation: 251 00:11:06,033 --> 00:11:08,833 the sum from 1 to 1 of i 
over 3 to the power of i, 252 00:11:08,833 --> 00:11:12,100 and that is the left-hand side. So now 
I've started with the right-hand side 253 00:11:12,100 --> 00:11:15,333 and gotten to the left-hand side. That is a complete and valid proof. 254 00:11:15,333 --> 00:11:17,000 255 00:11:17,000 --> 00:11:19,266 So therefore, P 1 is true. 256 00:11:19,266 --> 00:11:20,166 257 00:11:20,166 --> 00:11:22,700 Now my induction hypothesis, I've written it out 258 00:11:22,700 --> 00:11:25,300 a little bit different than I probably normally would, but there's a reason why. 259 00:11:25,300 --> 00:11:28,300 "Assume P k is true for some..." 260 00:11:28,300 --> 00:11:33,033 integer," remember we're only assuming 
that this is true for a single case. A lot of 261 00:11:33,033 --> 00:11:35,933 students wrote "for some natural numbers", 262 00:11:35,933 --> 00:11:38,233 "for some integers”, no, it's really just 263 00:11:38,233 --> 00:11:40,600 for some single integer 264 00:11:40,600 --> 00:11:42,466 k greater than or equal to 1. 265 00:11:42,466 --> 00:11:43,166 266 00:11:43,166 --> 00:11:45,000 That is, we are assuming that 267 00:11:45,000 --> 00:11:49,166 the sum from 1 to k of i over 3 to the power of i is 268 00:11:49,166 --> 00:11:53,333 3/4 minus 2k plus 3 all divided 
by 4 times 3 to the power of k. 269 00:11:53,333 --> 00:11:54,400 270 00:11:54,400 --> 00:11:56,966 Can you write just for some natural number k? 271 00:11:56,966 --> 00:11:59,733 You absolutely can, but I 
wanted to make it clear that 272 00:11:59,733 --> 00:12:03,266 k is greater than or equal to 1, 
and why the 1 here? Because 273 00:12:03,266 --> 00:12:07,333 the last base case we proved was 
n equals 1. You want that overlap, 274 00:12:07,333 --> 00:12:09,666 right, for the same reason that we talked about earlier. 275 00:12:09,666 --> 00:12:11,433 276 00:12:11,433 --> 00:12:14,833 So now in my induction 
conclusion, we now prove that 277 00:12:14,833 --> 00:12:19,033 P at k plus 1 is true. That is, we'd like to prove this statement... 278 00:12:19,033 --> 00:12:21,300 that probably should be a period here... 279 00:12:21,300 --> 00:12:24,000 so we want to prove that 
the sum from 1 to k plus 1 280 00:12:24,000 --> 00:12:26,933 of our fraction is equal to this right-hand side. 281 00:12:26,933 --> 00:12:28,300 282 00:12:28,300 --> 00:12:30,433 This is the statement that we 
want to prove. So it's very 283 00:12:30,433 --> 00:12:33,400 clear what we want to prove, and now 
I'm going to take the left-hand side and 284 00:12:33,400 --> 00:12:36,100 derive the right-hand side, 
which is what I say next. 285 00:12:36,100 --> 00:12:36,900 286 00:12:36,900 --> 00:12:38,900 We do the fraction break off as normal, 287 00:12:38,900 --> 00:12:43,333 I cite when I use the induction hypothesis, 
which is from step one to step two. 288 00:12:43,333 --> 00:12:44,500 289 00:12:44,500 --> 00:12:46,600 From here now, 290 00:12:46,600 --> 00:12:50,166 I'm finding my common denominator, 
so 4 times 3 to the k plus 1, 291 00:12:50,166 --> 00:12:53,433 and I'm bringing the negative sign in 
so that now when I add my fractions 292 00:12:53,433 --> 00:12:56,000 I actually get the correct value. 293 00:12:56,000 --> 00:12:59,300 I break up the 5 as minus 2 minus 3. 294 00:12:59,300 --> 00:13:02,366 All these terms are negative so I remove the fraction once again. 295 00:13:02,366 --> 00:13:06,333 I factor out my 2 and I get the 
exact thing I want on the right. 296 00:13:06,333 --> 00:13:10,533 So therefore, P(k) plus 1 is true, and 
now your formal concluding statement: 297 00:13:10,533 --> 00:13:15,700 "Thus by the Principle of Mathematical 
Induction, P n is true for all natural numbers n.” 298 00:13:15,700 --> 00:13:18,266 299 00:13:18,266 --> 00:13:21,333 That's it, this is a complete proof. I think it is 300 00:13:21,333 --> 00:13:25,200 correct and would earn full 
marks and everything is good. 301 00:13:25,200 --> 00:13:26,966 302 00:13:26,966 --> 00:13:30,200 But that is it. So hopefully, 303 00:13:30,200 --> 00:13:32,633 I've given you a little bit of insight as to some 304 00:13:32,633 --> 00:13:35,600 common mistakes that people 
make when writing an induction proof, 305 00:13:35,600 --> 00:13:40,133 and hopefully this helps you to 
frame future induction proofs properly. 306 00:13:40,133 --> 00:13:43,366 One final piece of advice: again, whenever... 307 00:13:43,366 --> 00:13:47,000 whenever a student comes to me and says 
that they're stuck with an induction proof, 308 00:13:47,000 --> 00:13:51,566 one of the first things I ask them is, "Well 
did you write down the statement P at n?" 309 00:13:51,566 --> 00:13:55,400 and many of the times students will 
tell me, "No I haven't" and I find that 310 00:13:55,400 --> 00:13:57,833 just the act of writing this statement down 311 00:13:57,833 --> 00:14:00,933 often gives students a really big push as to 312 00:14:00,933 --> 00:14:04,533 how to start your induction proof and how 
to frame it properly and how to finish it off. 313 00:14:04,533 --> 00:14:06,566 314 00:14:06,566 --> 00:14:09,166 So if I can give you one piece 
of advice with an induction proof 315 00:14:09,166 --> 00:14:12,133 that would be the piece I'd give 
you. Write down P of n explicitly. 316 00:14:12,133 --> 00:14:14,599 Thank you very much, hopefully this helped.