Sign In | Subscribe
Start learning today, and be successful in your academic & professional career. Start Today!
Loading video...
This is a quick preview of the lesson. For full access, please Log In or Sign up.
For more information, please see full course syllabus of Math Analysis
  • Discussion

  • Study Guides

  • Download Lecture Slides

  • Table of Contents

  • Transcription

  • Related Books

Bookmark and Share

Start Learning Now

Our free lessons will get you started (Adobe Flash® required).
Get immediate access to our entire library.

Sign up for

Membership Overview

  • Unlimited access to our entire library of courses.
  • Search and jump to exactly what you want to learn.
  • *Ask questions and get answers from the community and our teachers!
  • Practice questions with step-by-step solutions.
  • Download lesson files for programming and software training practice.
  • Track your course viewing progress.
  • Download lecture slides for taking notes.
  • Learn at your own pace... anytime, anywhere!

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,
    1. The first domino will fall over;
    2. If a domino falls over, it will cause the next domino to fall over as well;
    then we know that 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 P1, P2, P3, P4, ..., Pn, ... be some sequence of statements where n is a positive integer. If
    1. P1 is true, and
    2. If Pk is true for a positive integer k, then Pk+1 must also be true,
    then the statement Pn is true for all positive integers n.
  • 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 Pk is true" is called the inductive hypothesis, because we must use this hypothesis to show Pk+1 will also be true.
  • It helps a lot to somehow include part of the statement for Pk when we are writing out Pk+1. This is because we will almost inevitably wind up using our inductive hypothesis (Pk is true) to show that Pk+1 is also true. But we can't use our hypothesis about Pk unless it somehow appears in Pk+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

Transcription: Mathematical Induction

Hi--welcome back to

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 pn, the nth Fermat number, 2 to the 2 to the n plus 1, where n is a natural number0154

(0, 1, 2...working our way up)...if we have p0, then that would be equal to 2 to the 2 to the 0 plus 1.0162

What is 220? 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 221 + 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 223 + 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 225, 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 22n + 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 conjecture0284

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, p5, 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 down0303

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, is like if we were setting up a bunch of dominoes0387

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 d1.0401

Here would be our d1, our first domino.0407

The next domino we could call d2; our second domino is d2, and so on.0409

Here would be d3 and d4, 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 guarantee0432

is that the first domino, d1, will definitely fall over.0440

We are going to be absolutely certain that d1 is going to fall over.0445

Our first domino, d1, 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 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 dominoes0470

(we could, for example, talk about some dk and dk + 1 for any positive integer k,0477

some dk in the line, and then the next one would be called dk + 1--0482

if we are at the k spot, the k + 1 would be the next spot), if dk falls,0486

if the domino on the left falls (dk is the domino on the left), then the next domino in line,0490

dk + 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 dk falls, dk + 1 must fall.0516

We have here that dk falls; and then, at the next one...we have dk falls;0522

if dk falls, dk + 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, d1,0549

is definitely going to fall over; and that, if some domino, some dk falls over,0554

it will cause the next domino, dk + 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 d1 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 d1 must fall.0594

But by the second guarantee, we know that d2 must fall, because d1 is the one before d2.0597

So, d2 must now fall, as well; then, by our second guarantee, once again,0602

since d2 just fell, we know that d3 must fall.0606

Then, by our second guarantee, again, we know that since d3 just fell, we know that d4 must fall.0609

And then, since d4 just fell, d5 must fall; d6 must fall; d7 must fall;0614

d8, d9, d10, 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 domino0626

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

So, since d1 falls, we know that d2 must fall; we know that d3 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 d1, 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 p1, p2, p3, p4...0694

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 p1 is true, and if pk is true for a positive integer k,0711

then pk + 1 must also be true; then we know that the statement pn 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 p1; it is definitely true--the very first one (we have p1, p2, p3,0732

p4, p5...going on forever; we effectively have this infinitely long line of sequences).0736

And we are guaranteed, by our very first thing, that p1 has to be true; p1 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 p1 is true; that means that p2,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 p3 must be true;0757

p4 must be true; p5 must be true; p6 must be true.0761

And it goes on forever and ever and ever, and that is why we now know that pn 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 p1 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 pk is true (this part right here, the "if pk is true")0824

is called the inductive hypothesis, because it is the hypothesis that we use to show that pk + 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, pn,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 pn 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, pn, is true for all n, we must prove two things:1017

first, the base case, that p1 is true--that our very first statement is a true statement;1022

and then, we have to do the inductive step: that if some pk is true,1029

the next one in line, pk + 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 p1 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, "pk is true."1093

We have to start by assuming that if pk is true...we have to say,1098

"OK, pk is true; now let's show that pk + 1 is also going to be true."1102

Once we make this assumption, we somehow have to work to prove that pk + 1 must then also be true.1108

Now, notice: we haven't actually proven pk to be true; we are just asking ourselves,1112

"If pk were true, would pk + 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 pk when we are writing out pk + 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, "pk is true."1151

Otherwise, we wouldn't have needed to talk about pk being true, to show that pk + 1 is true.1154

So, we are going to end up using that inductive hypothesis, that pk is true.1159

So, we have to have some way of talking about it in our pk + 1 statement.1163

We can't use our hypothesis about pk unless it somehow appears in pk + 1.1167

That means, when we end up writing out the pk + 1 statement, that we have to figure out some way1175

to make pk, or some portion of pk, 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, pn; we can turn this into our statement, pn, this right here.1238

