For more information, please see full course syllabus of Math Analysis

For more information, please see full course syllabus of Math Analysis

### Mathematical Induction

- One of the most important ideas in mathematics is being able to prove something with total certainty. We can show not just that something works out, but that it will work every time, forever-it is mathematical
__fact__. We show this with*proof*. -
*Mathematical induction*is a form of proof that allows us to prove that a pattern holds true forever. - A good metaphor for the idea of induction is a never-ending line of dominoes. If we have two guarantees,
- The first domino will fall over;
- If a domino falls over, it will cause the next domino to fall over as well;

__all__the dominoes in our infinitely long line of dominoes will fall over. -
*The principle of mathematical induction*is basically the same idea as the above metaphor, except we replace "domino falling over" with "statement being true". Let P_{1}, P_{2}, P_{3}, P_{4}, ..., P_{n}, ... be some sequence of statements where n is a positive integer. If- P
_{1}is true, and -
__If__P_{k}is true for a positive integer k,__then__P_{k+1}must also be true,

_{n}is true for all positive integers n. - P
- Above, we call the first step the
*base case*because it establishes the basis we are working from. - Above, the second step is called the
*inductive step*since that is where the actual induction occurs. In the inductive step, the assumption "if P_{k}is true" is called the*inductive hypothesis*, because we must use this hypothesis to show P_{k+1}will also be true. - It helps a lot to somehow include part of the statement for P
_{k}when we are writing out P_{k+1}. This is because we will almost inevitably wind up using our inductive hypothesis (P_{k}is true) to show that P_{k+1}is also true. But we can't use our hypothesis about P_{k}unless it somehow appears in P_{k+1}. - Check out the video to see a working example of the inductive hypothesis where each step is explained. Induction can be a little confusing at first, and it really helps to see it in action.

### Mathematical Induction

Lecture Slides are screen-captured images of important points in the lecture. Students can download and print out these lecture slide images to do practice problems as well as take notes while watching the lecture.

- Intro 0:00
- Introduction 0:06
- Belief Vs. Proof 1:22
- A Metaphor for Induction 6:14
- The Principle of Mathematical Induction 11:38
- Base Case
- Inductive Step
- Inductive Hypothesis
- A Remark on Statements 14:18
- Using Mathematical Induction 16:58
- Working Example 19:58
- Finding Patterns
- Example 1 30:17
- Example 2 37:50
- Example 3 42:38

### Math Analysis Online

### Transcription: Mathematical Induction

*Hi--welcome back to Educator.com.*0000

*Today, we are going to talk about mathematical induction.*0002

*The great thing about math is that we can trust it.*0005

*Regardless of the technology that math enables us to have in our daily lives (like the Internet), what we learn in math is entirely, beautifully true.*0007

*We can have certainty in this truth, because of proof.*0016

*In math, we start with a few simple ideas, and then we use proof to build a tower of logic.*0019

*Because we prove every theorem and method that we work with, we can trust the whole of mathematics.*0025

*Mathematics is built on this concept of truth--that we start with some things that we can just take for granted,*0030

*absolutely certainly--these axiomatic truths that we looked at in geometry, for example, previously--you have seen it in some courses.*0037

*We start with these basic axioms, and then we work up from there, using logic.*0044

*We can use proof to make sure that we can trust every single thing that we work with.*0048

*So far in this course, we have proved many things with a variety of logical arguments.*0052

*We have made very strong logical arguments that show, without a doubt, that something has to be true.*0056

*In this lesson, we are going to see a new form for proofs, mathematical induction.*0061

*This method can be used anywhere, from our current level of math all the way to very advanced mathematics.*0066

*It is this really flexible kind of proof that lets us show a lot of things; it is a very powerful way of proving things.*0071

*All right, let's talk about belief versus proof.*0077

*In math, it is important to recognize that there is a difference between believing that something is true and proving that something is true.*0080

*While we may strongly believe in something, that implies that there is still some level of reasonable doubt.*0087

*Believing in something doesn't mean that we can know it absolutely certainly; it just means that it is probably true.*0092

*But there is still this tiny crack of doubt that maybe it is not going to end up being true.*0098

*We can only be certain about something once we have proved it; we can only be certain that something is true once we have proof.*0102

*A proof is an irrefutable logical argument; it is something that very clearly shows (and there is no way to disagree with it)*0110

*that, given some something, we can show that it is always going to end up working out; it gives us total certainty.*0116

*This means that, when we notice a pattern in the way things work, we don't know for sure that it will always hold true.*0124

*We may believe that it will hold, but until we prove it, we cannot be absolutely certain.*0129

*So, we may believe in something, but we have to go and prove it before we can be absolutely certain.*0134

*Proof is this really integral part to how mathematics works.*0140

*As an example, consider the following: in the 1600s, a mathematician named Fermat noticed a pattern.*0145

*It seemed to him that all numbers of the form below were prime numbers.*0150

*It is p _{n}, the n^{th} Fermat number, 2 to the 2 to the n plus 1, where n is a natural number*0154

*(0, 1, 2...working our way up)...if we have p _{0}, then that would be equal to 2 to the 2 to the 0 plus 1.*0162

*What is 2 ^{20}? Well, 2 to the 0...any number raised to the 0 is 1, so it is 2 to the 1.*0168

*So, we have 2 to the 2 to the 0 plus 1...2 to the 1, plus 1...that gets us 3; and indeed, 3 is a prime number.*0174

*Next, the next Fermat number would be 2 ^{21} + 1; that gets us 5, and indeed, that is a prime number.*0181

*The next one would be 2 to the 2 to the 2, plus 1; that is going to come out to be 17; indeed, that is a prime number.*0189

*Now, we are starting to get to a place where we can't immediately see that they are prime.*0194

*But 2 ^{23} + 1 is 257; and you can check--that does end up being prime.*0197

*The next one would be 2 to the 2 to the 4 plus 1, which comes out to be 65537;*0203

*and indeed, if you work at it, you can eventually check by hand that this does come out to be a prime number, as well.*0208

*So, Fermat could verify that this was true for the values of 0, 1, 2, 3, and 4--raising 2 to the 2 to the 0, to the 1, to the 2, to the 3, to the 4, plus 1.*0214

*Each one of these came out to be a prime number.*0226

*So, he could check by hand that you are able to make primes for these first five Fermat numbers (0, 1, 2, 3, 4).*0229

*He was able to show for sure that they do make primes.*0238

*However, the next Fermat number was too large for him to check, and he couldn't figure out a way to prove it prime.*0242

*The next one is 2 ^{25}, plus 1, which is equal to a huge 4 billion, 294 million, 967 thousand, 297--a big number.*0246

