WEBVTT mathematics/math-analysis/selhorst-jones
00:00:00.000 --> 00:00:02.200
Hi--welcome back to Educator.com.
00:00:02.200 --> 00:00:05.100
Today, we are going to talk about mathematical induction.
00:00:05.100 --> 00:00:07.600
The great thing about math is that we can trust it.
00:00:07.600 --> 00:00:16.100
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.
00:00:16.100 --> 00:00:19.600
We can have certainty in this truth, because of proof.
00:00:19.600 --> 00:00:24.700
In math, we start with a few simple ideas, and then we use proof to build a tower of logic.
00:00:24.700 --> 00:00:30.500
Because we prove every theorem and method that we work with, we can trust the whole of mathematics.
00:00:30.500 --> 00:00:37.300
Mathematics is built on this concept of truth--that we start with some things that we can just take for granted,
00:00:37.300 --> 00:00:44.200
absolutely certainly--these axiomatic truths that we looked at in geometry, for example, previously--you have seen it in some courses.
00:00:44.200 --> 00:00:48.200
We start with these basic axioms, and then we work up from there, using logic.
00:00:48.200 --> 00:00:52.500
We can use proof to make sure that we can trust every single thing that we work with.
00:00:52.500 --> 00:00:56.200
So far in this course, we have proved many things with a variety of logical arguments.
00:00:56.200 --> 00:01:01.100
We have made very strong logical arguments that show, without a doubt, that something has to be true.
00:01:01.100 --> 00:01:06.200
In this lesson, we are going to see a new form for proofs, **mathematical induction**.
00:01:06.200 --> 00:01:10.900
This method can be used anywhere, from our current level of math all the way to very advanced mathematics.
00:01:10.900 --> 00:01:17.500
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.
00:01:17.500 --> 00:01:20.300
All right, let's talk about belief versus proof.
00:01:20.300 --> 00:01:27.400
In math, it is important to recognize that there is a difference between believing that something is true and proving that something is true.
00:01:27.400 --> 00:01:32.600
While we may strongly believe in something, that implies that there is still some level of reasonable doubt.
00:01:32.600 --> 00:01:37.700
Believing in something doesn't mean that we can know it absolutely certainly; it just means that it is probably true.
00:01:37.700 --> 00:01:41.900
But there is still this tiny crack of doubt that maybe it is not going to end up being true.
00:01:41.900 --> 00:01:49.900
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.
00:01:49.900 --> 00:01:56.400
A proof is an irrefutable logical argument; it is something that very clearly shows (and there is no way to disagree with it)
00:01:56.400 --> 00:02:03.700
that, given some something, we can show that it is always going to end up working out; it gives us total certainty.
00:02:03.700 --> 00:02:09.000
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.
00:02:09.000 --> 00:02:13.800
We may believe that it will hold, but until we prove it, we cannot be absolutely certain.
00:02:13.800 --> 00:02:19.900
So, we may believe in something, but we have to go and prove it before we can be absolutely certain.
00:02:19.900 --> 00:02:24.800
Proof is this really integral part to how mathematics works.
00:02:24.800 --> 00:02:29.900
As an example, consider the following: in the 1600s, a mathematician named Fermat noticed a pattern.
00:02:29.900 --> 00:02:34.200
It seemed to him that all numbers of the form below were prime numbers.
00:02:34.200 --> 00:02:41.900
It is p<font size="-6">n</font>, the nth Fermat number, 2 to the 2 to the n plus 1, where n is a natural number
00:02:41.900 --> 00:02:48.500
(0, 1, 2...working our way up)...if we have p₀, then that would be equal to 2 to the 2 to the 0 plus 1.
00:02:48.500 --> 00:02:54.100
What is 2^2⁰? Well, 2 to the 0...any number raised to the 0 is 1, so it is 2 to the 1.
00:02:54.100 --> 00:03:01.100
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.
00:03:01.100 --> 00:03:08.800
Next, the next Fermat number would be 2^2¹ + 1; that gets us 5, and indeed, that is a prime number.
00:03:08.800 --> 00:03:14.600
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.
00:03:14.600 --> 00:03:17.500
Now, we are starting to get to a place where we can't immediately see that they are prime.
00:03:17.500 --> 00:03:23.100
But 2^2³ + 1 is 257; and you can check--that does end up being prime.
00:03:23.100 --> 00:03:28.600
The next one would be 2 to the 2 to the 4 plus 1, which comes out to be 65537;
00:03:28.600 --> 00:03:34.400
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.
00:03:34.400 --> 00:03:46.000
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.
00:03:46.000 --> 00:03:48.900
Each one of these came out to be a prime number.
00:03:48.900 --> 00:03:57.900
So, he could check by hand that you are able to make primes for these first five Fermat numbers (0, 1, 2, 3, 4).
00:03:57.900 --> 00:04:01.700
He was able to show for sure that they do make primes.
00:04:01.700 --> 00:04:06.500
However, the next Fermat number was too large for him to check, and he couldn't figure out a way to prove it prime.
00:04:06.500 --> 00:04:16.200
The next one is 2^2⁵, plus 1, which is equal to a huge 4 billion, 294 million, 967 thousand, 297--a big number.
00:04:16.200 --> 00:04:20.600
That is going to be really hard to check by hand; and Fermat wasn't able to check by hand.
00:04:20.600 --> 00:04:25.300
So, he couldn't figure out a clever way to prove for sure that it was prime without having to check by hand.
00:04:25.300 --> 00:04:28.600
And it was too big for him to check by hand, so he couldn't show that it was prime.
00:04:28.600 --> 00:04:34.500
Nonetheless, he had noticed a pattern; so he made a conjecture, that is, a hypothesis--an expectation,
00:04:34.500 --> 00:04:41.300
of how things will work: that all numbers of the form 2 + 1 are prime.
00:04:41.300 --> 00:04:44.200
But noticing a pattern does not necessarily prove it to be true.
00:04:44.200 --> 00:04:48.500
This was a conjecture, but we didn't know for sure whether it was going to end up being a true conjecture
00:04:48.500 --> 00:04:52.100
or a false conjecture--if it was going to end up being disproven.
00:04:52.100 --> 00:04:56.000
It was not until the 1700s that we knew whether or not the conjecture was true.
00:04:56.000 --> 00:05:02.800
Another mathematician, named Euler, showed that the sixth Fermat number, p₅, could be factored.
00:05:02.800 --> 00:05:10.100
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
00:05:10.100 --> 00:05:15.700
into the two numbers 641 times 6 million, 700 thousand, 417.
00:05:15.700 --> 00:05:23.500
So, since that Fermat number can be broken down into two factors, that means that it is not a prime number.
00:05:23.500 --> 00:05:30.100
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.
00:05:30.100 --> 00:05:34.600
Thus, he had proven the conjecture false; he had shown that there was a counterexample.
00:05:34.600 --> 00:05:41.200
So, that conjecture that Fermat had originally thought, that 2 to the 2 to the n plus 1 was prime--that is not true.
00:05:41.200 --> 00:05:44.200
We have proven it to not be true.
00:05:44.200 --> 00:05:49.000
It is relatively easy to prove that something is not true; you only need a single counterexample--
00:05:49.000 --> 00:05:53.200
one counterexample that cancels out and says, "No, here is a way that you can't have that work."
00:05:53.200 --> 00:05:57.800
That proves that that does not work; but how can we prove that a pattern will hold forever,
00:05:57.800 --> 00:06:02.900
that we have some sequence of things that is going to always end up being the case?
00:06:02.900 --> 00:06:04.900
We can do this with mathematical induction.
00:06:04.900 --> 00:06:07.700
There are other ways to do this; you can make logical arguments in other ways.
00:06:07.700 --> 00:06:12.100
But a good way to do this is with mathematical induction; it often works well.
00:06:12.100 --> 00:06:19.200
Before formally stating the principle of mathematical induction, let's look at a metaphor to help us understand how induction works.
00:06:19.200 --> 00:06:27.000
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.
00:06:27.000 --> 00:06:31.100
Domino, domino, domino, domino, domino...it is like if we were setting up a bunch of dominoes
00:06:31.100 --> 00:06:34.700
to push it over and have (thump, thump, thump, thump, thump, thump, thump...) falling-over dominoes.
00:06:34.700 --> 00:06:37.600
That is the image that we want to have in our mind.
00:06:37.600 --> 00:06:41.100
OK, we could name the dominoes, based on their location in line.
00:06:41.100 --> 00:06:46.700
The very first domino that would start on the line, on the very left side, we could call d₁.
00:06:46.700 --> 00:06:49.300
Here would be our d₁, our first domino.
00:06:49.300 --> 00:06:53.700
The next domino we could call d₂; our second domino is d₂, and so on.
00:06:53.700 --> 00:06:57.700
Here would be d₃ and d₄, and it is going to just continue on in that pattern.
00:06:57.700 --> 00:07:02.200
So, any domino...there exists some n that we can name any domino with.
00:07:02.200 --> 00:07:05.100
We talk about some domino: there is some number that we can associate with it,
00:07:05.100 --> 00:07:09.400
because we can just count up from the beginning and see what number we have to count to, to get to that domino.
00:07:09.400 --> 00:07:11.800
That means that we can name any given domino.
00:07:11.800 --> 00:07:20.000
All right, we have two guarantees: consider if we had two guarantees: the first guarantee
00:07:20.000 --> 00:07:25.100
is that the first domino, d₁, will definitely fall over.
00:07:25.100 --> 00:07:29.100
We are going to be absolutely certain that d₁ is going to fall over.
00:07:29.100 --> 00:07:36.800
Our first domino, d₁, is for sure going to fall over; we know that our very first domino in the line is going to fall over.
00:07:36.800 --> 00:07:41.800
It is going to get pushed somehow; a gust of wind is going to happen...an earthquake...but something will certainly happen.
00:07:41.800 --> 00:07:46.000
Who knows what it is, but we are guaranteed that it will fall over, for sure.
00:07:46.000 --> 00:07:50.000
We know that our very first one is going to fall over; that is our first guarantee.
00:07:50.000 --> 00:07:56.700
Our second guarantee is that, given any sequential pair, any pair of dominoes
00:07:56.700 --> 00:08:01.900
(we could, for example, talk about some d<font size="-6">k</font> and d<font size="-6">k + 1</font> for any positive integer k,
00:08:01.900 --> 00:08:05.900
some d<font size="-6">k</font> in the line, and then the next one would be called d<font size="-6">k + 1</font>--
00:08:05.900 --> 00:08:10.300
if we are at the k spot, the k + 1 would be the next spot), if d<font size="-6">k</font> falls,
00:08:10.300 --> 00:08:20.900
if the domino on the left falls (d<font size="-6">k</font> is the domino on the left), then the next domino in line,
00:08:20.900 --> 00:08:25.800
d<font size="-6">k + 1</font>, will also fall; this is our next guarantee.
00:08:25.800 --> 00:08:36.300
So, if the domino on the left falls, then the next domino will fall, as well.
00:08:36.300 --> 00:08:41.800
We are going to get falling from the next domino; if d<font size="-6">k</font> falls, d<font size="-6">k + 1</font> must fall.
00:08:41.800 --> 00:08:47.300
We have here that d<font size="-6">k</font> falls; and then, at the next one...we have d<font size="-6">k</font> falls;
00:08:47.300 --> 00:08:51.100
if d<font size="-6">k</font> falls, d<font size="-6">k + 1</font> must also fall.
00:08:51.100 --> 00:08:55.400
If one domino falls, the next domino in line is always guaranteed to fall.
00:08:55.400 --> 00:09:03.200
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.
00:09:03.200 --> 00:09:09.400
All right, we have these two things for sure: we have two guarantees and this infinite line of dominoes.
00:09:09.400 --> 00:09:14.600
There is some line of dominoes, and the two guarantees: that the first domino, d₁,
00:09:14.600 --> 00:09:20.300
is definitely going to fall over; and that, if some domino, some d<font size="-6">k</font> falls over,
00:09:20.300 --> 00:09:24.300
it will cause the next domino, d<font size="-6">k + 1</font>, to also fall over.
00:09:24.300 --> 00:09:34.700
Given these two guarantees, we now know that absolutely all of the dominoes in our infinitely long line of dominoes will fall over.
00:09:34.700 --> 00:09:37.700
We know for sure that all of them are going to fall over.
00:09:37.700 --> 00:09:44.200
Why? Well, because, by the first guarantee, we know that d₁ falls.
00:09:44.200 --> 00:09:48.500
We know that the very first one in the line has to fall, because we are guaranteed that it is going to fall.
00:09:48.500 --> 00:09:54.600
Then, by the second guarantee, if some domino falls, then we know that the next domino falls.
00:09:54.600 --> 00:09:56.900
By our first guarantee, we know that d₁ must fall.
00:09:56.900 --> 00:10:01.800
But by the second guarantee, we know that d₂ must fall, because d₁ is the one before d₂.
00:10:01.800 --> 00:10:06.100
So, d₂ must now fall, as well; then, by our second guarantee, once again,
00:10:06.100 --> 00:10:09.200
since d₂ just fell, we know that d₃ must fall.
00:10:09.200 --> 00:10:14.200
Then, by our second guarantee, again, we know that since d₃ just fell, we know that d₄ must fall.
00:10:14.200 --> 00:10:17.700
And then, since d₄ just fell, d₅ must fall; d₆ must fall; d₇ must fall;
00:10:17.700 --> 00:10:20.500
d₈, d₉, d<font size="-6">10</font>, forever and ever and ever.
00:10:20.500 --> 00:10:26.600
Thus, all of the dominoes must fall over; we know that every single domino must fall over,
00:10:26.600 --> 00:10:30.500
because we are guaranteed that the first domino is going to fall, and we know that every domino
00:10:30.500 --> 00:10:33.200
after a domino that has fallen will fall as well.
00:10:33.200 --> 00:10:36.500
So, since d₁ falls, we know that d₂ must fall; we know that d₃ must fall;
00:10:36.500 --> 00:10:38.400
and we can work our way out, going forever.
00:10:38.400 --> 00:10:44.500
This is inductive thinking, step-by-step logic; this is the idea of mathematical induction,
00:10:44.500 --> 00:10:48.100
that we have this first premise, that the definite thing is going to happen for the first thing;
00:10:48.100 --> 00:10:52.200
and that, if something happens, we know that the next thing has to happen, as well.
00:10:52.200 --> 00:10:58.200
We can start at d₁, and from that induction idea, we can move forward forever, stepping along.
00:10:58.200 --> 00:11:06.000
Mathematical induction is extremely similar; this idea of using it in math is very, very much the same thing as this line of dominoes.
00:11:06.000 --> 00:11:12.900
It is just that, instead of dominoes, we will work with statements; and instead of "falls over," we will say "is true."
00:11:12.900 --> 00:11:15.700
But other than that, the logic behind it is exactly the same.
00:11:15.700 --> 00:11:20.600
And I know that that might seem like a crazy thing to say--that we can connect dominoes and statements,
00:11:20.600 --> 00:11:24.000
and we can connect falling over with being true; but really, the idea behind it is the same.
00:11:24.000 --> 00:11:25.900
And we will see why in just a second.
00:11:25.900 --> 00:11:31.400
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.
00:11:31.400 --> 00:11:34.300
All right, now we are ready to look at the principle.
00:11:34.300 --> 00:11:40.100
The principle of mathematical induction is: let p₁, p₂, p₃, p₄...
00:11:40.100 --> 00:11:45.500
going on...p<font size="-6">n</font>...going on forever, be some infinitely long sequence of statements,
00:11:45.500 --> 00:11:48.500
or just some sequence of statements, where n is a positive integer.
00:11:48.500 --> 00:11:51.000
We are stepping forward, one statement at a time.
00:11:51.000 --> 00:12:00.800
And we are guaranteed two things: if p₁ is true, and if p<font size="-6">k</font> is true for a positive integer k,
00:12:00.800 --> 00:12:08.800
then p<font size="-6">k + 1</font> must also be true; then we know that the statement p<font size="-6">n</font> is true for all positive integers n.
00:12:08.800 --> 00:12:12.200
Why is this the case? Well, it is very much the same thing as we just saw with the dominoes.
00:12:12.200 --> 00:12:16.600
We have p₁; it is definitely true--the very first one (we have p₁, p₂, p₃,
00:12:16.600 --> 00:12:21.200
p₄, p₅...going on forever; we effectively have this infinitely long line of sequences).
00:12:21.200 --> 00:12:26.800
And we are guaranteed, by our very first thing, that p₁ has to be true; p₁ is true.
00:12:26.800 --> 00:12:32.600
Then, our next guarantee is that, if something is true, the next thing in line must be true.
00:12:32.600 --> 00:12:35.600
Our first guarantee was that p₁ is true; that means that p₂,
00:12:35.600 --> 00:12:37.500
since it is the next thing in line, must also be true.
00:12:37.500 --> 00:12:40.900
That means, by that same guarantee, that the next thing in line is true, that p₃ must be true;
00:12:40.900 --> 00:12:43.300
p₄ must be true; p₅ must be true; p₆ must be true.
00:12:43.300 --> 00:12:51.000
And it goes on forever and ever and ever, and that is why we now know that p<font size="-6">n</font> is going to be true for all positive integers n.
00:12:51.000 --> 00:12:55.000
It is because, since the first thing in line was guaranteed by that first guarantee,
00:12:55.000 --> 00:12:58.200
and the second thing is going to end up happening because of that second guarantee,
00:12:58.200 --> 00:13:01.700
and then the third one will happen because of the second guarantee again,
00:13:01.700 --> 00:13:03.900
and then the fourth thing will happen because of the second guarantee again...
00:13:03.900 --> 00:13:07.700
we can keep using that step, step, step, step, step--that the second guarantee gives us.
00:13:07.700 --> 00:13:14.500
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.
00:13:14.500 --> 00:13:21.000
All right, we often call the first step (that p₁ is true) the base case,
00:13:21.000 --> 00:13:23.100
because it is establishing the basis that we are working from.
00:13:23.100 --> 00:13:26.400
It is the very first one in the line of true statements.
00:13:26.400 --> 00:13:33.600
The second step is often called the inductive step, because it is the thing where the actual induction occurs--
00:13:33.600 --> 00:13:40.900
that induction being "if 1, then 2," "if 2, then 3," so 1, then 2, then 3, then 4, then 5, then 6...
00:13:40.900 --> 00:13:44.300
the fact that we can start at one place, and then step forever forward.
00:13:44.300 --> 00:13:51.400
In the inductive step, the assumption, if p<font size="-6">k</font> is true (this part right here, the "if p<font size="-6">k</font> is true")
00:13:51.400 --> 00:13:59.600
is called the **inductive hypothesis**, because it is the hypothesis that we use to show that p<font size="-6">k + 1</font> will also be true.
00:13:59.600 --> 00:14:04.000
We have to have this assumption that, if this thing happens, then this other thing will happen.
00:14:04.000 --> 00:14:09.000
It is just like, with the dominoes, we say, "If some domino falls over, then this thing is going to happen in response."
00:14:09.000 --> 00:14:16.100
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."
00:14:16.100 --> 00:14:19.500
All right, before we keep going, I want to have a quick remark on statements.
00:14:19.500 --> 00:14:23.000
The principle of mathematical induction is based on statements.
00:14:23.000 --> 00:14:27.900
We might be tempted to assume that any statement we see written out will automatically be true.
00:14:27.900 --> 00:14:33.500
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.
00:14:33.500 --> 00:14:35.400
Don't believe everything you read.
00:14:35.400 --> 00:14:39.300
A statement, like in English, is just a string of words and/or symbols.
00:14:39.300 --> 00:14:44.600
For example, the statement "Ice cream is made of hair" is most emphatically not true.
00:14:44.600 --> 00:14:47.500
Ice cream is not made of hair; that is not true.
00:14:47.500 --> 00:14:51.000
But it is still a statement, albeit a false statement.
00:14:51.000 --> 00:14:54.800
Just because something is said does not mean that it is always going to end up being true.
00:14:54.800 --> 00:15:02.800
Similarly, in math, the statement 3 + 5 + 7 = 10 is false; that is not true: 3 + 5 + 7 is not equal to 10.
00:15:02.800 --> 00:15:05.600
But it is still a statement--just not a true statement.
00:15:05.600 --> 00:15:11.200
3 + 5 + 7 is actually equal to 15, so we know that this one here is a false statement.
00:15:11.200 --> 00:15:15.800
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,
00:15:15.800 --> 00:15:19.600
because they are given to us directly from the problem, and we are not told to question them.
00:15:19.600 --> 00:15:21.800
We are saying, "Start with this thing and work with it."
00:15:21.800 --> 00:15:26.600
Or we are working on the problem from the beginning (like a word problem), and we see, from the information that we are given,
00:15:26.600 --> 00:15:30.800
that we can use logic to say, "Oh, this must definitely be the case; this must definitely be the case."
00:15:30.800 --> 00:15:33.400
We are able to work with these things and be certain of their truth.
00:15:33.400 --> 00:15:37.500
But just because something is said does not necessarily mean that it is always going to be true.
00:15:37.500 --> 00:15:41.400
Everything that we have dealt with so far in math--we have been able to assume the truth of things,
00:15:41.400 --> 00:15:44.000
because we know that we weren't being given lies.
00:15:44.000 --> 00:15:49.800
But now, if we are just talking about statements in general, we have to evaluate their truth before we can trust them.
00:15:49.800 --> 00:15:56.400
When we are working with mathematical induction, it is our job to not only set up the statements, p<font size="-6">n</font>,
00:15:56.400 --> 00:16:00.700
but to also prove that the statements are going to be true statements.
00:16:00.700 --> 00:16:03.100
We are not just going to get the statements and assume that they are true.
00:16:03.100 --> 00:16:07.300
We have to get the statements, and then show for sure that they end up being true.
00:16:07.300 --> 00:16:11.000
And occasionally, we might discover that the statements we have actually end up being false statements,
00:16:11.000 --> 00:16:14.600
at which point we will have to go back to the beginning and figure out a way that we can state it truthfully;
00:16:14.600 --> 00:16:17.200
or that will end up being the answer--the fact that it is actually not true.
00:16:17.200 --> 00:16:19.400
But generally, we are going to end up showing that it is true.
00:16:19.400 --> 00:16:25.600
Now, of course, if we want to show that n goes on infinitely, that all p<font size="-6">n</font> for any 1, 2, 3, 4, going on forever--
00:16:25.600 --> 00:16:30.200
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.
00:16:30.200 --> 00:16:35.100
We are not going to be able to have an infinite amount of time to prove an infinite number of things.
00:16:35.100 --> 00:16:38.700
So instead, we have to use some way to be able to show all of them at once.
00:16:38.700 --> 00:16:43.400
We can either use some sort of clever logical argument, or we can use proof by mathematical induction,
00:16:43.400 --> 00:16:46.300
where we can show that the first step will end up always being true,
00:16:46.300 --> 00:16:51.500
and that, if you have some step, the next thing is going to end up being true, to work our way out infinitely,
00:16:51.500 --> 00:16:55.300
like that line of dominoes, like we were just talking about a few moments ago.
00:16:55.300 --> 00:16:57.300
All right, how do we use mathematical induction?
00:16:57.300 --> 00:17:02.200
If we are going to use induction to prove that some statement, p<font size="-6">n</font>, is true for all n, we must prove two things:
00:17:02.200 --> 00:17:08.700
first, the base case, that p₁ is true--that our very first statement is a true statement;
00:17:08.700 --> 00:17:13.400
and then, we have to do the inductive step: that if some p<font size="-6">k</font> is true,
00:17:13.400 --> 00:17:16.600
the next one in line, p<font size="-6">k + 1</font>, must also be true.
00:17:16.600 --> 00:17:22.100
So, that means, when we are working with proof by induction, that we have at least two separate steps.
00:17:22.100 --> 00:17:28.100
We have two separate things that we have to deal with: proving the base case and proving the inductive step.
00:17:28.100 --> 00:17:29.500
We have to show each one of these.
00:17:29.500 --> 00:17:35.000
I am going to strongly recommend noting which one you are working on and making it so that you can keep the parts separate.
00:17:35.000 --> 00:17:38.200
How you work on the base case normally isn't going to really help you deal with the inductive step.
00:17:38.200 --> 00:17:41.300
How you work on the inductive step normally isn't really going to help you deal with the base case.
00:17:41.300 --> 00:17:46.100
So, just write "base case" and prove your base case; then write "inductive step"; then prove your inductive step.
00:17:46.100 --> 00:17:49.400
It will help you keep track of what you are doing; it will help keep it from being confusing.
00:17:49.400 --> 00:17:53.300
And it will help other people who read your work in the future to understand what happened there.
00:17:53.300 --> 00:17:58.400
In general, proving the base case almost always is going to be easier by far.
00:17:58.400 --> 00:18:03.300
Normally, we just end up simplifying the statement--whatever this p₁ statement ends up being;
00:18:03.300 --> 00:18:09.600
and we verify that it is, indeed, a true statement--it is just making sure that, yes, this is true.
00:18:09.600 --> 00:18:12.700
The tricky part normally ends up being dealing with the inductive step.
00:18:12.700 --> 00:18:18.500
To prove the inductive step, we must first assume the inductive hypothesis, "p<font size="-6">k</font> is true."
00:18:18.500 --> 00:18:21.900
We have to start by assuming that if p<font size="-6">k</font> is true...we have to say,
00:18:21.900 --> 00:18:28.200
"OK, p<font size="-6">k</font> is true; now let's show that p<font size="-6">k + 1</font> is also going to be true."
00:18:28.200 --> 00:18:32.600
Once we make this assumption, we somehow have to work to prove that p<font size="-6">k + 1</font> must then also be true.
00:18:32.600 --> 00:18:38.100
Now, notice: we haven't actually proven p<font size="-6">k</font> to be true; we are just asking ourselves,
00:18:38.100 --> 00:18:41.800
"If p<font size="-6">k</font> were true, would p<font size="-6">k + 1</font> also be true?"
00:18:41.800 --> 00:18:45.500
We are saying, "If we had this place that we could start from, would the next thing be true?"
00:18:45.500 --> 00:18:49.800
It is like the dominoes: if this domino were to fall over, would the next one in line fall over?
00:18:49.800 --> 00:18:53.300
That is all we need for mathematical induction: we don't have to prove that the one in the middle will fall over.
00:18:53.300 --> 00:18:58.000
We just have to say, "Well, if it were to fall over, would the next one fall over, as well?"
00:18:58.000 --> 00:19:06.500
All right, it helps a lot to somehow include part of the statement for p<font size="-6">k</font> when we are writing out p<font size="-6">k + 1</font>.
00:19:06.500 --> 00:19:11.000
This is because we are almost inevitably going to end up using the inductive hypothesis.
00:19:11.000 --> 00:19:14.400
We have to use this inductive hypothesis, "p<font size="-6">k</font> is true."
00:19:14.400 --> 00:19:19.400
Otherwise, we wouldn't have needed to talk about p<font size="-6">k</font> being true, to show that p<font size="-6">k + 1</font> is true.
00:19:19.400 --> 00:19:23.500
So, we are going to end up using that inductive hypothesis, that p<font size="-6">k</font> is true.
00:19:23.500 --> 00:19:27.300
So, we have to have some way of talking about it in our p<font size="-6">k + 1</font> statement.
00:19:27.300 --> 00:19:34.700
We can't use our hypothesis about p<font size="-6">k</font> unless it somehow appears in p<font size="-6">k + 1</font>.
00:19:34.700 --> 00:19:38.600
That means, when we end up writing out the p<font size="-6">k + 1</font> statement, that we have to figure out some way
00:19:38.600 --> 00:19:41.700
to make p<font size="-6">k</font>, or some portion of p<font size="-6">k</font>, show up in some way,
00:19:41.700 --> 00:19:48.400
so that we can apply that inductive hypothesis and use what we have assumed to be true.
00:19:48.400 --> 00:19:50.100
It is important to have that end up showing up.
00:19:50.100 --> 00:19:54.300
We will see how that occurs as we are actually working through problems and examples.
00:19:54.300 --> 00:19:57.100
All right, all of this is going to make a lot more sense once we see it in action.
00:19:57.100 --> 00:20:03.200
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.
00:20:03.200 --> 00:20:08.700
All right, consider the following formula, which we proved in the lesson Arithmetic Sequences and Series:
00:20:08.700 --> 00:20:15.400
we proved that adding the numbers 1 + 2 + 3 + ... up until we get to + n, all of the numbers consecutively,
00:20:15.400 --> 00:20:22.000
from 1 up until some n that we choose, is equal to n times n + 1 divided by 2.
00:20:22.000 --> 00:20:27.000
Previously, we proved this by a logical argument that involved equations and elimination.
00:20:27.000 --> 00:20:31.400
Adding up two equations (if you watched that lesson), we were able to prove it through logical argument.
00:20:31.400 --> 00:20:37.700
But we also could prove it through mathematical induction; let's see another way to prove this, through mathematical induction.
00:20:37.700 --> 00:20:45.800
We can see that the above equation is effectively our statement, p<font size="-6">n</font>; we can turn this into our statement, p<font size="-6">n</font>, this right here.
00:20:45.800 --> 00:20:53.800
How would this work? Well, our first statement, p₁, would be if we went from 1 up until an n of 1 (p₁, so 1 up until 1).
00:20:53.800 --> 00:21:01.200
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?
00:21:01.200 --> 00:21:05.800
That is the first statement: the first statement is that 1 is equal to 1 times 1 + 1 over 2.
00:21:05.800 --> 00:21:11.200
Our next statement, at p₂, would be 1 +...up until 2, so that is just going to be 1 + 2;
00:21:11.200 --> 00:21:13.800
and that is going to be equal...the statement says that it is equal;
00:21:13.800 --> 00:21:19.400
it will be up to us to verify that this actually ends up working out...to 2 times 2 + 1 over 2.
00:21:19.400 --> 00:21:24.100
And then, the next one, p₃, would be equal to 1 + 2 + 3...we get up to the third;
00:21:24.100 --> 00:21:28.500
and it is saying...the statement is that that is, indeed, equal to 3 times 3 + 1 over 2.
00:21:28.500 --> 00:21:33.800
And finally, the really interesting one here is p<font size="-6">n</font>, which is adding all the numbers from 1 up until n,
00:21:33.800 --> 00:21:36.300
and that that is equal to n times n + 1 over 2.
00:21:36.300 --> 00:21:40.900
So, this is our statement, p<font size="-6">n</font>--this way of writing it out here.
00:21:40.900 --> 00:21:42.800
I didn't mean to cut through that 2.
00:21:42.800 --> 00:21:49.700
To prove by induction that the statement p<font size="-6">n</font> = 1 added to all the numbers up until n is equal to n times n + 1 over 2--
00:21:49.700 --> 00:21:54.100
to prove this as true for all positive integers, if we are going to use proof by induction, we have to prove two things.
00:21:54.100 --> 00:22:02.200
We have to prove both the base case, p₁, and the inductive step, that p<font size="-6">k</font> implies p<font size="-6">k + 1</font>.
00:22:02.200 --> 00:22:08.300
The truth of some p<font size="-6">k</font> in the middle implies that p<font size="-6">k + 1</font>, the next one down the line, also has to be true.
00:22:08.300 --> 00:22:11.600
Let's begin with the base case; the base case is normally the easier thing, by far.
00:22:11.600 --> 00:22:17.200
Our p₁ statement was that 1 is equal to 1 times 1 + 1 over 2.
00:22:17.200 --> 00:22:21.600
Now, that is just a statement; once again, it is up to us to verify the truth of the statement.
00:22:21.600 --> 00:22:27.300
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.
00:22:27.300 --> 00:22:33.400
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.
00:22:33.400 --> 00:22:37.000
The statement could be lying to us; it is up to us to figure out if this is, indeed, true;
00:22:37.000 --> 00:22:41.100
are the left side and the right side actually equal to each other?
00:22:41.100 --> 00:22:50.500
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
00:22:50.500 --> 00:22:54.600
that simplifies; the 2's cancel out, and we have 1 = 1; and indeed, that is true.
00:22:54.600 --> 00:22:59.900
So, that means that our base case checks out; we have shown that the base case is definitely true.
00:22:59.900 --> 00:23:05.200
Next, we move on to the inductive step: we write "inductive step," so that we see where we are.
00:23:05.200 --> 00:23:09.200
The very first thing that we always do with the inductive step is write out our inductive hypothesis.
00:23:09.200 --> 00:23:13.900
We say, "If p<font size="-6">k</font> is true..." so we assume that p<font size="-6">k</font> (which would be 1 + 2 + 3...
00:23:13.900 --> 00:23:19.200
all the way up until we get to some k, is equal to k times k + 1 over 2) is true.
00:23:19.200 --> 00:23:27.900
We are assuming that this thing is true: p<font size="-6">k</font>, which is the statement 1 + 2 + 3...up until + k = k + (k + 1)/2--
00:23:27.900 --> 00:23:33.000
we can just take this as cold, hard fact; it is the assumption that if this domino were to fall,
00:23:33.000 --> 00:23:35.000
now we just need to work on the next domino falling.
00:23:35.000 --> 00:23:40.700
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.
00:23:40.700 --> 00:23:43.200
All right, so we have this assumed as true.
00:23:43.200 --> 00:23:45.700
With the inductive hypothesis in mind, we want to show
00:23:45.700 --> 00:23:51.700
(our inductive hypothesis is right here; it is up to us to show) that p<font size="-6">k + 1</font> must also be true.
00:23:51.700 --> 00:23:58.200
We can write out p<font size="-6">k + 1</font> as 1 + 2 + 3 +...up until...well, now we are going up to k + 1,
00:23:58.200 --> 00:24:04.400
so up until + k + 1...and we can plug in k + 1 times k + 1 + 1, all over 2.
00:24:04.400 --> 00:24:06.700
So, we see that this is what the statement would be.
00:24:06.700 --> 00:24:10.300
However, we can't really see how p<font size="-6">k</font> shows up in here;
00:24:10.300 --> 00:24:15.000
how does something in this portion right here show up?--because remember what we talked about before.
00:24:15.000 --> 00:24:19.500
We are going to have to use our inductive hypothesis; that is what the inductive hypothesis is there for.
00:24:19.500 --> 00:24:22.700
If we could prove this without an inductive hypothesis, why are we doing induction?
00:24:22.700 --> 00:24:27.300
So, we have to use that inductive hypothesis somehow to be able to apply it here,
00:24:27.300 --> 00:24:32.400
so that we can show that p<font size="-6">k + 1</font> must be true.
00:24:32.400 --> 00:24:36.000
We need to get some way to see some portion of p<font size="-6">k</font> appear.
00:24:36.000 --> 00:24:44.500
We realize that we can rewrite what we have here: we could write p<font size="-6">k + 1</font> as it is above, but we can't easily see p<font size="-6">k</font> in it.
00:24:44.500 --> 00:24:52.800
So instead, we write it out as p<font size="-6">k + 1</font> = 1 + 2 + 3 + ... + k + k + 1.
00:24:52.800 --> 00:24:58.500
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.
00:24:58.500 --> 00:25:02.100
So, k has to be included in there, because it is the number before k + 1.
00:25:02.100 --> 00:25:09.700
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.
00:25:09.700 --> 00:25:15.700
So, we can write it out; now that means that we have p<font size="-6">k</font> showing up right here.
00:25:15.700 --> 00:25:21.900
1 + 2 + 3...up until k...look, that is this right here; so we can bring this to bear.
00:25:21.900 --> 00:25:25.900
And we just simplified the right side a little bit; that just ends up being the same thing.
00:25:25.900 --> 00:25:31.400
k + 1 times k + 1 + 1 is just k + 1 times k + 2, over 2; we just simplified the right side.
00:25:31.400 --> 00:25:38.100
All right, we have our inductive hypothesis, that 1 + 2 + 3 + ... + k = k times k + 1 over 2.
00:25:38.100 --> 00:25:47.000
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.
00:25:47.000 --> 00:25:51.800
So, we want to verify the statement below; we want to show that this is not a question mark--
00:25:51.800 --> 00:25:56.400
that it is, indeed, that the left side and the right side are equal to each other, for sure.
00:25:56.400 --> 00:26:00.900
We want to verify this; we want to make that question mark be absolutely an equals sign.
00:26:00.900 --> 00:26:07.100
What we notice is that we have p<font size="-6">k</font> here--our inductive hypothesis, p<font size="-6">k</font>.
00:26:07.100 --> 00:26:13.100
We can substitute p<font size="-6">k</font>, our hypothesis; and what we have here is the same thing as what we have here.
00:26:13.100 --> 00:26:16.300
So, we can plug in; we can swap out this stuff right here.
00:26:16.300 --> 00:26:19.100
Now, we have gotten our hypothesis into the game.
00:26:19.100 --> 00:26:22.300
We have been able to plug it in; so now, we can start using it--we can work things out.
00:26:22.300 --> 00:26:29.000
We are almost absolutely, certainly, going to use that inductive hypothesis; otherwise, we wouldn't need to be doing induction.
00:26:29.000 --> 00:26:32.600
We bring the hypothesis to bear somehow.
00:26:32.600 --> 00:26:36.400
We can plug it in, generally; and from here, we just have to simplify the equation.
00:26:36.400 --> 00:26:42.000
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.
00:26:42.000 --> 00:26:47.500
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."
00:26:47.500 --> 00:26:56.100
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<font size="-6">k + 1</font> is true.
00:26:56.100 --> 00:27:06.700
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<font size="-6">k + 1</font> is true.
00:27:06.700 --> 00:27:11.900
And we will have shown that p<font size="-6">k + 1</font> is true from p<font size="-6">k</font>, and we will have completed our inductive step.
00:27:11.900 --> 00:27:17.800
OK, we just worked this out: what we had on the left side was k times k + 1 over 2, plus k + 1.
00:27:17.800 --> 00:27:21.100
And then, on the right side, we had k + 1 times k + 2 over 2.
00:27:21.100 --> 00:27:28.200
So, we expand: k times k + 1 gets us k² + k; we can put this over a fraction, so that we can have them over common denominators.
00:27:28.200 --> 00:27:30.600
So, we have 2k + 2 over 2.
00:27:30.600 --> 00:27:39.100
We expand the right side, k + 1 times k + 2; that is going to be k times k, k², plus 2k + 1k, so 3k, plus 1 times 2, 2.
00:27:39.100 --> 00:27:41.800
So, we get k² + 3k + 2, all over 2.
00:27:41.800 --> 00:27:47.500
Now, we just combine these two fractions here, k² + k over 2, plus 2k + 2 over 2.
00:27:47.500 --> 00:27:54.000
It is going to be k² + k + 2k + 2, all over 2, which simplifies to a nice k² + 3k + 2, over 2,
00:27:54.000 --> 00:27:59.100
which is equal to k² + 3k + 2 over 2, which is, indeed, definitely always going to be true.
00:27:59.100 --> 00:28:04.500
So, we have just shown that, yes, our inductive step does work; we have proved the inductive step to be true.
00:28:04.500 --> 00:28:09.700
If we have p<font size="-6">k</font> true, then p<font size="-6">k + 1</font> must be true, from our logic.
00:28:09.700 --> 00:28:15.500
So, we have completed both steps: we have completed the base case (back a while), and we just completed the inductive step.
00:28:15.500 --> 00:28:19.000
That means that we have completed both of the parts necessary for a proof by induction.
00:28:19.000 --> 00:28:20.700
We have to prove both of those parts.
00:28:20.700 --> 00:28:31.600
We now know that p<font size="-6">n</font> 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.
00:28:31.600 --> 00:28:37.800
And I like to complete my proofs with a little square, just to say, "We have completed the proof; it is done."
00:28:37.800 --> 00:28:41.500
And there we are; that is an example of how proof by induction works.
00:28:41.500 --> 00:28:44.700
All right, at this level in math, you will often be directly told what to prove.
00:28:44.700 --> 00:28:48.900
You will be given some formula or some statement, and it is going to say, "Go prove this."
00:28:48.900 --> 00:28:54.000
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.
00:28:54.000 --> 00:29:00.000
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.
00:29:00.000 --> 00:29:06.000
However, sometimes you won't be given a formula.
00:29:06.000 --> 00:29:12.700
Instead, it is going to be your job to discover a pattern inside of that sequence, inside of what you are looking at;
00:29:12.700 --> 00:29:20.100
and then create some sort of hypothetical formula that will describe that pattern, and finally to prove that your formula will always work.
00:29:20.100 --> 00:29:23.100
So, the proof itself can be challenging; that is what we are working on.
00:29:23.100 --> 00:29:30.600
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.
00:29:30.600 --> 00:29:34.800
Sometimes, that is the hardest part: being able to look at what you have, figure out what the pattern here is,
00:29:34.800 --> 00:29:39.200
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.
00:29:39.200 --> 00:29:44.100
If you need to do this, and you find it difficult, I recommend checking out "Tips for finding patterns,"
00:29:44.100 --> 00:29:47.300
which is one of the parts in the lesson Introduction to Sequences.
00:29:47.300 --> 00:29:53.700
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.
00:29:53.700 --> 00:29:57.500
The formula is based on some sequence of statements, effectively.
00:29:57.500 --> 00:30:01.200
And a sequence is based on some sequence of numbers; so there is a lot of connection between them.
00:30:01.200 --> 00:30:06.900
This "Tips for finding patterns" inside of Introduction to Sequences--you will end up seeing a lot of things there.
00:30:06.900 --> 00:30:11.100
A lot of the ideas there, you can apply to looking at formulas, so that is a really good thing to check out,
00:30:11.100 --> 00:30:14.300
if you are having to work on that and you find it difficult.
00:30:14.300 --> 00:30:16.100
All right, we are ready for some examples.
00:30:16.100 --> 00:30:16.700
Prove that the below...
00:30:16.700 --> 00:30:21.100
Oh, by the way, if you just skipped directly to the examples, you definitely, definitely, definitely, in this case,
00:30:21.100 --> 00:30:26.600
want to go back to the working example first; so if you just skipped to this part directly, check out the working example first,
00:30:26.600 --> 00:30:30.800
because it will explain what is going on here, as opposed to being confusing and just not having any meaning.
00:30:30.800 --> 00:30:33.200
The working example will explain everything that is going on.
00:30:33.200 --> 00:30:36.100
If you just watched the whole lesson, I'm sorry; I didn't mean to...I'm sorry about that.
00:30:36.100 --> 00:30:37.300
Anyway, let's go on.
00:30:37.300 --> 00:30:39.900
Prove that the below is true for any positive integer n.
00:30:39.900 --> 00:30:48.900
We have 1² + 2² + 3² + ... + n² = n times n + 1 over 2n + 1.
00:30:48.900 --> 00:30:54.200
This is effectively our statement p<font size="-6">n</font>...not effectively; this *is* our statement p<font size="-6">n</font>.
00:30:54.200 --> 00:31:02.500
Adding all of the squares, 1² + 2²...up until n², is equal to n times (n + 1) times (2n + 1), all divided by 6.
00:31:02.500 --> 00:31:07.300
Our first thing to do is to show that the base case ends up being true.
00:31:07.300 --> 00:31:11.600
The base case would be what it would be if we plugged in a 1 for n, if it was just the first statement.
00:31:11.600 --> 00:31:15.800
What would that end up looking like? That is going to be...proving that would be equivalent to showing
00:31:15.800 --> 00:31:20.900
that these two sides are the same, that 1² is equivalent to 1 (plugging in 1 for our n),
00:31:20.900 --> 00:31:27.100
1 + 1, plugging in 1 for our n...2 times...plugging in 1 for our n...plus 1...all over 6.
00:31:27.100 --> 00:31:28.700
Does this end up working out to be the same?
00:31:28.700 --> 00:31:37.600
1² 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.
00:31:37.600 --> 00:31:42.200
Is 1, indeed, equal to 1 times 2 times 3...is 6...over 6?
00:31:42.200 --> 00:31:48.300
And yes, indeed, that would be 1 = 1; so we just showed that our base case ends up being true.
00:31:48.300 --> 00:31:51.300
The next thing that we want to work out is the inductive step.
00:31:51.300 --> 00:31:58.000
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.
00:31:58.000 --> 00:32:02.800
What is the thing we are assuming? The hypothesis: we are assuming that p<font size="-6">k</font>,
00:32:02.800 --> 00:32:08.600
which would be 1² + 2²...up until we get to some k²
00:32:08.600 --> 00:32:17.800
(any positive integer k) is equal to k...we plug in k for n...k + 1, times 2k + 1, all over 6.
00:32:17.800 --> 00:32:20.700
So, we assume that this is true; this is our assumption.
00:32:20.700 --> 00:32:23.800
We can use this later; we can plug it in.
00:32:23.800 --> 00:32:28.100
All right, we have our general thing here, p<font size="-6">n</font>, 1² + 2² + 3²...
00:32:28.100 --> 00:32:31.500
up until n², is equal to n times n + 1 times 2n + 1.
00:32:31.500 --> 00:32:37.000
And our inductive hypothesis is just saying, "What if we looked at some k, and we assumed that at k, it was true?"
00:32:37.000 --> 00:32:43.500
So now, we want to show--it is our job to now show--that p<font size="-6">k + 1</font> is true.
00:32:43.500 --> 00:32:47.000
It is our job to show that p<font size="-6">k + 1</font> ends up being true.
00:32:47.000 --> 00:32:57.800
Showing that p<font size="-6">k + 1</font> is true is going to end up being equivalent to showing that 1² + 2² + ...
00:32:57.800 --> 00:33:03.900
up until we get to (k + 1)²...now, here is the part...we don't want to put in (k + 1)²,
00:33:03.900 --> 00:33:07.600
because we want to somehow have our p<font size="-6">k</font> show up.
00:33:07.600 --> 00:33:10.900
We are going to have to apply our hypothesis in there somewhere.
00:33:10.900 --> 00:33:11.800
So, we want to have it show up.
00:33:11.800 --> 00:33:18.200
We realize that up in 1² + 2² ... + (k + 1)², well, what would be right before that?
00:33:18.200 --> 00:33:23.000
We go back, and instead of using (k + 1)² as the last thing, it would be easier to see in the pattern
00:33:23.000 --> 00:33:28.700
what is really there, to make it easier, to substitute this: + k² + (k + 1)².
00:33:28.700 --> 00:33:31.200
I will break this onto a different line, because now we are starting to get a little cramped.
00:33:31.200 --> 00:33:35.900
We want to show (we don't know for certain; it is up to us to verify) that that would be...
00:33:35.900 --> 00:33:51.700
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.
00:33:51.700 --> 00:33:57.000
So, at this point, we say, "We have 1² + 2² + ... up until k²,
00:33:57.000 --> 00:34:05.600
so we can swap that in for what is here at p<font size="-6">k</font>, which is this thing right here"--we can now swap that in.
00:34:05.600 --> 00:34:08.900
Now, we are going to move over here, so we have a little bit more room.
00:34:08.900 --> 00:34:20.700
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;
00:34:20.700 --> 00:34:22.600
plus...what is the thing that we still have left over?
00:34:22.600 --> 00:34:28.900
We still have (k + 1)² left over; we didn't substitute out for that; so, plus k + 1 squared.
00:34:28.900 --> 00:34:38.700
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.
00:34:38.700 --> 00:34:46.500
I will simplify that a little bit: that will be 2k + 2 + 1; so that would be 2k + 3, all over 6.
00:34:46.500 --> 00:34:51.400
OK, at this point, to show that they end up being the same on either side of that...
00:34:51.400 --> 00:34:55.100
"maybe-it-is," to show that each side is the same, that the sides are equivalent,
00:34:55.100 --> 00:34:58.800
we can just end up simplifying each of the sides, working with each side on their own.
00:34:58.800 --> 00:35:06.900
We work with expanding this part over here; k times...k + 1 times 2k + 1...k times 2k gets us 2k²;
00:35:06.900 --> 00:35:15.600
k times 1 is k, plus 1 times 2k, so + 3k; 1 times 1...plus 1; all over 6; plus...
00:35:15.600 --> 00:35:20.200
let's multiply this part by 6/6, because we know that we will want to put them together
00:35:20.200 --> 00:35:22.600
into a single fraction, so that we can compare the two things;
00:35:22.600 --> 00:35:28.800
(k + 1)² is (k + 1) times (k + 1); it becomes k² + 2k + 1.
00:35:28.800 --> 00:35:33.400
And is that, indeed, equal to...let's expand the right side; expand the far right first.
00:35:33.400 --> 00:35:41.200
k + 1 times k + 2 times 2k + 3...k times 2k gets us 2k²; k times 3 is 3k; 2 times 2k is 4k;
00:35:41.200 --> 00:35:49.200
so 3k + 4k is 7k; 2 times 3 is + 6; all divided by 6.
00:35:49.200 --> 00:36:00.500
So, we can keep expanding over here; k times 2k² is 2k³, plus 3k², plus k, all over 6.
00:36:00.500 --> 00:36:14.600
Plus...6k² + 12k + 6, all over 6; and is that equal to (k + 1) times (2k² + 7k + 6)?
00:36:14.600 --> 00:36:18.400
OK, how is this one going? I am going to do this one partially in my head.
00:36:18.400 --> 00:36:21.100
If you get lost here, just write it out, and you will see how it worked.
00:36:21.100 --> 00:36:24.500
k times 2k² is going to come out to be 2k³.
00:36:24.500 --> 00:36:31.200
k times 7k is 7k²; plus...1 times 2k²...7k² + 2k² is 9k²;
00:36:31.200 --> 00:36:41.300
k times 6 is 6k; 1 times 7k is 7k; 7k + 6k is 13k; and 1 times 6 is +6, all over 6.
00:36:41.300 --> 00:36:46.200
And finally, if we combine our two fractions on the left, then 2k³...
00:36:46.200 --> 00:36:50.900
everything will be divided by 6 over here...2k³ plus nothing on our other fraction,
00:36:50.900 --> 00:36:55.700
so that is just that...3k² + 6k²...we get 9k²;
00:36:55.700 --> 00:37:02.200
k + 12k + 13k...there are no constants on our left fraction, plus the one on our right fraction, so + 6.
00:37:02.200 --> 00:37:05.900
And is that, indeed, equal to 2k³ + 9k²?
00:37:05.900 --> 00:37:10.800
We see that that is, indeed, the exact same thing; thus, our inductive step right here
00:37:10.800 --> 00:37:14.300
(not our inductive hypothesis, but our inductive step) just checked out.
00:37:14.300 --> 00:37:18.400
So, we have now shown that the base case checks out; the inductive hypothesis checks out.
00:37:18.400 --> 00:37:24.700
So, combined, they show that this here is always true.
00:37:24.700 --> 00:37:28.700
We have just shown that combining these two things (the base case, p₁, being true,
00:37:28.700 --> 00:37:34.900
and if p<font size="-6">k</font> is true--our inductive hypothesis--then p<font size="-6">k + 1</font> is true, which we just showed here)--
00:37:34.900 --> 00:37:38.000
we combined those two things, so now we have shown that p<font size="-6">n</font> is true for all things:
00:37:38.000 --> 00:37:45.000
that 1² + 2² + 3²...up until + n² is equal to n(n + 1)(2n + 1), all divided by 6.
00:37:45.000 --> 00:37:49.400
We have completed our proof by induction.
00:37:49.400 --> 00:37:59.300
The second example: Show that, for n = 1, 2, 3...forever, that n³ + 2n is divisible by 3.
00:37:59.300 --> 00:38:05.500
So really, this is our statement, p<font size="-6">n</font>: p<font size="-6">n</font> is "n³ + 2n is divisible by 3."
00:38:05.500 --> 00:38:09.200
The first thing that we always have to do: we have to start by showing the base case.
00:38:09.200 --> 00:38:15.400
Our base case first: the base case is showing that the p₁ statement would be true.
00:38:15.400 --> 00:38:28.900
Verifying p₁ is the same thing as verifying that 1³ + 2(1) is divisible by 3.
00:38:28.900 --> 00:38:38.400
1³ + 2(1) is 1 + 2, or 3; that is divisible by 3--that checks out, so our base case just checked out; great.
00:38:38.400 --> 00:38:44.000
Next, we want to work on the inductive step.
00:38:44.000 --> 00:38:48.600
Always, the first thing we do in our inductive step is to write what our hypothesis is.
00:38:48.600 --> 00:38:51.000
What is the assumption that we can work from?
00:38:51.000 --> 00:38:56.100
Our hypothesis is going to be that p<font size="-6">k</font> ends up being true.
00:38:56.100 --> 00:39:09.200
What is p<font size="-6">k</font>? p<font size="-6">k</font> would be if we plugged in k for our n here: k³ + 2k is divisible by 3.
00:39:09.200 --> 00:39:13.600
This is our starting assumption: that k³ + 2k is divisible by 3.
00:39:13.600 --> 00:39:23.800
At this point, we now want to show that p<font size="-6">k + 1</font> is true.
00:39:23.800 --> 00:39:27.500
Showing that p<font size="-6">k + 1</font> is true is going to be the same thing as showing
00:39:27.500 --> 00:39:38.100
that k + 1 (plugging in k + 1 for n now), cubed, plus 2(k + 1) for n now, is divisible by 3.
00:39:38.100 --> 00:39:44.200
So now, we just need to show...if this is divisible by 3, then we will have proven our inductive step, as well.
00:39:44.200 --> 00:39:45.600
So, we will have shown the whole thing.
00:39:45.600 --> 00:39:57.300
From here on, let's just take a close look at (k + 1)³ + 2(k + 1).
00:39:57.300 --> 00:39:58.800
Hopefully, we will have enough room to work this out.
00:39:58.800 --> 00:40:02.400
(k + 1)³...well, we can write that as (k + 1)(k + 1)².
00:40:02.400 --> 00:40:07.000
What is (k + 1)²? That is k² + 2k + 1.
00:40:07.000 --> 00:40:11.400
Plus...2 times (k + 1)...that is 2k + 2.
00:40:11.400 --> 00:40:15.900
k + 1 times k² + 2k + 1...well, k times k² is going to be k³;
00:40:15.900 --> 00:40:20.900
k times 2k is 2k², plus 1 times k², so + 3k²;
00:40:20.900 --> 00:40:28.200
k times 1...+ 1k; plus 1 times 2k is 2k, so + 3k total; plus 1 times 1 is 1;
00:40:28.200 --> 00:40:33.500
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."
00:40:33.500 --> 00:40:44.200
Plus 2k + 2...OK, so at this point, we can realize, "What was our hypothesis? Our hypothesis was that k³ + 2k is definitely divisible by 3."
00:40:44.200 --> 00:40:47.600
Look: here is k³; here is 2k; let's bring them together.
00:40:47.600 --> 00:40:54.200
Now, we have k³ + 2k; and we will put everything else on the other side.
00:40:54.200 --> 00:41:01.000
So, 3k² + 3k...and we have a 1 here and a 2 here, so that combines to + 3.
00:41:01.000 --> 00:41:03.600
Now, we can look at each part of this independently.
00:41:03.600 --> 00:41:10.100
k³ + 2k is a thing; plus...and over here, we have a 3 here, a 3 here, and a 3 here;
00:41:10.100 --> 00:41:16.600
so we can pull a 3 out; 3 comes out of k² + k + 1.
00:41:16.600 --> 00:41:24.600
Now, at this point, we realize--look, by our inductive hypothesis, we knew that this is divisible by 3.
00:41:24.600 --> 00:41:30.300
We know that that is divisible by 3; furthermore, we have 3 times k² + k + 1;
00:41:30.300 --> 00:41:35.700
well, anything that we end up multiplying by 3 on it...well, that already has a factor of 3 multiplied in.
00:41:35.700 --> 00:41:44.400
So, it must be divisible by 3; so that means both parts that we are adding together are divisible by 3.
00:41:44.400 --> 00:41:50.400
If both parts that we add together are divisible by 3, then it must be that the entire thing is divisible by 3.
00:41:50.400 --> 00:41:54.400
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;
00:41:54.400 --> 00:41:58.100
I can divide this thing by 3; so even when we put them together, I can still divide the thing by 3.
00:41:58.100 --> 00:42:04.200
Since both parts are divisible by 3, that means that (k + 1)³ + 2(k + 1),
00:42:04.200 --> 00:42:06.500
which we just showed, has to be divisible by 3.
00:42:06.500 --> 00:42:10.500
So, we have just shown that, if p<font size="-6">k</font> is true, then p<font size="-6">k + 1</font> is true.
00:42:10.500 --> 00:42:14.900
So, we have now shown the inductive step; since we have shown that p₁ is true,
00:42:14.900 --> 00:42:17.700
and if something in the middle is true, then the next thing is true;
00:42:17.700 --> 00:42:21.600
then p₁ being true implies that p₂ must be true, by our inductive step,
00:42:21.600 --> 00:42:25.500
which implies that p₃ must be true, by our inductive step; p₄, p₅, p₆, p₇...
00:42:25.500 --> 00:42:34.400
So, we know that, forever and always, n³ + 2n is divisible by 3; we have completed our proof by induction.
00:42:34.400 --> 00:42:38.900
The next proof, the last example: Come up with a formula that gives the value of the nth partial sum
00:42:38.900 --> 00:42:45.100
of the sequence below: 1, 3, 5, 7, 9... then prove that your formula always works.
00:42:45.100 --> 00:42:47.700
The first few partial sums of the sequence are below.
00:42:47.700 --> 00:42:52.000
Our first partial sum would be just adding 1 together, so that is 1.
00:42:52.000 --> 00:42:57.300
Our next partial sum would be adding just 3 onto what we had before, so that would be 1 + 3.
00:42:57.300 --> 00:42:59.500
The next thing would be 5, so 1 + 3 + 5.
00:42:59.500 --> 00:43:07.700
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.
00:43:07.700 --> 00:43:10.100
If we were to keep going with this pattern, what would be next?
00:43:10.100 --> 00:43:18.700
Well, that would be 11 next; we are adding by 2 each time, so 1 + 3 + 5 + 7 + 9 + 11.
00:43:18.700 --> 00:43:21.100
Let's see if we can figure out what the pattern going on here is.
00:43:21.100 --> 00:43:23.600
1 on its own--well, that is just 1.
00:43:23.600 --> 00:43:37.900
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.
00:43:37.900 --> 00:43:49.300
We have an idea of what the formula is: it looks like the nth partial sum is going to be equal to n²; great.
00:43:49.300 --> 00:44:04.100
What we have here is 1 + 3 + 5 + ... + something...whatever we end on...is equal to n².
00:44:04.100 --> 00:44:08.300
We need to figure out what we end on; how do we call out each member of this sequence?
00:44:08.300 --> 00:44:10.800
Well, we can remember what we did in arithmetic sequences.
00:44:10.800 --> 00:44:14.800
We see that we have 1 as our starting place; we add by 2 each time.
00:44:14.800 --> 00:44:23.800
So, we could realize that the nth term here, a<font size="-6">n</font>, is equal to 2n - 1.
00:44:23.800 --> 00:44:30.400
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.
00:44:30.400 --> 00:44:33.800
We see that what we are going up to is 2n - 1.
00:44:33.800 --> 00:44:48.200
So, our statement, the p<font size="-6">n</font> statement, is that 1 + 3 + 5, working up until 2n - 1, is equal to n², for any n.
00:44:48.200 --> 00:44:54.100
So, that is what we have figured out that our formula is for how we are getting these partial sums.
00:44:54.100 --> 00:44:58.200
As we add up more and more terms of this sequence, we have now figured out our formula.
00:44:58.200 --> 00:45:05.400
We have figured out how this pattern of adding things up comes to be.
00:45:05.400 --> 00:45:09.300
We see that we have n² coming out, if we do this each time.
00:45:09.300 --> 00:45:14.600
On the first term, n = 1, we have 1; at n = 2, we have 4; n = 3...
00:45:14.600 --> 00:45:16.900
We see that, each time, it is just squaring that number.
00:45:16.900 --> 00:45:21.300
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.
00:45:21.300 --> 00:45:28.500
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.
00:45:28.500 --> 00:45:30.800
At this point, we are now ready to prove this.
00:45:30.800 --> 00:45:39.000
All right, so now it is just up to us to prove that this is, indeed, true: that our statement p<font size="-6">n</font> is true for any value of n:
00:45:39.000 --> 00:45:45.800
that 1 + 3 + 5...up until + 2n - 1 is equal to n², no matter what n we put in, as long as n is a positive integer.
00:45:45.800 --> 00:45:49.900
So, the first thing to prove: always prove the base case first, because it is almost always easier.
00:45:49.900 --> 00:45:52.500
It also helps you understand how the thing comes together.
00:45:52.500 --> 00:45:57.500
So, the base case: showing that p₁ is true is going to be the same thing as showing that 1,
00:45:57.500 --> 00:46:04.000
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²?
00:46:04.000 --> 00:46:06.400
Yes, 1 is equal to 1; that was pretty easy.
00:46:06.400 --> 00:46:08.300
So, there is our base case, finished.
00:46:08.300 --> 00:46:14.600
Next, we do the inductive step; now we want to show that the inductive step is going to end up being true.
00:46:14.600 --> 00:46:19.800
The first thing that we always do: we assume our hypothesis first; what is our hypothesis going to be?
00:46:19.800 --> 00:46:22.800
Our hypothesis will be that p<font size="-6">k</font> is true.
00:46:22.800 --> 00:46:33.900
What is the statement p<font size="-6">k</font>? Well, that would be 1 + 3 + ... up until we get to +...plug in k for n...2k - 1 = k².
00:46:33.900 --> 00:46:39.800
So, we are assuming that 1 + 3 + ... + 2k - 1 is equal to k².
00:46:39.800 --> 00:46:44.700
OK, with that assumption that this thing is true, we need now to show that k + 1 is going to be true, as well.
00:46:44.700 --> 00:46:50.900
So now, we want to show that k + 1 is true.
00:46:50.900 --> 00:47:01.300
Showing that k + 1 is true is going to be equivalent to showing that 1 + 3 + ... + 2k - 1...
00:47:01.300 --> 00:47:10.100
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,
00:47:10.100 --> 00:47:14.000
swapping out that n here, as well, for k + 1, squared.
00:47:14.000 --> 00:47:18.300
Now, remember: we want to have our hypothesis show up somewhere.
00:47:18.300 --> 00:47:20.000
We have to get our hypothesis to show up somewhere.
00:47:20.000 --> 00:47:23.200
So, we realize that that is really this part up here.
00:47:23.200 --> 00:47:34.700
So, we can rewrite this as 1 + 3 + ... until we get to back a step of two...so that would be 2k - 1;
00:47:34.700 --> 00:47:42.200
forward a step by 2...we see that that would be 2k + 1; if we work out this value here,
00:47:42.200 --> 00:47:46.500
we end up seeing that it is the same thing here; 2k + 2 - 1 is just 2k + 1.
00:47:46.500 --> 00:47:50.400
And we want to show that that is equal to (k + 1)².
00:47:50.400 --> 00:48:04.800
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."
00:48:04.800 --> 00:48:13.800
That means that what we have in the thing we are trying to show, p<font size="-6">k + 1</font>, that part of it, is going to just be equal to k², right here.
00:48:13.800 --> 00:48:21.700
So, we can swap out k² here; so now we have k² plus what still remains; that is 2k + 1.
00:48:21.700 --> 00:48:24.300
And we want to show that this is true, so it is a question mark here.
00:48:24.300 --> 00:48:28.100
We don't know for sure that it is true yet; it is up to us to show that it ends up being true.
00:48:28.100 --> 00:48:35.800
Plus what remained there, 2k + 1: is that equal to (k + 1)²?
00:48:35.800 --> 00:48:42.900
Well, let's just simplify it: we have k²; we expand this; well, k² + (2k + 1)...that is just 2k + 1;
00:48:42.900 --> 00:48:45.900
is that equal to...what do we get when we expand (k + 1)²?
00:48:45.900 --> 00:48:53.400
Well, that is k² + 2k + 1; we end up seeing that that is indeed true.
00:48:53.400 --> 00:48:57.800
That is always going to end up being true, so we have shown that our inductive step is true.
00:48:57.800 --> 00:49:01.400
With this hypothesis in mind, we know that the next thing down the line...
00:49:01.400 --> 00:49:04.800
with p<font size="-6">k</font> being true, we know that p<font size="-6">k + 1</font> must be true.
00:49:04.800 --> 00:49:09.300
Because we know that our base case is true (p₁ is true), and we know that if something is true,
00:49:09.300 --> 00:49:12.900
then the next thing has to be true; then since p₁ is true, the next thing must be true.
00:49:12.900 --> 00:49:16.700
p₂ is true; p₃ is true; p₄ is true; p₅ is true; p₆ is true.
00:49:16.700 --> 00:49:21.300
And the fireworks keep going forever and ever; we see that everything is always true.
00:49:21.300 --> 00:49:28.200
We have that this statement ends up being true for absolutely every single n that we would plug into it.
00:49:28.200 --> 00:49:31.900
We have completed the proof; our proof is done--pretty cool.
00:49:31.900 --> 00:49:37.300
The only really challenging part there--that wasn't that difficult of a proof by induction, compared to the ones that we did previously--
00:49:37.300 --> 00:49:40.800
the challenging part there was being able to figure out what that formula was in the first place.
00:49:40.800 --> 00:49:44.800
So, once again, if you have difficulty with that, I recommend checking out the Arithmetic Sequences and Series.
00:49:44.800 --> 00:49:51.400
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.
00:49:51.400 --> 00:49:53.000
All right, we will see you at Educator.com later--goodbye!