Skip to main content

Questions tagged [induction]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
12 votes
11 answers
4k views

Does a proof by induction have to explicitly refer to the principle of mathematical induction?

I teach high school math. Some of my colleagues insist that a proof by induction should explicitly refer to the principle of mathematical induction, i.e. it must include the words "by the ...
Dan's user avatar
  • 1,245
12 votes
7 answers
3k views

Does induction really avoid proving an infinite number of claims?

I am teaching calculus $1$ this semester, and I saw the following motivation for using induction by another teacher: Since we can't go over "manually proving" all claims $1,2,\ldots$ and ...
Asaf Shachar's user avatar
8 votes
2 answers
516 views

Is there any example of a "forwards/backwards" induction?

I like to make the "dominoes" analogy when I teach my students induction. I recently came across the following video: https://www.youtube.com/watch?v=-BTWiZ7CYoI In this video, a sequence of ...
Steven Gubkin's user avatar
10 votes
6 answers
1k views

'Low-algebra' examples of induction

What are good examples of proofs by induction that are relatively low on algebra? Examples might include simple results about graphs. My aim is to help students get a sense of the logical form of an ...
dbmag9's user avatar
  • 660
7 votes
3 answers
501 views

Is induction or recursion easier to understand?

This is not really a new question, more a revisiting of @vonbrand's "Any suggestions on how to approach recursion and induction?" In an introductory programming class this past year, I asked the ...
Joseph O'Rourke's user avatar
7 votes
0 answers
394 views

Examples of multiple induction

It is easy to find/construct cases that can be proven by nested induction, i.e., some variation of the theme to prove the statement $P(m, n)$ you prove $P(1, n)$ by induction as a base case for $m$, ...
vonbrand's user avatar
  • 12.3k
14 votes
4 answers
952 views

Proofs that make theorems less clear

Teaching Theory of Computation for the first time, I encountered a phenomenon which perhaps is familiar to others in different contexts. I realize most MESE participants are not conversant with Th....
Joseph O'Rourke's user avatar
18 votes
4 answers
2k views

Why do students only see the last term of a sum abbreviated with an ellipsis?

It's very common in learning mathematical induction to prove statements like $$ 0^2+1^2+2^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}.$$ I've found that very frequently, on this sort of problem, when ...
Mike Shulman's user avatar
  • 6,580
16 votes
3 answers
612 views

Teaching strong induction instead of induction

After teaching induction and then strong induction (i.e. the version where you assume $\forall k<n, P(k)$ and prove $P(n)$), one of my students asked why we ever use ordinary induction, since ...
Mike Shulman's user avatar
  • 6,580
87 votes
21 answers
26k views

Why are induction proofs so challenging for students?

This forum already has many good, simple examples of induction proofs, a great resource. As I am soon to teach induction for the $n^\textrm{th}$ time—this time to some perhaps under-prepared ...
Joseph O'Rourke's user avatar
44 votes
28 answers
12k views

Good, simple examples of induction?

Many examples of induction are silly, in that there are more natural methods available. Could you please post examples of induction, where it is required, and which are simple enough as examples in a ...
vonbrand's user avatar
  • 12.3k