*That is going to be really hard to check by hand; and Fermat wasn't able to check by hand.*0256

*So, he couldn't figure out a clever way to prove for sure that it was prime without having to check by hand.*0260

*And it was too big for him to check by hand, so he couldn't show that it was prime.*0265

*Nonetheless, he had noticed a pattern; so he made a conjecture, that is, a hypothesis--an expectation,*0268

*of how things will work: that all numbers of the form 2 ^{2n} + 1 are prime.*0274

*But noticing a pattern does not necessarily prove it to be true.*0281

*This was a conjecture, but we didn't know for sure whether it was going to end up being a true conjecture*0284

*or a false conjecture--if it was going to end up being disproven.*0288

*It was not until the 1700s that we knew whether or not the conjecture was true.*0292

*Another mathematician, named Euler, showed that the sixth Fermat number, p _{5}, could be factored.*0296

*So, 2 to the 2 to the 5, plus 1, which comes out to be 4 billion, 294 million, 967 thousand, 297, can be broken down*0303

*into the two numbers 641 times 6 million, 700 thousand, 417.*0310

*So, since that Fermat number can be broken down into two factors, that means that it is not a prime number.*0316

*Thus, Euler had shown that not all Fermat numbers are prime, because there is at least one of them that can be broken into factors.*0323

*Thus, he had proven the conjecture false; he had shown that there was a counterexample.*0330

*So, that conjecture that Fermat had originally thought, that 2 to the 2 to the n plus 1 was prime--that is not true.*0334

*We have proven it to not be true.*0341

*It is relatively easy to prove that something is not true; you only need a single counterexample--*0344

*one counterexample that cancels out and says, "No, here is a way that you can't have that work."*0349

*That proves that that does not work; but how can we prove that a pattern will hold forever,*0353

*that we have some sequence of things that is going to always end up being the case?*0358

*We can do this with mathematical induction.*0363

*There are other ways to do this; you can make logical arguments in other ways.*0365

*But a good way to do this is with mathematical induction; it often works well.*0368

*Before formally stating the principle of mathematical induction, let's look at a metaphor to help us understand how induction works.*0372

*Here is our metaphor: let's imagine that we have an infinitely long line of dominoes, and they are stood up on their ends, like in this picture here.*0379

*Domino, domino, domino, domino, domino...it is like if we were setting up a bunch of dominoes*0387

*to push it over and have (thump, thump, thump, thump, thump, thump, thump...) falling-over dominoes.*0391

*That is the image that we want to have in our mind.*0395

*OK, we could name the dominoes, based on their location in line.*0397

*The very first domino that would start on the line, on the very left side, we could call d _{1}.*0401

*Here would be our d _{1}, our first domino.*0407

*The next domino we could call d _{2}; our second domino is d_{2}, and so on.*0409

*Here would be d _{3} and d_{4}, and it is going to just continue on in that pattern.*0414

*So, any domino...there exists some n that we can name any domino with.*0418

*We talk about some domino: there is some number that we can associate with it,*0422

*because we can just count up from the beginning and see what number we have to count to, to get to that domino.*0425

*That means that we can name any given domino.*0429

*All right, we have two guarantees: consider if we had two guarantees: the first guarantee*0432

*is that the first domino, d _{1}, will definitely fall over.*0440

*We are going to be absolutely certain that d _{1} is going to fall over.*0445

*Our first domino, d _{1}, is for sure going to fall over; we know that our very first domino in the line is going to fall over.*0449

*It is going to get pushed somehow; a gust of wind is going to happen...an earthquake...but something will certainly happen.*0457

*Who knows what it is, but we are guaranteed that it will fall over, for sure.*0462

*We know that our very first one is going to fall over; that is our first guarantee.*0466

*Our second guarantee is that, given any sequential pair, any pair of dominoes*0470

*(we could, for example, talk about some d _{k} and d_{k + 1} for any positive integer k,*0477

*some d _{k} in the line, and then the next one would be called d_{k + 1}--*0482

*if we are at the k spot, the k + 1 would be the next spot), if d _{k} falls,*0486

*if the domino on the left falls (d _{k} is the domino on the left), then the next domino in line,*0490

*d _{k + 1}, will also fall; this is our next guarantee.*0501

*So, if the domino on the left falls, then the next domino will fall, as well.*0506

*We are going to get falling from the next domino; if d _{k} falls, d_{k + 1} must fall.*0516

*We have here that d _{k} falls; and then, at the next one...we have d_{k} falls;*0522

*if d _{k} falls, d_{k + 1} must also fall.*0527

*If one domino falls, the next domino in line is always guaranteed to fall.*0531

*We have this guarantee that the dominoes do, indeed, always push each other over for any pair of dominoes that we end up looking at.*0535

*All right, we have these two things for sure: we have two guarantees and this infinite line of dominoes.*0543

*There is some line of dominoes, and the two guarantees: that the first domino, d _{1},*0549

*is definitely going to fall over; and that, if some domino, some d _{k} falls over,*0554

*it will cause the next domino, d _{k + 1}, to also fall over.*0560

*Given these two guarantees, we now know that absolutely all of the dominoes in our infinitely long line of dominoes will fall over.*0564

*We know for sure that all of them are going to fall over.*0575

*Why? Well, because, by the first guarantee, we know that d _{1} falls.*0578

*We know that the very first one in the line has to fall, because we are guaranteed that it is going to fall.*0584

*Then, by the second guarantee, if some domino falls, then we know that the next domino falls.*0588

*By our first guarantee, we know that d _{1} must fall.*0594

*But by the second guarantee, we know that d _{2} must fall, because d_{1} is the one before d_{2}.*0597

*So, d _{2} must now fall, as well; then, by our second guarantee, once again,*0602

*since d _{2} just fell, we know that d_{3} must fall.*0606

*Then, by our second guarantee, again, we know that since d _{3} just fell, we know that d_{4} must fall.*0609

*And then, since d _{4} just fell, d_{5} must fall; d_{6} must fall; d_{7} must fall;*0614

*d _{8}, d_{9}, d_{10}, forever and ever and ever.*0618

*Thus, all of the dominoes must fall over; we know that every single domino must fall over,*0620

*because we are guaranteed that the first domino is going to fall, and we know that every domino*0626

*after a domino that has fallen will fall as well.*0630

*So, since d _{1} falls, we know that d_{2} must fall; we know that d_{3} must fall;*0633

*and we can work our way out, going forever.*0636

*This is inductive thinking, step-by-step logic; this is the idea of mathematical induction,*0638

*that we have this first premise, that the definite thing is going to happen for the first thing;*0644

*and that, if something happens, we know that the next thing has to happen, as well.*0648

