Exploring Mathematical Induction: Impactful Examples and Real Life Applications

[matqkks]

Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of introducing mathematical induction? I need something which will have an impact. Are there any real life applications of induction?

 

[bw0young0math]

Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of introducing mathematical induction? I need something which will have an impact. Are there any real life applications of induction?

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.

^^*

 

[ModusPonens]

When I explained induction to a friend who wasn't geting it I said: imagine that you have proved the property P(0) and that you have proven that $P(n)\Rightarrow P(n+1)$. What does this mean? In particular it means that you have proven:

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 really 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.

 

[alyafey22]

Mathematical induction is just a way to prove some facts . The easiness of a proof by induction makes us somehow suspicious about how true it is . It uses rules of implications which are well-established and natural . Proof by induction is very useful in many areas of mathematics especially Abstract algebra , Number theory and Set theory .Actually there are many problems which seem no where near to be solved by induction but indeed they are .

 

[mathworker]

Simplicity of induction makes it look unorthodox in sum cases but it is like proving you are boy and saying next to every boy there is a boy and method is amazing to check something we know

 

[Evgeny.Makarov]

Some students are not convinced that a proof by mathematical induction is a proof.

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.

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

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.

 

[matqkks]

Are there some really good teaching examples of mathematical induction?

 

[ModusPonens]

Hello Evgeny

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 :D ). 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?

 

[Evgeny.Makarov]

Are there some really good teaching examples of mathematical induction?

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.

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.

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

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.

matqkks, if you find out what exactly your students had trouble understanding and what helped them, we would appreciate if you share it.

Concerning the question about the alleged circularity of induction and the foundations of mathematics, I decided to start a https://driven2services.com/staging/mh/index.php?threads/5272/.