Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [induction]

The tag has no usage guidance.

6
votes
0answers
91 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 ...
8
votes
5answers
817 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 ...
6
votes
3answers
223 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 ...
7
votes
0answers
135 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$, ...
13
votes
3answers
530 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....
16
votes
4answers
1k 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 ...
15
votes
2answers
292 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 ...
61
votes
20answers
14k 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 ...
30
votes
17answers
5k 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 ...