*We can start at d _{1}, and from that induction idea, we can move forward forever, stepping along.*0652

*Mathematical induction is extremely similar; this idea of using it in math is very, very much the same thing as this line of dominoes.*0658

*It is just that, instead of dominoes, we will work with statements; and instead of "falls over," we will say "is true."*0666

*But other than that, the logic behind it is exactly the same.*0673

*And I know that that might seem like a crazy thing to say--that we can connect dominoes and statements,*0676

*and we can connect falling over with being true; but really, the idea behind it is the same.*0680

*And we will see why in just a second.*0684

*It is that we have this one thing that starts it, and then we have this other guarantee that says that it keeps going forever and ever and ever.*0686

*All right, now we are ready to look at the principle.*0691

*The principle of mathematical induction is: let p _{1}, p_{2}, p_{3}, p_{4}...*0694

*going on...p _{n}...going on forever, be some infinitely long sequence of statements,*0700

*or just some sequence of statements, where n is a positive integer.*0705

*We are stepping forward, one statement at a time.*0708

*And we are guaranteed two things: if p _{1} is true, and if p_{k} is true for a positive integer k,*0711

*then p _{k + 1} must also be true; then we know that the statement p_{n} is true for all positive integers n.*0721

*Why is this the case? Well, it is very much the same thing as we just saw with the dominoes.*0729

*We have p _{1}; it is definitely true--the very first one (we have p_{1}, p_{2}, p_{3},*0732

*p _{4}, p_{5}...going on forever; we effectively have this infinitely long line of sequences).*0736

*And we are guaranteed, by our very first thing, that p _{1} has to be true; p_{1} is true.*0741

*Then, our next guarantee is that, if something is true, the next thing in line must be true.*0747

*Our first guarantee was that p _{1} is true; that means that p_{2},*0752

*since it is the next thing in line, must also be true.*0755

*That means, by that same guarantee, that the next thing in line is true, that p _{3} must be true;*0757

*p _{4} must be true; p_{5} must be true; p_{6} must be true.*0761

*And it goes on forever and ever and ever, and that is why we now know that p _{n} is going to be true for all positive integers n.*0763

*It is because, since the first thing in line was guaranteed by that first guarantee,*0771

*and the second thing is going to end up happening because of that second guarantee,*0775

*and then the third one will happen because of the second guarantee again,*0778

*and then the fourth thing will happen because of the second guarantee again...*0782

*we can keep using that step, step, step, step, step--that the second guarantee gives us.*0784

*We are able to step forever and ever and ever; we are able to have that infinitely many of these statements are going to end up being true.*0788

*All right, we often call the first step (that p _{1} is true) the base case,*0794

*because it is establishing the basis that we are working from.*0801

*It is the very first one in the line of true statements.*0803

*The second step is often called the inductive step, because it is the thing where the actual induction occurs--*0806

*that induction being "if 1, then 2," "if 2, then 3," so 1, then 2, then 3, then 4, then 5, then 6...*0813

*the fact that we can start at one place, and then step forever forward.*0821

*In the inductive step, the assumption, if p _{k} is true (this part right here, the "if p_{k} is true")*0824

*is called the inductive hypothesis, because it is the hypothesis that we use to show that p_{k + 1} will also be true.*0831

*We have to have this assumption that, if this thing happens, then this other thing will happen.*0839

*It is just like, with the dominoes, we say, "If some domino falls over, then this thing is going to happen in response."*0844

*But now, we are talking in terms of truth: "If this thing is true, then the next thing down the line must be true, as well."*0849

*All right, before we keep going, I want to have a quick remark on statements.*0856

*The principle of mathematical induction is based on statements.*0859

*We might be tempted to assume that any statement we see written out will automatically be true.*0863

*But that is not necessarily the case: just because you see something written out does not mean that you want to assume it will always, always be true.*0868

*Don't believe everything you read.*0873

*A statement, like in English, is just a string of words and/or symbols.*0875

*For example, the statement "Ice cream is made of hair" is most emphatically not true.*0879

*Ice cream is not made of hair; that is not true.*0884

*But it is still a statement, albeit a false statement.*0887

*Just because something is said does not mean that it is always going to end up being true.*0891

*Similarly, in math, the statement 3 + 5 + 7 = 10 is false; that is not true: 3 + 5 + 7 is not equal to 10.*0895

*But it is still a statement--just not a true statement.*0903

*3 + 5 + 7 is actually equal to 15, so we know that this one here is a false statement.*0905

*Most of the time, when we are working in math, we are always allowed to assume that the statements we are working with are true,*0911

*because they are given to us directly from the problem, and we are not told to question them.*0916

*We are saying, "Start with this thing and work with it."*0919

*Or we are working on the problem from the beginning (like a word problem), and we see, from the information that we are given,*0922

*that we can use logic to say, "Oh, this must definitely be the case; this must definitely be the case."*0926

*We are able to work with these things and be certain of their truth.*0931

*But just because something is said does not necessarily mean that it is always going to be true.*0933

*Everything that we have dealt with so far in math--we have been able to assume the truth of things,*0937

*because we know that we weren't being given lies.*0941

*But now, if we are just talking about statements in general, we have to evaluate their truth before we can trust them.*0944

*When we are working with mathematical induction, it is our job to not only set up the statements, p _{n},*0950

*but to also prove that the statements are going to be true statements.*0956

*We are not just going to get the statements and assume that they are true.*0961

*We have to get the statements, and then show for sure that they end up being true.*0963

*And occasionally, we might discover that the statements we have actually end up being false statements,*0967

*at which point we will have to go back to the beginning and figure out a way that we can state it truthfully;*0971

*or that will end up being the answer--the fact that it is actually not true.*0974

*But generally, we are going to end up showing that it is true.*0977

*Now, of course, if we want to show that n goes on infinitely, that all p _{n} for any 1, 2, 3, 4, going on forever--*0979

*that they are all true--we can't prove each one of them by hand, because we can't prove an infinite number of things.*0985

*We are not going to be able to have an infinite amount of time to prove an infinite number of things.*0990

*So instead, we have to use some way to be able to show all of them at once.*0995

*We can either use some sort of clever logical argument, or we can use proof by mathematical induction,*0999

*where we can show that the first step will end up always being true,*1003

*and that, if you have some step, the next thing is going to end up being true, to work our way out infinitely,*1006

*like that line of dominoes, like we were just talking about a few moments ago.*1011

*All right, how do we use mathematical induction?*1015

*If we are going to use induction to prove that some statement, p _{n}, is true for all n, we must prove two things:*1017

*first, the base case, that p _{1} is true--that our very first statement is a true statement;*1022

