- Thread starter
- #1

- Thread starter matqkks
- Start date

- Thread starter
- #1

- Jun 14, 2013

- 27

Hello.

I'm using phone now. So I can't write in detail. Sorry.

You can convince them with "Principle of mathematical Induction. "

If you have a book "introduction to real analysis" from Bartle, please see p.12-13.

I'm so sorry not to write here in detail.

Please click.

I uploaded about the contents in my blog with taking picture.

^^*

Last edited:

- Jun 26, 2012

- 45

P(0) and $P(0)\Rightarrow P(1)$. Therefore you have proven P(1). So you proven that

P(1) and $P(1)\Rightarrow P(2)$. Therefore you have proven P(2). Etc.

As for the real life example, I don't realy know the level of your students, so I can't provide one. Maybe the direct formula for a sequence defined by recursion? That sequence can be given a pratical interpretation. I can only remember the Fibonnaci sequence, but the general formula might be more confusing than enlightening.

- Jan 17, 2013

- 1,667

- May 31, 2013

- 119

- Jan 30, 2012

- 2,525

It's curious that you said they doubt that (supposed) proofs using induction are (valid) proofs and not that they don't understand induction. Maybe these students are extremely smart in the manner of, say, L.E.J. Brouwer, the founder of intuitionism, who did not think that proofs using the law of excluded middle or reasoning by contradiction are valid. Indeed, some very smart people find induction to be a somewhat circular principle and require restrictions on the complexity of induction statements, i.e., P(n). Their reasoning goes something like this. Induction for all possible P(n) is used as an axiom schema in Peano arithmetic, i.e., it serves to define what natural numbers are. But if P(n) uses a quantifier, the quantified variable is supposed to range over natural numbers, so in order to understand the meaning of P(n), we already need to understand natural numbers. So, knowing what natural numbers are involves understanding infinitely many instances of the induction schema, and this in turn requires understanding natural numbers as the domain of quantification. This may motivate some to consider induction for quantifier-free P(n) only. It turns out that grading induction statements by quantifier complexity is not only philosophically motivated, but leads to interesting results relating proof theory and computational complexity.Some students are not convinced that a proof by mathematical induction is a proof.

I don't claim that I fully understand this argument, and I doubt that this is these students' concern.

I see two possible reasons for not understanding induction. The first one is the failure to grasp some prerequisites. For example, if a person does not know that $P(3)\Rightarrow P(4)$ follows from $\forall n\,(P(n)\Rightarrow P(n+1))$, then of course s/he will have trouble seeing that $P(0)$ and $\forall n\,(P(n)\Rightarrow P(n+1))$ imply $P(4)$. Or the person may not understand quantifiers at all.

The second, probably, more likely, reason is being overwhelmed by new concepts and details. This may happen if a student is presented with an algorithm for constructing a proof by induction mixed with or instead of an explanation for why induction is a valid argument. Imagine hearing in a rapid sequence: "property"… "predicate"… "basis"… "inductive step"… "implies"… "n = k+1"… The student may think, "What on earth is a predicate and how it is different from a property?" "And what again is an implication? I don't remember its truth table". "What is the significance of having two different variable names n and k?"

I like the explanation in post #3. I would make sure that students understand Modus Ponens (no pun intended with the name of the author of post #3) and would write $P(0)$, $P(0)\Rightarrow P(1)$, …, $P(5)\Rightarrow P(6)$. If someone does not understand how to derive $P(1)$, …, $P(6)$ from this, I would be really surprised.

To finish, I'd like to ask a question myself. I am wondering how you would explain why mathematical induction is needed.

- Thread starter
- #7

- Jun 26, 2012

- 45

You seem to be quite knowledgeable of the foundations of mathematics. I'm sure you are aware how the set of finite ordinals is constructed. So why is there a contradiction? We can prove the Peano axioms in this set, from set theory. That means that there are natural numbers (let's not focus on what "are" means ). Now, is the problem proving the uniqueness of a Peano model, modulo isomorphism?

Generalising, it would seem that if we first define a set and then take out of that set the subset (with the unary operation and the constant) which satisfies the Peano axioms, why wouldn't this work?

What am I missing?

- Jan 30, 2012

- 2,525

I don't know of any especially good examples. I think examples from standard textbooks on discrete mathematics, such as the formula for $1+\dots+n$, are fine.Are there some really good teaching examples of mathematical induction?

There are some insightful exercises for students who already know how to use basic induction. These are about statements with more than one variable, situations where strengthening the induction statement is necessary, and about unfolding induction to produce a direct proof.

This is not a trick question. Both a direct proof and a proof by induction are used for theorems of the form $\forall n\,P(n)$. In a direct proof, we fix an arbitrary $n$ and have to show $P(n)$ without any additional assumptions. In a proof by induction (more precisely, in the inductive step), we also fix an arbitrary $n$, but now we have to prove $P(n)$ from the assumption $P(n-1)$. Obviously, having an extra assumption makes proving $P(n) easier and is sometimes crucial.To finish, I'd like to ask a question myself. I am wondering how you would explain why mathematical induction is needed.

Concerning the question about the alleged circularity of induction and the foundations of mathematics, I decided to start a new thread.