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

The tag has no usage guidance.

8
votes
5answers
792 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
210 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
123 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
521 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
287 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 ...
60
votes
19answers
13k 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 ...