*and then, we have to do the inductive step: that if some p _{k} is true,*1029

*the next one in line, p _{k + 1}, must also be true.*1033

*So, that means, when we are working with proof by induction, that we have at least two separate steps.*1036

*We have two separate things that we have to deal with: proving the base case and proving the inductive step.*1042

*We have to show each one of these.*1048

*I am going to strongly recommend noting which one you are working on and making it so that you can keep the parts separate.*1049

*How you work on the base case normally isn't going to really help you deal with the inductive step.*1055

*How you work on the inductive step normally isn't really going to help you deal with the base case.*1058

*So, just write "base case" and prove your base case; then write "inductive step"; then prove your inductive step.*1061

*It will help you keep track of what you are doing; it will help keep it from being confusing.*1066

*And it will help other people who read your work in the future to understand what happened there.*1069

*In general, proving the base case almost always is going to be easier by far.*1073

*Normally, we just end up simplifying the statement--whatever this p _{1} statement ends up being;*1078

*and we verify that it is, indeed, a true statement--it is just making sure that, yes, this is true.*1083

*The tricky part normally ends up being dealing with the inductive step.*1089

*To prove the inductive step, we must first assume the inductive hypothesis, "p _{k} is true."*1093

*We have to start by assuming that if p _{k} is true...we have to say,*1098

*"OK, p _{k} is true; now let's show that p_{k + 1} is also going to be true."*1102

*Once we make this assumption, we somehow have to work to prove that p _{k + 1} must then also be true.*1108

*Now, notice: we haven't actually proven p _{k} to be true; we are just asking ourselves,*1112

*"If p _{k} were true, would p_{k + 1} also be true?"*1118

*We are saying, "If we had this place that we could start from, would the next thing be true?"*1122

*It is like the dominoes: if this domino were to fall over, would the next one in line fall over?*1125

*That is all we need for mathematical induction: we don't have to prove that the one in the middle will fall over.*1130

*We just have to say, "Well, if it were to fall over, would the next one fall over, as well?"*1133

*All right, it helps a lot to somehow include part of the statement for p _{k} when we are writing out p_{k + 1}.*1138

*This is because we are almost inevitably going to end up using the inductive hypothesis.*1146

*We have to use this inductive hypothesis, "p _{k} is true."*1151

*Otherwise, we wouldn't have needed to talk about p _{k} being true, to show that p_{k + 1} is true.*1154

*So, we are going to end up using that inductive hypothesis, that p _{k} is true.*1159

*So, we have to have some way of talking about it in our p _{k + 1} statement.*1163

*We can't use our hypothesis about p _{k} unless it somehow appears in p_{k + 1}.*1167

*That means, when we end up writing out the p _{k + 1} statement, that we have to figure out some way*1175

*to make p _{k}, or some portion of p_{k}, show up in some way,*1178

*so that we can apply that inductive hypothesis and use what we have assumed to be true.*1182

*It is important to have that end up showing up.*1188

*We will see how that occurs as we are actually working through problems and examples.*1190

*All right, all of this is going to make a lot more sense once we see it in action.*1194

*So, if it seems a little bit confusing right now, just follow it through; it is going to make much more sense as we actually work through what is going on.*1197

*All right, consider the following formula, which we proved in the lesson Arithmetic Sequences and Series:*1203

*we proved that adding the numbers 1 + 2 + 3 + ... up until we get to + n, all of the numbers consecutively,*1209

*from 1 up until some n that we choose, is equal to n times n + 1 divided by 2.*1215

*Previously, we proved this by a logical argument that involved equations and elimination.*1222

*Adding up two equations (if you watched that lesson), we were able to prove it through logical argument.*1227

*But we also could prove it through mathematical induction; let's see another way to prove this, through mathematical induction.*1231

*We can see that the above equation is effectively our statement, p _{n}; we can turn this into our statement, p_{n}, this right here.*1238

*How would this work? Well, our first statement, p _{1}, would be if we went from 1 up until an n of 1 (p_{1}, so 1 up until 1).*1246

*Well, that is just going to end up being 1; so 1 added to itself--is that, indeed, equal to 1 times 1 + 1 over 2?*1254

*That is the first statement: the first statement is that 1 is equal to 1 times 1 + 1 over 2.*1261

*Our next statement, at p _{2}, would be 1 +...up until 2, so that is just going to be 1 + 2;*1266

*and that is going to be equal...the statement says that it is equal;*1271

*it will be up to us to verify that this actually ends up working out...to 2 times 2 + 1 over 2.*1274

*And then, the next one, p _{3}, would be equal to 1 + 2 + 3...we get up to the third;*1279

*and it is saying...the statement is that that is, indeed, equal to 3 times 3 + 1 over 2.*1284

*And finally, the really interesting one here is p _{n}, which is adding all the numbers from 1 up until n,*1288

*and that that is equal to n times n + 1 over 2.*1294

*So, this is our statement, p _{n}--this way of writing it out here.*1296

*I didn't mean to cut through that 2.*1301

*To prove by induction that the statement p _{n} = 1 added to all the numbers up until n is equal to n times n + 1 over 2--*1303

*to prove this as true for all positive integers, if we are going to use proof by induction, we have to prove two things.*1310

*We have to prove both the base case, p _{1}, and the inductive step, that p_{k} implies p_{k + 1}.*1314

*The truth of some p _{k} in the middle implies that p_{k + 1}, the next one down the line, also has to be true.*1322

*Let's begin with the base case; the base case is normally the easier thing, by far.*1328

*Our p _{1} statement was that 1 is equal to 1 times 1 + 1 over 2.*1331

*Now, that is just a statement; once again, it is up to us to verify the truth of the statement.*1337

*So, we will write in the middle here this little equals sign with a question mark, because we don't actually know for sure that it is equal.*1341

*The statement said that 1 is equal to 1 times 1 + 1 over 2; but we don't know for sure that that is true.*1347

*The statement could be lying to us; it is up to us to figure out if this is, indeed, true;*1353

*are the left side and the right side actually equal to each other?*1357

*We work this out: we have 1; is it equal to...let's check: 1 times 1 + 1 over 2...1 compared to 1 times 2/2 (1 + 1 is 2), and then*1361

*that simplifies; the 2's cancel out, and we have 1 = 1; and indeed, that is true.*1370

*So, that means that our base case checks out; we have shown that the base case is definitely true.*1374

*Next, we move on to the inductive step: we write "inductive step," so that we see where we are.*1380

*The very first thing that we always do with the inductive step is write out our inductive hypothesis.*1385

*We say, "If p _{k} is true..." so we assume that p_{k} (which would be 1 + 2 + 3...*1389

*all the way up until we get to some k, is equal to k times k + 1 over 2) is true.*1394