How would this work? Well, our first statement, p1, would be if we went from 1 up until an n of 1 (p1, 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 p2, 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 2 times 2 + 1 over 2.1274

And then, the next one, p3, 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 pn, 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, pn--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 pn = 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, p1, and the inductive step, that pk implies pk + 1.1314

The truth of some pk in the middle implies that pk + 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 p1 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 then1361

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 pk is true..." so we assume that pk (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: pk, 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 show1423

(our inductive hypothesis is right here; it is up to us to show) that pk + 1 must also be true.1426

We can write out pk + 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 pk 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 pk + 1 must be true.1467

We need to get some way to see some portion of pk appear.1472

We realize that we can rewrite what we have here: we could write pk + 1 as it is above, but we can't easily see pk in it.1476

So instead, we write it out as pk + 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 pk 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 pk here--our inductive hypothesis, pk.1561

We can substitute pk, 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 pk + 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, pk + 1 is true.1616

And we will have shown that pk + 1 is true from pk, 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 k2 + 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, k2, plus 2k + 1k, so 3k, plus 1 times 2, 2.1650

So, we get k2 + 3k + 2, all over 2.1659

Now, we just combine these two fractions here, k2 + k over 2, plus 2k + 2 over 2.1662

It is going to be k2 + k + 2k + 2, all over 2, which simplifies to a nice k2 + 3k + 2, over 2,1667

which is equal to k2 + 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 pk true, then pk + 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 pn 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 12 + 22 + 32 + ... + n2 = n times n + 1 over 2n + 1.1840

This is effectively our statement pn...not effectively; this is our statement pn.1849

Adding all of the squares, 12 + 22...up until n2, 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 showing1871

that these two sides are the same, that 12 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 1...all over 6.1881

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

12 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 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 pk,1918

which would be 12 + 22...up until we get to some k21923

(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, pn, 12 + 22 + 32...1944

up until n2, 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 pk + 1 is true.1957

It is our job to show that pk + 1 ends up being true.1963

Showing that pk + 1 is true is going to end up being equivalent to showing that 12 + 22 + ...1967

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

because we want to somehow have our pk 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 12 + 22 ... + (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 pattern1998

what is really there, to make it easier, to substitute this: + k2 + (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 12 + 22 + ... up until k2,2032

so we can swap that in for what is here at pk, 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 2k2;2099

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

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

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

(k + 1)2 is (k + 1) times (k + 1); it becomes k2 + 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 2k2; 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 2k2 is 2k3, plus 3k2, plus k, all over 6.2149

Plus...6k2 + 12k + 6, all over 6; and is that equal to (k + 1) times (2k2 + 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 2k2 is going to come out to be 2k3.2181

k times 7k is 7k2; plus...1 times 2k2...7k2 + 2k2 is 9k2;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 2k3...2201

everything will be divided by 6 over here...2k3 plus nothing on our other fraction,2206

so that is just that...3k2 + 6k2...we get 9k2;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 2k3 + 9k2?2222

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

(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, p1, being true,2245

and if pk is true--our inductive hypothesis--then pk + 1 is true, which we just showed here)--2249

we combined those two things, so now we have shown that pn is true for all things:2255

that 12 + 22 + 32...up until + n2 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 n3 + 2n is divisible by 3.2269

So really, this is our statement, pn: pn is "n3 + 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 p1 statement would be true.2289

Verifying p1 is the same thing as verifying that 13 + 2(1) is divisible by 3.2295

13 + 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 pk ends up being true.2331

What is pk? pk would be if we plugged in k for our n here: k3 + 2k is divisible by 3.2336

This is our starting assumption: that k3 + 2k is divisible by 3.2349

At this point, we now want to show that pk + 1 is true.2353

Showing that pk + 1 is true is going to be the same thing as showing2364

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 k2 + 2k + 1.2402

Plus...2 times (k + 1)...that is 2k + 2.2407

k + 1 times k2 + 2k + 1...well, k times k2 is going to be k3;2411

k times 2k is 2k2, plus 1 times k2, so + 3k2;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 k3 + 2k is definitely divisible by 3."2433

Look: here is k3; here is 2k; let's bring them together.2444

Now, we have k3 + 2k; and we will put everything else on the other side.2447

So, 3k2 + 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

k3 + 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 k2 + 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 k2 + 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 pk is true, then pk + 1 is true.2526

So, we have now shown the inductive step; since we have shown that p1 is true,2530

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

then p1 being true implies that p2 must be true, by our inductive step,2538

which implies that p3 must be true, by our inductive step; p4, p5, p6, p7...2541

So, we know that, forever and always, n3 + 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 nth partial sum2554

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 nth partial sum is going to be equal to n2; great.2618

What we have here is 1 + 3 + 5 + ... + something...whatever we end equal to n2.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 nth term here, an, 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 pn statement, is that 1 + 3 + 5, working up until 2n - 1, is equal to n2, 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 n2 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 pn is true for any value of n:2731

that 1 + 3 + 5...up until + 2n - 1 is equal to n2, 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 p1 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 12?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 pk is true.2780

What is the statement pk? Well, that would be 1 + 3 + ... up until we get to +...plug in k for n...2k - 1 = k2.2783

So, we are assuming that 1 + 3 + ... + 2k - 1 is equal to k2.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 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, pk + 1, that part of it, is going to just be equal to k2, right here.2885

So, we can swap out k2 here; so now we have k2 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 k2; we expand this; well, k2 + (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 k2 + 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 pk being true, we know that pk + 1 must be true.2941

Because we know that our base case is true (p1 is true), and we know that if something is true,2945

then the next thing has to be true; then since p1 is true, the next thing must be true.2949

p2 is true; p3 is true; p4 is true; p5 is true; p6 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 later--goodbye!2991