Return to Answer

Lots of good answers here (I've upvoted many). I'm won't try to add to the didcussion about why induction is hard, but I can suggest some approaches that have helped some of my students.

Well ordering helps students understand the traditional formulation of induction: consider proposition $P(n)$ about positive integral $n$. If $P(1)$ is true and the truth of $P(n)$ implies that of $P(n+1)$ for all $n$ then $P(n)$ is true for all $n$. Just look for a minimal counterexample.

Lots of good answers here (I've upvoted many). I'm won't try to add to the discussion about why induction is hard, but I can suggest some approaches that have helped some of my students.

Well ordering helps students understand the traditional formulation of induction and implies it: consider proposition $P(n)$ about positive integral $n$. If $P(1)$ is true and the truth of $P(n)$ implies that of $P(n+1)$ for all $n$ then $P(n)$ is true for all $n$. Just look for a minimal counterexample. To prove that the traditional formulation implies well ordering, consider a set $S$ with no least element and let $P(n)$ be the proposition "$S$ has no elements less than or equal to $n$". Then $P(1)$ is true, since if $1$ were in $S$ it would be the least element. If $P(n)$ is true then $P(n+1)$ is too, lest $n+1$ be the least element of $S$. The truth of all the statements $P(n)$ clearly implies $S$ is empty.

Lots of good answers here (I've upvoted many). I'm won't try to add to the didcussion about why induction is hard, but I can suggest some approaches that have helped some of my students.

Many have seen induction as an algebra exercise - for example, summing the first $n$ squares. Those examples are tedious and work badly. Students have trouble with the hypothetical "Suppose it's true for $n$ ..." and you find yourself trying to answer their "How do you know it's true for $n$?"

I like to start with well ordering, without even calling it induction. Students have little trouble accepting the the fact that a nonempty set of positive integers must have a least element. Then you can prove lots of things by showing that a minimal counterexample leads to a contradiction. (I think that's worth doing in spite of my preference for direct rather than indirect proofs.)

For example you can start the fundamental theorem of arithmetic (FTA)- every integer is a product of primes in at least one way - by looking at the smallest integer for which it fails. (One pedagogical problem here is that they don't think the FTA needs to be proved. Examples of rings in which it fails usually take more class time than one can afford.)

The uniqueness in the FTA follows from the same kind of argument if you grant the lemma that a prime dividing a product must divide one of the factors.

That lemma follows from the extended form of the Euclidean algorithm, asserting that the $\text{gcd}(m,n)$ is an integral combination of $m$ and $n$. You can prove that by induction - a minimal counterexample leads to a contradiction with one application of division with remainder.

The actual computation of the coefficients for the linear combination giving the gcd is a classic recursive program - well worth doing in a course with both math and cs students. Just reading the code in an easy language like python is instructive - no need for them to write it. As has been noted in other answers. learning recursion and learning induction reinforce each other.

With well ordering in hand you can tell the classic joke: every positive number is interesting. If not, then the least boring integer is an interesting number. Be sure to distinguish between least (boring integer) and (least boring) integer.

Well ordering helps students understand the traditional formulation of induction: consider proposition $P(n)$ about positive integral $n$. If $P(1)$ is true and the truth of $P(n)$ implies that of $P(n+1)$ for all $n$ then $P(n)$ is true for all $n$. Just look for a minimal counterexample.

If you have time, teach Fermat's method of descent by going through Euler's proof that $x^4 + y^4 = z^2$ has only trivial solutions.

Well ordering also helps focus on the "inductive step" rather than the base case (as another answer recommends). That inductive step is central in lots of combinatorial arguments. You can show that the cardinality of an $n+1$ element set is twice that of an $n$ element set without knowing a formula for the latter. The recursion for counting combinations works the same way. Then you have a nice inductive proof of the formula by showing it satisfies the same recursion.

The pattern I'm recommending might be called "induction in disguise." The formal structure is there, but appears as simple common sense rather than formidable logic with quantifiers and hypotheses and algebra.

Hope this helps.

Lots of good answers here (I've upvoted many). I'm won't try to add to the didcussion about why induction is hard, but I can suggest some approaches that have helped some of my students.

Many have seen induction as an algebra exercise - for example, summing the first $n$ squares. Those examples are tedious and work badly. Students have trouble with the hypothetical "Suppose it's true for $n$ ..." and you find yourself trying to answer their "How do you know it's true for $n$?"

I like to start with well ordering, without even calling it induction. Students have little trouble accepting the fact that a nonempty set of positive integers must have a least element. Then you can prove lots of things by showing that a minimal counterexample leads to a contradiction. (I think that's worth doing in spite of my preference for direct rather than indirect proofs.)

For example you can start the fundamental theorem of arithmetic (FTA)- every integer is a product of primes in at least one way - by looking at the smallest integer for which it fails. (One pedagogical problem here is that they don't think the FTA needs to be proved. Examples of rings in which it fails usually take more class time than one can afford.)

The uniqueness in the FTA follows from the same kind of argument if you grant the lemma that a prime dividing a product must divide one of the factors.

That lemma follows from the extended form of the Euclidean algorithm, asserting that the $\text{gcd}(m,n)$ is an integral combination of $m$ and $n$. You can prove that by induction - a minimal counterexample leads to a contradiction with one application of division with remainder.

The actual computation of the coefficients for the linear combination giving the gcd is a classic recursive program - well worth doing in a course with both math and cs students. Just reading the code in an easy language like python is instructive - no need for them to write it. As has been noted in other answers. learning recursion and learning induction reinforce each other.

With well ordering in hand you can tell the classic joke: every positive number is interesting. If not, then the least boring integer is an interesting number. Be sure to distinguish between least (boring integer) and (least boring) integer.

Well ordering helps students understand the traditional formulation of induction: consider proposition $P(n)$ about positive integral $n$. If $P(1)$ is true and the truth of $P(n)$ implies that of $P(n+1)$ for all $n$ then $P(n)$ is true for all $n$. Just look for a minimal counterexample.

If you have time, teach Fermat's method of descent by going through Euler's proof that $x^4 + y^4 = z^2$ has only trivial solutions.

Well ordering also helps focus on the "inductive step" rather than the base case (as another answer recommends). That inductive step is central in lots of combinatorial arguments. You can show that the cardinality of an $n+1$ element set is twice that of an $n$ element set without knowing a formula for the latter. The recursion for counting combinations works the same way. Then you have a nice inductive proof of the formula by showing it satisfies the same recursion.

The pattern I'm recommending might be called "induction in disguise." The formal structure is there, but appears as simple common sense rather than formidable logic with quantifiers and hypotheses and algebra.

Hope this helps.

Lots of good answers here (I've upvoted many). I'm won't try to add to the didcussion about why induction is hard, but I can suggest some approaches that have helped some of my students.

Many have seen induction as an algebra exercise - for example, summing the first $n$ squares. Those examples are tedious and work badly. Students have trouble with the hypothetical "Suppose it's true for $n$ ..." and you find yourself trying to answer their "How do you know it's true for $n$?"

I like to start with well ordering, without even calling it induction. Students have little trouble accepting the the fact that a nonempty set of positive integers must have a least element. Then you can prove lots of things by showing that a minimal counterexample leads to a contradiction. (I think that's worth doing in spite of my preference for direct rather than indirect proofs.)

For example you can start the fundamental theorem of arithmetic (FTA)- every integer is a product of primes in at least one way - by looking at the smallest integer for which it fails. (One pedagogical problem here is that they don't think the FTA needs to be proved. Examples of rings in which it fails usually take more class time than one can afford.)

The uniqueness in the FTA follows from the same kind of argument if you grant the lemma that a prime dividing a product must divide one of the factors.

That lemma follows from the extended form of the Euclidean algorithm, asserting that the $\text{gcd}(m,n)$ is an integral combination of $m$ and $n$. You can prove that by induction - a minimal counterexample leads to a contradiction with one application of division with remainder.

The actual computation of the coefficients for the linear combination giving the gcd is a classic recursive program - well worth doing in a course with both math and cs students. Just reading the code in an easy language like python is instructive - no need for them to write it. As has been noted in other answers. learning recursion and learning induction reinforce each other.

With well ordering in hand you can tell the classic joke: every positive number is interesting. If not, then the least boring integer is an interesting number. Be sure to distinguish between least (boring integer) and (least boring) integer.

Well ordering helps students understand the traditional formulation of induction: if for a proposition $P(n)$ about positive integral $n$, if $P(1)$ is true and the truth of $P(n)$ implies that of $P(n+1)$ for all $n$ then $P(n)$ is true for all $n$. Just look for a minimal counterexample.

Well ordering also helps focus on the "inductive step" rather than the base case (as another answer recommends). That inductive step is central in lots of combinatorial arguments. You can show that the cardinality of an $n+1$ element set is twice that of an $n$ element set without knowing a formula for the latter. The recursion for counting combinations works the same way. Then you have a nice inductive proof of the formula by showing it satisfies the same recursion.

The pattern I'm recommending might be called "induction in disguise." The formal structure is there, but appears as simple common sense rather than formidable logic with quantifiers and hypotheses and algebra.

Hope this helps.

Lots of good answers here (I've upvoted many). I'm won't try to add to the didcussion about why induction is hard, but I can suggest some approaches that have helped some of my students.

Many have seen induction as an algebra exercise - for example, summing the first $n$ squares. Those examples are tedious and work badly. Students have trouble with the hypothetical "Suppose it's true for $n$ ..." and you find yourself trying to answer their "How do you know it's true for $n$?"

I like to start with well ordering, without even calling it induction. Students have little trouble accepting the the fact that a nonempty set of positive integers must have a least element. Then you can prove lots of things by showing that a minimal counterexample leads to a contradiction. (I think that's worth doing in spite of my preference for direct rather than indirect proofs.)

For example you can start the fundamental theorem of arithmetic (FTA)- every integer is a product of primes in at least one way - by looking at the smallest integer for which it fails. (One pedagogical problem here is that they don't think the FTA needs to be proved. Examples of rings in which it fails usually take more class time than one can afford.)

The uniqueness in the FTA follows from the same kind of argument if you grant the lemma that a prime dividing a product must divide one of the factors.

That lemma follows from the extended form of the Euclidean algorithm, asserting that the $\text{gcd}(m,n)$ is an integral combination of $m$ and $n$. You can prove that by induction - a minimal counterexample leads to a contradiction with one application of division with remainder.

The actual computation of the coefficients for the linear combination giving the gcd is a classic recursive program - well worth doing in a course with both math and cs students. Just reading the code in an easy language like python is instructive - no need for them to write it. As has been noted in other answers. learning recursion and learning induction reinforce each other.

With well ordering in hand you can tell the classic joke: every positive number is interesting. If not, then the least boring integer is an interesting number. Be sure to distinguish between least (boring integer) and (least boring) integer.

Well ordering helps students understand the traditional formulation of induction: consider proposition $P(n)$ about positive integral $n$. If $P(1)$ is true and the truth of $P(n)$ implies that of $P(n+1)$ for all $n$ then $P(n)$ is true for all $n$. Just look for a minimal counterexample.

If you have time, teach Fermat's method of descent by going through Euler's proof that $x^4 + y^4 = z^2$ has only trivial solutions.

Well ordering also helps focus on the "inductive step" rather than the base case (as another answer recommends). That inductive step is central in lots of combinatorial arguments. You can show that the cardinality of an $n+1$ element set is twice that of an $n$ element set without knowing a formula for the latter. The recursion for counting combinations works the same way. Then you have a nice inductive proof of the formula by showing it satisfies the same recursion.

The pattern I'm recommending might be called "induction in disguise." The formal structure is there, but appears as simple common sense rather than formidable logic with quantifiers and hypotheses and algebra.

Hope this helps.