*We are assuming that this thing is true: p _{k}, which is the statement 1 + 2 + 3...up until + k = k + (k + 1)/2--*1399

*we can just take this as cold, hard fact; it is the assumption that if this domino were to fall,*1408

*now we just need to work on the next domino falling.*1413

*We don't have to prove for certain that this one is true; we are allowed to assume it, because it works in combination with the first guarantee.*1415

*All right, so we have this assumed as true.*1421

*With the inductive hypothesis in mind, we want to show*1423

*(our inductive hypothesis is right here; it is up to us to show) that p _{k + 1} must also be true.*1426

*We can write out p _{k + 1} as 1 + 2 + 3 +...up until...well, now we are going up to k + 1,*1432

*so up until + k + 1...and we can plug in k + 1 times k + 1 + 1, all over 2.*1438

*So, we see that this is what the statement would be.*1444

*However, we can't really see how p _{k} shows up in here;*1447

*how does something in this portion right here show up?--because remember what we talked about before.*1450

*We are going to have to use our inductive hypothesis; that is what the inductive hypothesis is there for.*1455

*If we could prove this without an inductive hypothesis, why are we doing induction?*1459

*So, we have to use that inductive hypothesis somehow to be able to apply it here,*1463

*so that we can show that p _{k + 1} must be true.*1467

*We need to get some way to see some portion of p _{k} appear.*1472

*We realize that we can rewrite what we have here: we could write p _{k + 1} as it is above, but we can't easily see p_{k} in it.*1476

*So instead, we write it out as p _{k + 1} = 1 + 2 + 3 + ... + k + k + 1.*1484

*How can we do this? Well, we know that there had to be k in here, because it is all the numbers from 1 up until k + 1.*1493

*So, k has to be included in there, because it is the number before k + 1.*1498

*k + 1 minus 1 is k; so it has to be the number before it, so it has to be included somewhere in our ellipsis in our continuing pattern.*1502

*So, we can write it out; now that means that we have p _{k} showing up right here.*1510

*1 + 2 + 3...up until k...look, that is this right here; so we can bring this to bear.*1516

*And we just simplified the right side a little bit; that just ends up being the same thing.*1522

*k + 1 times k + 1 + 1 is just k + 1 times k + 2, over 2; we just simplified the right side.*1526

*All right, we have our inductive hypothesis, that 1 + 2 + 3 + ... + k = k times k + 1 over 2.*1531

*We are assuming that that is true, and it is our job to show that 1 + 2 + 3 up until + k + 1 is equal to k + 1 times k + 2 over 2.*1538

*So, we want to verify the statement below; we want to show that this is not a question mark--*1547

*that it is, indeed, that the left side and the right side are equal to each other, for sure.*1552

*We want to verify this; we want to make that question mark be absolutely an equals sign.*1556

*What we notice is that we have p _{k} here--our inductive hypothesis, p_{k}.*1561

*We can substitute p _{k}, our hypothesis; and what we have here is the same thing as what we have here.*1567

*So, we can plug in; we can swap out this stuff right here.*1573

*Now, we have gotten our hypothesis into the game.*1576

*We have been able to plug it in; so now, we can start using it--we can work things out.*1579

*We are almost absolutely, certainly, going to use that inductive hypothesis; otherwise, we wouldn't need to be doing induction.*1582

*We bring the hypothesis to bear somehow.*1589

*We can plug it in, generally; and from here, we just have to simplify the equation.*1592

*It is not really an equation, because we don't actually know if the two sides are equal to each other, so it is not technically an equation.*1596

*But we can write it as this idea of "are they equal to each other? Let's see if they are the same thing, on either side."*1602

*And then, we can just verify that, if it does come out to be clearly the same on both sides, then we will know that p _{k + 1} is true.*1607

*If we can get rid of that equals sign in our equation, if we can turn it into just an equals, then we will know that, indeed, p _{k + 1} is true.*1616

*And we will have shown that p _{k + 1} is true from p_{k}, and we will have completed our inductive step.*1627

*OK, we just worked this out: what we had on the left side was k times k + 1 over 2, plus k + 1.*1632

*And then, on the right side, we had k + 1 times k + 2 over 2.*1638

*So, we expand: k times k + 1 gets us k ^{2} + k; we can put this over a fraction, so that we can have them over common denominators.*1641

*So, we have 2k + 2 over 2.*1648

*We expand the right side, k + 1 times k + 2; that is going to be k times k, k ^{2}, plus 2k + 1k, so 3k, plus 1 times 2, 2.*1650

*So, we get k ^{2} + 3k + 2, all over 2.*1659

*Now, we just combine these two fractions here, k ^{2} + k over 2, plus 2k + 2 over 2.*1662

*It is going to be k ^{2} + k + 2k + 2, all over 2, which simplifies to a nice k^{2} + 3k + 2, over 2,*1667

*which is equal to k ^{2} + 3k + 2 over 2, which is, indeed, definitely always going to be true.*1674

*So, we have just shown that, yes, our inductive step does work; we have proved the inductive step to be true.*1679

*If we have p _{k} true, then p_{k + 1} must be true, from our logic.*1684

*So, we have completed both steps: we have completed the base case (back a while), and we just completed the inductive step.*1690

*That means that we have completed both of the parts necessary for a proof by induction.*1695

*We have to prove both of those parts.*1699

*We now know that p _{n} is true for all n; that is, for any positive integer, we have that 1 + 2 + 3, up until + n, is equal to n times n + 1 over 2.*1701

*And I like to complete my proofs with a little square, just to say, "We have completed the proof; it is done."*1711

*And there we are; that is an example of how proof by induction works.*1718

*All right, at this level in math, you will often be directly told what to prove.*1721

*You will be given some formula or some statement, and it is going to say, "Go prove this."*1725

*You will be given something, and it will be your job to prove it, by induction, since this is a thing about proof by induction.*1729

*But in most of the things, if you are asked to prove something else, it would also just be "here is something; go prove it," like when you were in geometry class.*1734

*However, sometimes you won't be given a formula.*1740

*Instead, it is going to be your job to discover a pattern inside of that sequence, inside of what you are looking at;*1746

*and then create some sort of hypothetical formula that will describe that pattern, and finally to prove that your formula will always work.*1753

*So, the proof itself can be challenging; that is what we are working on.*1760

*But sometimes the hardest part isn't the proof that the proof by induction works, but just finding the pattern and turning it into a formula.*1763

*Sometimes, that is the hardest part: being able to look at what you have, figure out what the pattern here is,*1770

*and how you can turn this into a formula, how you can turn this into a statement that you can then go on to prove.*1775

