| Transcript
for the Math
Jam "Induction"
on Jun 26. |
| Math Jam hosted by ANieh
(Ari Nieh ). |
rrusczyk19:33:28
Let's get started. It appears that our regularly scheduled instructor couldn't make it tonight, so you're stuck with me!
rrusczyk19:33:33
Welcome to the Math Jam! Tonight we will be introducing the powerful proof technique, induction.
julianna19:37:13
what is induction?
rrusczyk19:37:28
That is why we are here -- to find the answer to the question, "What is induction?"
rrusczyk19:37:40
The techniques we're discussing are both important and powerful, but do not require any advanced machinery. A strong grasp of basic algebra is all you'll need.
Math Champion19:37:44
is this an intro to induction or is this like challenging problems using induction
rrusczyk19:37:52
This is an introduction to induction.
Math Champion19:38:07
let's get started then :)
rrusczyk19:38:11
Good idea!
rrusczyk19:38:33
Many of the statements we use in mathematics are secretly several statements at once. We're so accustomed to this usage that we usually don't even think about it.
rrusczyk19:38:40
For example, when we say something like:
rrusczyk19:38:49
rrusczyk19:38:59
We are actually saying a whole lot of things:
rrusczyk19:39:05
rrusczyk19:39:23
Our original equation can be seen as a shorthand for the entire collection of equations of that form.
rrusczyk19:39:37
Now, we have to be a bit careful about what we mean by "entire collection". Which possible values of x make the above equation true?
harmony19:39:51
real values
pytheagle19:39:51
real numbers
rrusczyk19:39:57
It does work for real numbers.
rrusczyk19:39:59
Any others?
takyiuliu19:40:09
complex numbers
Funkymunk19:40:09
Complex numbers
The.forgotten.user19:40:09
complex numbenrs
juggler19:40:16
Complex?
Eulers_Apprentice19:40:16
complex numbers?
rrusczyk19:40:26
Indeed, it works for complex numbers, too.
rrusczyk19:40:38
And now, I'd like to pause to introduce our instructor!
rrusczyk19:41:15
I'd like to introduce your instructor, Ari Nieh. Ari studied mathematics at Harvey Mudd College and UC Berkeley, completing his PhD in quantum topology in 2007. He has worked at Canada/USA Mathcamp for more than a decade as a counselor, teacher, and choir director. He's also an accomplished musician, and I enjoyed his singing very much in Mathcamp sessions when I visited the camp a few years ago!
rrusczyk19:41:24
He'll pick up where I'm leaving off!
ANieh19:41:41
Good evening, all
ANieh19:42:06
I'm terribly sorry for arriving late, but let's jump right in.
ANieh19:43:14
So as we've seen, the above equation works for a variety of mathematical systems.
ANieh19:43:44
To be precise, we'll need to specify exactly where we want things to work.
ANieh19:45:18
For some statements, they may only be true (or only make sense at all) for more restricted values of the variable. For example, consider the statement:
ANieh19:46:38
ANieh19:46:49
What are the values of N for which this equation makes sense?
julianna19:47:35
natural numbers
k00lperson19:47:38
Any positive number
bargello19:47:42
n=1,2,3,...
SR-7119:47:53
whole numbers
ANieh19:48:24
It's not clear exactly what the expression means for non-integers.
ANieh19:48:59
We can include zero or not, but for the sake of simplicity, let's start at 1. Then the above statement is shorthand for the collection of statements:
ANieh19:49:06
ANieh19:49:28
The tool I'm going to talk about today is called "proof by induction", and it's often used to prove statements which are indexed by the natural numbers in this way.
ANieh19:49:53
Suppose that we have a collection of statements, one for each natural number, that we would like to prove. Let's call these statements P(1), P(2), P(3), et cetera. Proof by induction works as two-step process.
ANieh19:50:11
[A] First, we show that the first statement in our collection is true. Usually, we can find a fairly direct proof for P(1), because it's the simplest case.
ANieh19:50:23
[B] Second, we show that P(N) implies P(N+1) for all values of N. That is, we want to prove that if the Nth statement is true, then the one after it must also be true.
ANieh19:51:06
If we can do both of these steps, then the Principle of Mathematical Induction states that all of the P(N) are true! This makes sense from a intuitive perspective. We know that P(1) is true by [A]. By [B], the truth of P(1) implies the truth of P(2). And then by [B], the truth of P(2) implies the truth of P(3). And so on.
Patryk2219:51:16
is step b the same as assuming true for p = n and proving true for p = n+1?
ANieh19:51:21
Yes.
Mewto5555519:51:37
This seems limited, won't it only show it for integers?
ANieh19:52:11
Not exactly. All that matters, for now, is that there is one statement for each integer.
ANieh19:52:22
(Sorry, positive integer.)
ANieh19:52:37
The statements themselves do not have to be equations, although they are for now.
ANieh19:53:03
One pleasing metaphor for this process is setting up dominoes to knock over. [B] consists of putting the dominoes sufficiently close together that each domino will hit the next one if it is given a push. [A] is the push we give the first domino.
xpmath19:53:40
Or climbing ladders one step at a time!
ANieh19:53:45
Exactly.
ANieh19:54:16
ANieh19:54:33
[A] is to prove P(1), which we call the "base case". What is P(1)?
The.forgotten.user19:54:43
1=1(1+1)/2 so P(1) is true
Math Champion19:54:47
ok, so its true for P(1) since 1(2)/2=1
rpond19:54:50
for 1, 1(1+1)/2 = 1(2)/2 = 1
ANieh19:54:59
Right. And that's obviously true. So now we need to do [B], which is called the "induction step". To show P(N) implies P(N+1), we will assume P(N) is true, then use it to prove P(N+1).
ANieh19:55:13
ANieh19:55:21
What does P(N+1) look like?
dragon9619:55:40
1+2+...+n+(n+1)=(n+1)(n+2)/2
ANieh19:56:03
ANieh19:56:10
Now, how can we get from P(N) to P(N+1)?
Ronnicus19:56:24
Wait are you replacing the N with N+1?
ANieh19:56:26
Yes.
RoFlLoLcOpT19:56:29
add (n+1)
pytheagle19:56:33
add (n+1)?
Mewto5555519:56:35
add N+1 to both sides of P(N)
ANieh19:57:04
Exactly. We just add N+1 to both sides. Then we get:
ANieh19:57:12
ANieh19:57:31
Which is exactly P(N+1).
ANieh19:57:36
So now we've proved both [A] and [B], and therefore the statement is true for every natural number!
Jesse19:58:22
This is like recursion in computer programming.
ANieh19:58:31
Indeed, it's very similar.
ANieh19:58:42
We build on what we've already proved.
ANieh19:58:52
Now that we've seen an example, let's try another with you leading the way.
mathdriven19:59:08
why can't we just skip a?
ANieh19:59:15
The base case could be false.
ANieh19:59:23
In which case, our entire proof falls apart
xpmath19:59:30
because then you don't have anything to start on-you can't climb nothing!
ANieh19:59:35
Next problem:
ANieh19:59:38
Jongao19:59:59
Start with base case 1
ReseesPieces20:00:05
start with the first case 1
qwertythecucumber20:00:10
1 = 1^2, so P(1) is good
ANieh20:00:18
ANieh20:00:38
And what's the induction step?
Math Champion20:01:02
you need to prove P(N+1) works when P(N) works
BarneyRocks20:01:21
topofmath20:01:24
Krrish20:01:28
so add N+1 to both sides of the equation
ANieh20:01:40
ANieh20:02:24
So, there's some confusion now about how this next equation comes about
ANieh20:03:26
P(N+1) is obtained by using (N+1) as the natural number in your P statement.
ANieh20:03:50
And that's how we get the statement:
ANieh20:03:53
ANieh20:04:03
which now, we need to prove
ANieh20:04:15
How can we prove that statement, given P(N)?
bargello20:04:29
we can add 2(n+1) -1 to both sides of the induction hypothesis and then simplify on the right
ANieh20:05:08
We add 2N+1 to both sides, which yields:
ANieh20:05:17
ANieh20:05:30
And we're done.
ANieh20:06:21
Depending on the problem, we might not always want to start with the base case N=1. Suppose we want to prove that:
ANieh20:06:29
ANieh20:06:38
The.forgotten.user20:06:59
we must find the least N for wihich the statement is true
Funkymunk20:07:05
sufficiently large values of N? How large is sufficiently large?
ANieh20:07:20
That's exactly the question we'd like to answer. How large is large enough?
connaissance20:07:35
N=4
helagha20:07:40
N=4
RoFlLoLcOpT20:07:42
n=4 gives 16<24, so 4 is the smallest
ANieh20:07:57
ANieh20:08:12
er, "And the induction step?"
ANieh20:09:01
First, we should take
ANieh20:09:14
RoFlLoLcOpT20:09:24
bargello20:09:38
assume 2^n
ANieh20:09:51
and how do we prove that?
The.forgotten.user20:10:57
ANieh20:11:40
Ronnicus20:12:33
wait, why does N! *2= N! * (N+1)?
ANieh20:12:50
It doesn't, but N + 1 > 2
ANieh20:13:19
Now, given the problems we've done so far, you might think that induction is useful in a rather narrow way, since we've always known the correct equation in advance! Clearly, that's not how real mathematicians work. You don't always know what you're trying to prove. However, we can still use induction to solve more open-ended problems.
ANieh20:13:39
First, we'll spot a pattern that seems to hold for the first few values of N, and then we'll use induction to prove it.
ANieh20:13:51
So here's the problem:
ANieh20:14:01
ANieh20:14:18
How should we start?
Math Champion20:14:28
try values for 1, 2, and 3
connaissance20:14:30
Start with small N
ANieh20:14:38
ANieh20:14:49
What's the pattern?
rpond20:14:57
looks like (n+1)! - 1
cowpi20:15:00
(N+1)! - 1
dragon9620:15:04
(N+1)! -1
ANieh20:15:17
ANieh20:15:26
We've already done several base cases, so we just need the induction step.
ANieh20:16:41
We start with P(N)
ANieh20:17:30
ANieh20:19:47
Notice that every time we do one of these, we need to find a way to relate P(N) to P(N+1). Sometimes it's obvious, but sometimes less so. It can be helpful to "work backwards" from P(N+1) to find out exactly where we can apply P(N).
ANieh20:20:02
xpmath20:20:27
Wouldn't factoring be better for that?
ANieh20:20:45
It certainly could be, but let's assume we don't know any number theory for the moment.
bargello20:20:54
1^3-1=0 is a multiple of 3
ANieh20:21:09
Pretty easy base case. So let's try the induction step. What does the statement P(N+1) look like?
dragon9620:21:25
(n+1)^3-(n+1)
justinahmann20:21:29
(N+!)^3-N-1 is a multiple of 3!
ANieh20:21:38
ANieh20:21:43
What's the best way to relate that back to P(N)?
dragon9620:22:01
expand it
PowerOfPi20:22:07
expand
ANieh20:22:14
ANieh20:22:18
Now what?
Mewto5555520:22:53
well we know n^3-n=0mod3 so we can subtract that dude out
ANieh20:23:07
Exactly; we want to relate this back to P(N)
ANieh20:23:17
ANieh20:23:42
ANieh20:24:16
Many of you have pointed out that this can be solved in other ways; that's certainly true, but it's rather neat that we can do it with induction as well.
Ronnicus20:24:40
So we have proved that the equation holds true for all NATURAL numbers?
ANieh20:25:04
Yes. We proved it for N = 1, and then we proved that if it works for N, it works for N + 1 as well.
ANieh20:25:43
Before we move on, I have a quick question: are people interested in seeing a proof that induction works? Or are you happy to take it on faith for now?
dragon9620:26:05
can we use induction for this proof?
ANieh20:26:14
Definitely not! That would be circular reasoning.
ANieh20:26:30
So, the statement we're trying to prove is:
ANieh20:27:30
If we prove the base case, and if we prove P(N) implies P(N+1), then all the P statements are true
ANieh20:27:46
Our proof of the Principle of Mathematical Induction is going to be a proof by contradiction. Suppose we have proved both [A] that P(1) is true, and [B] that P(N) implies P(N+1) for all N, but the conclusion fails: that is, there is at least one number N such that P(N) is false.
ANieh20:28:08
Let S be the set of numbers N such that P(N) is false. Let's look at the least element of S, which we'll call K. Is it possible that K = 1?
Funkymunk20:28:23
No, thats our base
FlyAgaric20:28:32
No because that was the base case
ANieh20:28:43
Clearly K cannot be 1, because by [A] we know that P(1) is true.
PowerOfPi20:29:12
But what about N^2>N!?
ANieh20:29:41
Right now, we're doing it for a base case of 1. You'd have to modify the proof slightly to apply it more generally.
ANieh20:29:55
So P(K) is false, but P(N) is true for all N less than K. In particular, let's look at the statement just before P(K), which is P(K-1). Because K > 1, P(K-1) is a statement in our collection, and it must be true. Now, where is the contradiction?
speedcuber20:30:27
if P(K-1) is true, then P(K) must be true
Funkymunk20:30:30
Because P(K-1), P(K-1+1) = P(K) must be true
Mewto5555520:30:36
P(K-1+1)=P(K) is true but P(K) is not true so ZOMG THIS DUDE IS WRONG!
ANieh20:30:45
By [B], if P(K-1) is true, then P(K) should also be true. This is a contradiction, and hence our assumption must have been false: the set S was empty. So P(N) is true for all N.
The.forgotten.user20:31:00
So we can take it on faith that Proof by Contradiction works? Or is there a proof for that too?
ANieh20:31:30
An excellent question! I would advise you to take it on faith for now, but if you someday study metamathematics, you may eventually believe otherwise.
ANieh20:31:44
Most mathematicians are willing to take that on faith
ANieh20:32:06
Next, I'd like to talk about another form of induction, which is called "Strong induction".
ANieh20:32:14
With strong induction, the base case is the same. The induction step, however, relies on assuming that P(1), P(2), ... P(N) are all true, and using that to prove P(N+1).
ANieh20:32:30
Here, the domino metaphor doesn't really work. This is more like peer pressure: after Persons 1 through N have all bought Soulja Boy's new single, Person N+1 gives in and buys it too.
The.forgotten.user20:32:39
was the other way called "Weak Induction"?
ANieh20:32:57
It can be, but many people just call it "induction".
ANieh20:33:13
Let's use strong induction to prove that every natural number is the product of one or more primes. (I'm sure you all know this is true, but you've probably never proved it before!) What is our base case?
Mewto5555520:33:39
1 is not the product of primes....
ANieh20:33:46
Exactly. I should have said, "every natural number greater than one".
qwertythecucumber20:33:53
2 then
ANieh20:34:02
Now, P(N) is the statement, "N is a product of one or more primes." If we assume P(2), ... , P(N) are all true, then how can we prove P(N+1)?
xpmath20:35:11
Is this equivalent to the fundamental theorem of arithmetic?
xpmath20:35:14
well part of it; the existence
ANieh20:35:23
Yes, not the uniqueness.
gh62520:35:43
If N+1 is prime, then we are done. If N+1 isn't prime, then it must be the product of two or more of the numbers 2, 3, 4, ..., N. Since these are each multiples of one or more primes, we are done.
ANieh20:35:48
Exactly!
ANieh20:36:03
ANieh20:36:20
And by our induction hypothesis, both A and B are products of one or more primes, and therefore N+1 is as well.
SwimminTwinkie0120:36:28
so you have to make sure p(1) and p(2) are true before you go into proving p(n+1)? so its like you have two base cases just to be sure?
ANieh20:36:40
Nope, here we only needed one base case: N = 2.
speedcuber20:37:03
so we assume the one base case holds true up to n then prove P(n+1)?
ANieh20:37:20
Yes, and that proves it for all numbers greater than or equal to the base case.
pytheagle20:37:31
But how can we assume that it's true for P(2), P(3), ... P(N)? What if it's not?
ANieh20:37:46
We're not assuming that's true.
ANieh20:38:07
Rather, we assume it in order to prove N + 1, then immediately un-assume it!
ANieh20:38:47
Before we finish, there's one other important thing I'd like to mention. We've used induction largely to prove combinatorial / number theoretic identities, but its applications are actually much wider. Induction comes up in geometry, topology, analysis, graph theory, set theory, theoretical computer science, and all kinds of algebra. Anywhere there are natural numbers or recursively defined structures, there's likely to be induction. And that's pretty much all mathematics!
connaissance20:38:54
The proof for strong induction is fundamentally the same as weak induction, right?
ANieh20:39:02
Yes.
ANieh20:39:30
I would like to leave you with some problems to solve using induction. If you've been following fairly well, trying some of these would be a good way to test yourself. Some of them are ideas you may have seen before and proved by different methods.
justinahmann20:39:47
induction comes up in geometry?!?!
ANieh20:39:51
Yes.
nintendonumbers80820:39:57
will you ever use induction to prove calculus?
ANieh20:40:06
Certainly.
futbill202520:40:23
can you give us an example of induction in geometry
ANieh20:40:28
Certainly:
ANieh20:40:34
HiDN42820:40:55
Such as the surface area of a spere?
ANieh20:41:17
That's an excellent example: the surface area of an n-dimensional sphere can be derived by induction.
ANieh20:41:39
I'm going to give a few more problems for you to work on on your own:
ANieh20:41:50
ANieh20:41:57
ANieh20:42:32
Ronnicus20:42:37
Can you post this on the message board so we can compare solutions and such
ANieh20:42:46
Yes, I'll do that.
ANieh20:42:56
PowerOfPi20:43:09
WHich message board?
ANieh20:43:14
Pre-olympiad
The.forgotten.user20:43:17
nonempty?
ANieh20:43:20
nope!
Mewto5555520:43:25
wait for the fibonacci one what is the 0th fibonacci number defined as?
ANieh20:43:36
The zeroth Fibonacci number is 0
gh62520:43:41
The third one doesn't need induction.
ANieh20:43:56
Some of them don't, but it's interesting to solve them that way.
ANieh20:44:09
ANieh20:44:22
ANieh20:44:35
ANieh20:44:57
One last problem for those of you who have seen a bit of graph theory. Suppose a connected graph in the plane has V vertices and E edges, and it divides the plane into F faces. Prove that V - E + F = 2. (Hint: use induction on V.)
ANieh20:45:04
(If you're unfamiliar with those terms but want to try the problem anyway, you can see some connected graphs in the plane here: http://mathworld.wolfram.com/PlanarGraph.html . The red dots are vertices, the black lines are edges, and the white regions are faces.)
The.forgotten.user20:45:27
isn't that euler's theorem?
ANieh20:45:30
Yes
ANieh20:45:39
I'll remain online a bit longer if you want to ask more questions or bounce ideas off me. Thanks for coming, and I hope you enjoyed the Math Jam!
Mewto5555520:47:53
wait i dont see the problems on the forum
ANieh20:48:04
I'll post them there soon.
justinahmann20:49:03
did euclid use induction?
ANieh20:49:28
Not that I know of.
ANieh20:49:42
Archimedes did infinite descent, which is similar.
SonyWii20:50:03
What is quantum topology?
ANieh20:50:19
It's a kind of topology that lies at the intersection of topology and algebra
ANieh20:50:29
google "Jones polynomial" to get an introduction!
juggler20:50:36
do you know any good resources to help us with induction and other proof techniques?
rrusczyk20:50:38
Mathematical Circles, our Intermediate Algebra and Intermediate Counting, Art and Craft of Problem Solving, Problem Solving Strategies.
speedcuber20:51:00
before you mentioned metamathematics, so is that like "thinking about mathematics"?
ANieh20:51:18
It's foundational mathematics: set theory and logic
ANieh20:51:27
although it's certainly related to philosophy.
nintendonumbers80820:51:59
is infinite descent starting from a fixed value and proving cases down until one?
ANieh20:52:30
Not exactly; it's more like a cross between induction and contradiction.
HiDN42820:52:45
would the book, The Moment of Proof, help me with induction?
ANieh20:53:05
I'm not familiar with that book, but most introductions to proof techniques will discuss induction.
Ronnicus20:53:10
What is the most commonly used proof technique?
ANieh20:53:17
It varies tremendously!
Mewto5555520:53:21
Do you ever use induction in quantum topology?
ANieh20:53:26
Absolutely.
SonyWii20:53:33
Is there going to a Math Jam for proving things with other methods?
ANieh20:53:46
That's a question for Mr Rusczyk.
HiDN42820:55:13
At waht math class would i really start learning much more about proofs(e.g. math analysis, calc
ANieh20:55:36
Often, that'll show up in the first two years of college.
rrusczyk20:55:55
We do proofs in nearly all of our classes at AoPS.
ANieh20:55:56
Depends on where you are.
rrusczyk20:56:10
Sony: we may do another one in late fall, or next spring.
mathemagician172920:56:26
I think i'm overlooking something, but why was the example with the natural numbers >1 an example of strong induction?
ANieh20:57:25
Because the two factors were both less than N + 1, but not necessarily N itself
ANieh20:57:32
in fact, never N!
HiDN42820:57:56
What math classes is that? calculus bc?
ANieh20:58:34
Usually there are some proofs in BC calculus, but you may not get lots of serious proofs until abstract algebra or real analysis, depending on your teachers' style.
SonyWii20:59:24
Can you show an example of a calculus proof?
ANieh21:00:06
Sure.
ANieh21:00:51
Any function whose Nth derivatives are zero is a polynomial of degree at most N - 1.
ANieh21:01:16
Base case: N = 1.
ANieh21:01:43
All functions with vanishing first derivative are constants.
ANieh21:02:18
Now, assume true for N, and suppose we have a function f whose N + 1st derivative is zero.
ANieh21:02:50
Then consider the function f' .
ANieh21:03:14
The nth derivative of f' is zero, so f' is a polynomial of degree at most n - 1.
ANieh21:03:25
so we antidifferentiate
ANieh21:03:36
and f is a polynomial of degree at most n.
HiDN42821:03:59
I heard somewhere that an author proved god using induction as part of his step. Is this true? (sorry to the atheists)
ANieh21:04:22
When philosophers use the term "induction", they're not using it quite the same way mathematicians do.
ANieh21:04:42
"inductive reasoning" means reasoning from the general to the specific
ANieh21:04:59
contrasting with "deductive reasoning", which goes from the specific to the general.
ANieh21:05:30
Any other questions?
Ronnicus21:06:38
I saw a movie involving the IMO that said induction is "dangerous at times" why is this ?
ANieh21:06:58
I have no idea! I have been using induction for many years, and so far I haven't been harmed by it.
FlyAgaric21:07:13
I saw this in my math textbook but it wasn't similar to this. We skipped that chapter. Is that like what you just said?
ANieh21:07:23
I couldn't tell you without reading your book.
nintendonumbers80821:07:29
isn't that "hard problems"?
Ronnicus21:07:42
YES MAN
HiDN42821:07:45
Have you ever proved something important? like you were the first to prove it?
ANieh21:08:02
I have proved things that I was the first to prove, but I wouldn't call them important.
Ronnicus21:08:05
The USA coach, yufang said that
ANieh21:08:23
Not many mathematicians prove something "important", though.
ANieh21:09:37
I think we're about done here. I'll post the problems to the forum now. It was nice "meeting" you all!