*If you need to do this, and you find it difficult, I recommend checking out "Tips for finding patterns,"*1779

*which is one of the parts in the lesson Introduction to Sequences.*1784

*There are a lot of connections between finding the general term of a sequence and finding a formula, because they are both based on a sequence.*1787

*The formula is based on some sequence of statements, effectively.*1794

*And a sequence is based on some sequence of numbers; so there is a lot of connection between them.*1797

*This "Tips for finding patterns" inside of Introduction to Sequences--you will end up seeing a lot of things there.*1801

*A lot of the ideas there, you can apply to looking at formulas, so that is a really good thing to check out,*1807

*if you are having to work on that and you find it difficult.*1811

*All right, we are ready for some examples.*1814

*Prove that the below...*1816

*Oh, by the way, if you just skipped directly to the examples, you definitely, definitely, definitely, in this case,*1817

*want to go back to the working example first; so if you just skipped to this part directly, check out the working example first,*1821

*because it will explain what is going on here, as opposed to being confusing and just not having any meaning.*1826

*The working example will explain everything that is going on.*1831

*If you just watched the whole lesson, I'm sorry; I didn't mean to...I'm sorry about that.*1833

*Anyway, let's go on.*1836

*Prove that the below is true for any positive integer n.*1837

*We have 1 ^{2} + 2^{2} + 3^{2} + ... + n^{2} = n times n + 1 over 2n + 1.*1840

*This is effectively our statement p _{n}...not effectively; this is our statement p_{n}.*1849

*Adding all of the squares, 1 ^{2} + 2^{2}...up until n^{2}, is equal to n times (n + 1) times (2n + 1), all divided by 6.*1854

*Our first thing to do is to show that the base case ends up being true.*1862

*The base case would be what it would be if we plugged in a 1 for n, if it was just the first statement.*1867

*What would that end up looking like? That is going to be...proving that would be equivalent to showing*1871

*that these two sides are the same, that 1 ^{2} is equivalent to 1 (plugging in 1 for our n),*1876

*1 + 1, plugging in 1 for our n...2 times...plugging in 1 for our n...plus 1...all over 6.*1881

*Does this end up working out to be the same?*1887

*1 ^{2} is 1; what is on our right side? 1 times...1 + 1 is 2; 2 times 1, plus 1, would end up being 3, over 6.*1889

*Is 1, indeed, equal to 1 times 2 times 3...is 6...over 6?*1897

*And yes, indeed, that would be 1 = 1; so we just showed that our base case ends up being true.*1902

*The next thing that we want to work out is the inductive step.*1908

*What would our inductive step be? Well, always the first thing that happens in the inductive step is that we write out what our hypothesis is.*1911

*What is the thing we are assuming? The hypothesis: we are assuming that p _{k},*1918

*which would be 1 ^{2} + 2^{2}...up until we get to some k^{2}*1923

*(any positive integer k) is equal to k...we plug in k for n...k + 1, times 2k + 1, all over 6.*1928

*So, we assume that this is true; this is our assumption.*1938

*We can use this later; we can plug it in.*1941

*All right, we have our general thing here, p _{n}, 1^{2} + 2^{2} + 3^{2}...*1944

*up until n ^{2}, is equal to n times n + 1 times 2n + 1.*1948

*And our inductive hypothesis is just saying, "What if we looked at some k, and we assumed that at k, it was true?"*1951

*So now, we want to show--it is our job to now show--that p _{k + 1} is true.*1957

*It is our job to show that p _{k + 1} ends up being true.*1963

*Showing that p _{k + 1} is true is going to end up being equivalent to showing that 1^{2} + 2^{2} + ...*1967

*up until we get to (k + 1) ^{2}...now, here is the part...we don't want to put in (k + 1)^{2},*1978

*because we want to somehow have our p _{k} show up.*1984

*We are going to have to apply our hypothesis in there somewhere.*1987

*So, we want to have it show up.*1991

*We realize that up in 1 ^{2} + 2^{2} ... + (k + 1)^{2}, well, what would be right before that?*1992

*We go back, and instead of using (k + 1) ^{2} as the last thing, it would be easier to see in the pattern*1998

*what is really there, to make it easier, to substitute this: + k ^{2} + (k + 1)^{2}.*2003

*I will break this onto a different line, because now we are starting to get a little cramped.*2009

*We want to show (we don't know for certain; it is up to us to verify) that that would be...*2011

*swap in k + 1 now for n; so k + 1 times...k + 1 in here would be k + 2, times...k + 1 in here...2 times...k + 1 + 1, all divided by 6.*2016

*So, at this point, we say, "We have 1 ^{2} + 2^{2} + ... up until k^{2},*2032

*so we can swap that in for what is here at p _{k}, which is this thing right here"--we can now swap that in.*2037

*Now, we are going to move over here, so we have a little bit more room.*2045

*k times k + 1 times 2k + 1, all over 6: this is our inductive hypothesis, which we assumed is true, so we can use it as we want;*2049

*plus...what is the thing that we still have left over?*2061

*We still have (k + 1) ^{2} left over; we didn't substitute out for that; so, plus k + 1 squared.*2062

*And it is now our job to show that that is, indeed, equal to what was on the other side, which is k + 1 times k + 2 times 2k + 1 + 1.*2069

*I will simplify that a little bit: that will be 2k + 2 + 1; so that would be 2k + 3, all over 6.*2079

*OK, at this point, to show that they end up being the same on either side of that...*2086

*"maybe-it-is," to show that each side is the same, that the sides are equivalent,*2091

*we can just end up simplifying each of the sides, working with each side on their own.*2095

*We work with expanding this part over here; k times...k + 1 times 2k + 1...k times 2k gets us 2k ^{2};*2099

*k times 1 is k, plus 1 times 2k, so + 3k; 1 times 1...plus 1; all over 6; plus...*2107

*let's multiply this part by 6/6, because we know that we will want to put them together*2115

*into a single fraction, so that we can compare the two things;*2120

*(k + 1) ^{2} is (k + 1) times (k + 1); it becomes k^{2} + 2k + 1.*2122

*And is that, indeed, equal to...let's expand the right side; expand the far right first.*2129

*k + 1 times k + 2 times 2k + 3...k times 2k gets us 2k ^{2}; k times 3 is 3k; 2 times 2k is 4k;*2133

*so 3k + 4k is 7k; 2 times 3 is + 6; all divided by 6.*2141

*So, we can keep expanding over here; k times 2k ^{2} is 2k^{3}, plus 3k^{2}, plus k, all over 6.*2149

*Plus...6k ^{2} + 12k + 6, all over 6; and is that equal to (k + 1) times (2k^{2} + 7k + 6)?*2160

*OK, how is this one going? I am going to do this one partially in my head.*2174

*If you get lost here, just write it out, and you will see how it worked.*2178

*k times 2k ^{2} is going to come out to be 2k^{3}.*2181

*k times 7k is 7k ^{2}; plus...1 times 2k^{2}...7k^{2} + 2k^{2} is 9k^{2};*2184

*k times 6 is 6k; 1 times 7k is 7k; 7k + 6k is 13k; and 1 times 6 is +6, all over 6.*2191

*And finally, if we combine our two fractions on the left, then 2k ^{3}...*2201

*everything will be divided by 6 over here...2k ^{3} plus nothing on our other fraction,*2206

*so that is just that...3k ^{2} + 6k^{2}...we get 9k^{2};*2211

*k + 12k + 13k...there are no constants on our left fraction, plus the one on our right fraction, so + 6.*2216

*And is that, indeed, equal to 2k ^{3} + 9k^{2}?*2222

*We see that that is, indeed, the exact same thing; thus, our inductive step right here*2226

*(not our inductive hypothesis, but our inductive step) just checked out.*2231

*So, we have now shown that the base case checks out; the inductive hypothesis checks out.*2234

*So, combined, they show that this here is always true.*2238

*We have just shown that combining these two things (the base case, p _{1}, being true,*2245

*and if p _{k} is true--our inductive hypothesis--then p_{k + 1} is true, which we just showed here)--*2249

*we combined those two things, so now we have shown that p _{n} is true for all things:*2255

*that 1 ^{2} + 2^{2} + 3^{2}...up until + n^{2} is equal to n(n + 1)(2n + 1), all divided by 6.*2258

*We have completed our proof by induction.*2265

*The second example: Show that, for n = 1, 2, 3...forever, that n ^{3} + 2n is divisible by 3.*2269

*So really, this is our statement, p _{n}: p_{n} is "n^{3} + 2n is divisible by 3."*2279

*The first thing that we always have to do: we have to start by showing the base case.*2285

*Our base case first: the base case is showing that the p _{1} statement would be true.*2289

*Verifying p _{1} is the same thing as verifying that 1^{3} + 2(1) is divisible by 3.*2295

*1 ^{3} + 2(1) is 1 + 2, or 3; that is divisible by 3--that checks out, so our base case just checked out; great.*2309

*Next, we want to work on the inductive step.*2318

*Always, the first thing we do in our inductive step is to write what our hypothesis is.*2324

*What is the assumption that we can work from?*2328

*Our hypothesis is going to be that p _{k} ends up being true.*2331

*What is p _{k}? p_{k} would be if we plugged in k for our n here: k^{3} + 2k is divisible by 3.*2336

*This is our starting assumption: that k ^{3} + 2k is divisible by 3.*2349

*At this point, we now want to show that p _{k + 1} is true.*2353

*Showing that p _{k + 1} is true is going to be the same thing as showing*2364

*that k + 1 (plugging in k + 1 for n now), cubed, plus 2(k + 1) for n now, is divisible by 3.*2367

*So now, we just need to show...if this is divisible by 3, then we will have proven our inductive step, as well.*2378

*So, we will have shown the whole thing.*2384

*From here on, let's just take a close look at (k + 1) ^{3} + 2(k + 1).*2385

*Hopefully, we will have enough room to work this out.*2397

*(k + 1) ^{3}...well, we can write that as (k + 1)(k + 1)^{2}.*2399

*What is (k + 1) ^{2}? That is k^{2} + 2k + 1.*2402

*Plus...2 times (k + 1)...that is 2k + 2.*2407

*k + 1 times k ^{2} + 2k + 1...well, k times k^{2} is going to be k^{3};*2411

*k times 2k is 2k ^{2}, plus 1 times k^{2}, so + 3k^{2};*2416

*k times 1...+ 1k; plus 1 times 2k is 2k, so + 3k total; plus 1 times 1 is 1;*2421

*also, in the next lesson, when we talk about the binomial theorem, we will recognize, "Oh, yes, that is definitely how it has to expand."*2428

*Plus 2k + 2...OK, so at this point, we can realize, "What was our hypothesis? Our hypothesis was that k ^{3} + 2k is definitely divisible by 3."*2433

*Look: here is k ^{3}; here is 2k; let's bring them together.*2444

*Now, we have k ^{3} + 2k; and we will put everything else on the other side.*2447

*So, 3k ^{2} + 3k...and we have a 1 here and a 2 here, so that combines to + 3.*2454

*Now, we can look at each part of this independently.*2461

*k ^{3} + 2k is a thing; plus...and over here, we have a 3 here, a 3 here, and a 3 here;*2463

*so we can pull a 3 out; 3 comes out of k ^{2} + k + 1.*2470

*Now, at this point, we realize--look, by our inductive hypothesis, we knew that this is divisible by 3.*2476

*We know that that is divisible by 3; furthermore, we have 3 times k ^{2} + k + 1;*2484

*well, anything that we end up multiplying by 3 on it...well, that already has a factor of 3 multiplied in.*2490

*So, it must be divisible by 3; so that means both parts that we are adding together are divisible by 3.*2496

*If both parts that we add together are divisible by 3, then it must be that the entire thing is divisible by 3.*2504

*If something over here is divisible by 3, and something over here is divisible by 3, well, that means that I can divide this thing by 3;*2510

*I can divide this thing by 3; so even when we put them together, I can still divide the thing by 3.*2514

*Since both parts are divisible by 3, that means that (k + 1) ^{3} + 2(k + 1),*2518

*which we just showed, has to be divisible by 3.*2524

*So, we have just shown that, if p _{k} is true, then p_{k + 1} is true.*2526

*So, we have now shown the inductive step; since we have shown that p _{1} is true,*2530

*and if something in the middle is true, then the next thing is true;*2535

*then p _{1} being true implies that p_{2} must be true, by our inductive step,*2538

*which implies that p _{3} must be true, by our inductive step; p_{4}, p_{5}, p_{6}, p_{7}...*2541

*So, we know that, forever and always, n ^{3} + 2n is divisible by 3; we have completed our proof by induction.*2545

*The next proof, the last example: Come up with a formula that gives the value of the n ^{th} partial sum*2554

*of the sequence below: 1, 3, 5, 7, 9... then prove that your formula always works.*2559

*The first few partial sums of the sequence are below.*2565

*Our first partial sum would be just adding 1 together, so that is 1.*2568

*Our next partial sum would be adding just 3 onto what we had before, so that would be 1 + 3.*2572

*The next thing would be 5, so 1 + 3 + 5.*2577

*The next thing would be 1 + 3 + 5 + 7; the next thing would be 9; let's write that out, as well: 1 + 3 + 5 + 7 + 9.*2579

*If we were to keep going with this pattern, what would be next?*2588

*Well, that would be 11 next; we are adding by 2 each time, so 1 + 3 + 5 + 7 + 9 + 11.*2590

*Let's see if we can figure out what the pattern going on here is.*2599

*1 on its own--well, that is just 1.*2601

*1 + 3 is 4; 1 + 3 + 5 is 9; add on another 7: 7 + 9 is 16; add on another 9; that is 25; add on another 11; that is 36.*2603

*We have an idea of what the formula is: it looks like the n ^{th} partial sum is going to be equal to n^{2}; great.*2618

*What we have here is 1 + 3 + 5 + ... + something...whatever we end on...is equal to n ^{2}.*2629

*We need to figure out what we end on; how do we call out each member of this sequence?*2644

*Well, we can remember what we did in arithmetic sequences.*2648

*We see that we have 1 as our starting place; we add by 2 each time.*2651

*So, we could realize that the n ^{th} term here, a_{n}, is equal to 2n - 1.*2655

*We verify this: n at 1 gets us 1; n at 2 would get us 3; n at 3 would get us 5; so this works out.*2664

*We see that what we are going up to is 2n - 1.*2670

*So, our statement, the p _{n} statement, is that 1 + 3 + 5, working up until 2n - 1, is equal to n^{2}, for any n.*2674

*So, that is what we have figured out that our formula is for how we are getting these partial sums.*2688

*As we add up more and more terms of this sequence, we have now figured out our formula.*2694

*We have figured out how this pattern of adding things up comes to be.*2698

*We see that we have n ^{2} coming out, if we do this each time.*2705

*On the first term, n = 1, we have 1; at n = 2, we have 4; n = 3...*2709

*We see that, each time, it is just squaring that number.*2714

*We also have to figure out what the sequence of the things looks like, because we have to be able to figure out what we end on.*2717

*We have to be able to say what the last thing is, so that we can actually work with having a left side and a right side to our statement's equation.*2721

*At this point, we are now ready to prove this.*2728

*All right, so now it is just up to us to prove that this is, indeed, true: that our statement p _{n} is true for any value of n:*2731

*that 1 + 3 + 5...up until + 2n - 1 is equal to n ^{2}, no matter what n we put in, as long as n is a positive integer.*2739

*So, the first thing to prove: always prove the base case first, because it is almost always easier.*2746

*It also helps you understand how the thing comes together.*2750

*So, the base case: showing that p _{1} is true is going to be the same thing as showing that 1,*2752

*added up until...well, we just add it up to 1, so that is just 1 on the left side--is that equal to 1 ^{2}?*2757

*Yes, 1 is equal to 1; that was pretty easy.*2764

*So, there is our base case, finished.*2766

*Next, we do the inductive step; now we want to show that the inductive step is going to end up being true.*2768

*The first thing that we always do: we assume our hypothesis first; what is our hypothesis going to be?*2774

*Our hypothesis will be that p _{k} is true.*2780

*What is the statement p _{k}? Well, that would be 1 + 3 + ... up until we get to +...plug in k for n...2k - 1 = k^{2}.*2783

*So, we are assuming that 1 + 3 + ... + 2k - 1 is equal to k ^{2}.*2794

*OK, with that assumption that this thing is true, we need now to show that k + 1 is going to be true, as well.*2800

*So now, we want to show that k + 1 is true.*2805

*Showing that k + 1 is true is going to be equivalent to showing that 1 + 3 + ... + 2k - 1...*2811

*I'm sorry, it is not 2k - 1; we are going to swap out k + 1 for n here, so 2 times (k + 1) - 1, equals k + 1,*2821

*swapping out that n here, as well, for k + 1, squared.*2830

*Now, remember: we want to have our hypothesis show up somewhere.*2834

*We have to get our hypothesis to show up somewhere.*2838

*So, we realize that that is really this part up here.*2840

*So, we can rewrite this as 1 + 3 + ... until we get to back a step of two...so that would be 2k - 1;*2843

*forward a step by 2...we see that that would be 2k + 1; if we work out this value here,*2855

*we end up seeing that it is the same thing here; 2k + 2 - 1 is just 2k + 1.*2862

*And we want to show that that is equal to (k + 1) ^{2}.*2866

*OK, we bring this up here; and on the way, we are going to say, "Right here, from here to here, we assumed up here that this was true."*2870

*That means that what we have in the thing we are trying to show, p _{k + 1}, that part of it, is going to just be equal to k^{2}, right here.*2885

*So, we can swap out k ^{2} here; so now we have k^{2} plus what still remains; that is 2k + 1.*2894

*And we want to show that this is true, so it is a question mark here.*2902

*We don't know for sure that it is true yet; it is up to us to show that it ends up being true.*2904

*Plus what remained there, 2k + 1: is that equal to (k + 1) ^{2}?*2908

*Well, let's just simplify it: we have k ^{2}; we expand this; well, k^{2} + (2k + 1)...that is just 2k + 1;*2916

*is that equal to...what do we get when we expand (k + 1) ^{2}?*2923

*Well, that is k ^{2} + 2k + 1; we end up seeing that that is indeed true.*2926

*That is always going to end up being true, so we have shown that our inductive step is true.*2933

*With this hypothesis in mind, we know that the next thing down the line...*2938

*with p _{k} being true, we know that p_{k + 1} must be true.*2941

*Because we know that our base case is true (p _{1} is true), and we know that if something is true,*2945

*then the next thing has to be true; then since p _{1} is true, the next thing must be true.*2949

*p _{2} is true; p_{3} is true; p_{4} is true; p_{5} is true; p_{6} is true.*2953

*And the fireworks keep going forever and ever; we see that everything is always true.*2957

*We have that this statement ends up being true for absolutely every single n that we would plug into it.*2961

*We have completed the proof; our proof is done--pretty cool.*2968

*The only really challenging part there--that wasn't that difficult of a proof by induction, compared to the ones that we did previously--*2972

*the challenging part there was being able to figure out what that formula was in the first place.*2977

*So, once again, if you have difficulty with that, I recommend checking out the Arithmetic Sequences and Series.*2981

*There is that section, "Tips on finding patterns," that will really help you see how to find patterns; there is a lot of good stuff in there.*2985

*All right, we will see you at Educator.com later--goodbye!*2991

## Start Learning Now

Our free lessons will get you started (Adobe Flash

Sign up for Educator.com^{®}required).Get immediate access to our entire library.

## Membership Overview

Unlimited access to our entire library of courses.Learn at your own pace... anytime, anywhere!