# 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 course on proofs (or which includes proofs, e.g. a first course on discrete mathematics)?

• There is discussion on this at Mathematics Stack Exchange: math.stackexchange.com/questions/423513/… – Mike Jones Aug 24 '14 at 14:59
• I want to challenge the premise here just a little - not because I don't agree with it, but because it implies that induction isn't "needed" for e.g. the famous sum of the first $n$ positive integers. Okay, it isn't - but how exactly do you show that the "reverse 'em and divide by two" method works for all n? Any time we use "dot dot dot" or "and so on" we need to be careful; even if we're not actually using Well-Ordering implicitly then it is still worth pointing out when "dot dot dot" can lead to trouble. We are careful about this with series, we should be with "non-induction" as well. – kcrisman Mar 8 '16 at 15:31
• Comment: I'm not so sure that the use of "non silly" examples, at least at first, is the best pedagogical practice. I suspect the problem with the classic example is that it bothers you, not the class. Furthermore, non-silly examples are likely to be more complicated (at least in terms of the appearance of the algebra, number of symbols). It is better when learning a new method to do it with something simple, not complicated. Similarly, I think the geometric chess board examples are not a good way to introduces induction to kids first learning induction in algebra 2 class. (cont. see below) – guest Jul 7 '19 at 20:48
• continuation of comment by guest converted from answer: Also, it's maybe even a feature, not a bug, that there is comparison to other proofs. As it gives added psychological comfort in the result. – quid Jul 10 '19 at 12:00
• @Guest, I'm looking for extra examples that my students don't feel are pointless, perhaps that prove some surprising fact. – vonbrand Aug 10 '19 at 23:01

The problem with induction proofs is that too often the problem is given by "Prove that..."

After a few examples and explanations of induction, if the students know elementary calculus, the following sequence might prove interesting:

1. Find the first ten derivatives of $x\cdot e^x$.
2. What seems to be the formula for the $n$th derivative of $x\cdot e^x$?
3. Prove that your formula is right by induction.
4. Find and prove a formula for the $n$th derivative of $x^2\cdot e^x$. When looking for the formula, organize your answers in a way that will help you; you may want to drop the $e^x$ and look at the coefficients of $x^2$ together and do the same for $x$ and the constant term.

I'd have the students work this out in class and in teams of two and their work was corrected and counted as a homework. Of course, the use of a CAS helped getting rid of the messy part of finding derivatives. Not all students found this interesting. But those who did started to learn what it was to do (elementary) research.

Two more examples.

1. Proving that a $2^n \times 2^n$ chessboard with a single square missing can be covered using L-shaped (made out of three squares) pieces.

2. Proving that a convex $n$-gon can be divided into $n-2$ triangles.

• 1. I think this is a great example; so I posted a bit about its history in this same thread. 2. Perhaps you want to say a convex $n$-gon? The statement is true as is, but I'm not sure whether the more general proof qualifies as simple... – Benjamin Dickman Apr 3 '14 at 1:54
• True on 2, thanks! – Santiago Canez May 20 '14 at 23:11
• Proving DeMorgan's Laws for $n$ sets. I like this example because it requires the $n=2$ case in the induction step.
• It's common to have students prove that $\sum_{k=1}^n k^3 = \left(\sum_{k=1}^n k\right)^2$. A great follow up is to assume you have a sequence $\langle a_k\rangle$ that satisfies $\sum_{k=1}^n a_k^3 = \left(\sum_{k=1}^n a_k\right)^2$ and prove, by induction on $n$, that necessarily $a_k=k$ for all $k$.
• Proving the Well-Ordering Principle of $\mathbb{N}$ by induction on whether the set in question has $n$ as an element. I designed a scaffolded version of this as a homework exercise, and it also has the students think about why induction on the size of the set in question does not prove the claim!
• Have not personally used this, but perhaps Cauchy's "backward induction" proof of the AGM inequality is of interest.
• or $a_k=0$ for all $k$... – Matthew Towers Jan 21 '16 at 11:18

Historical remark. Though it has already been mentioned in an answer, I can't resist posting a bit more about the following wonderful example of a proof by induction.

I quote directly from the original printing of Polyominoes (1965) by Solomon Golomb:

T R O M I N O E S

It is impossible to cover an $$8 \times 8$$ board entirely with trominoes, polyominoes of $$3$$ squares, because $$64$$ is not divisible by $$3$$. Instead, it shall be asked: Can the $$8 \times 8$$ board be covered with $$21$$ trominoes and $$1$$ monomino (a single square)? (p. 20).

In this particular problem, Golomb is talking about trominoes that look like extended dominoes. He demonstrates that this is only possible when the monomino is placed in one of four different squares, and then begins his discussion of L-shaped trominoes:

When another type of tromino is considered, the result is surprisingly different: No matter where on the checkerboard a monomino is placed, the remaining squares always can be covered with $$21$$ right trominoes [i.e., L-shaped trominoes] (p. 21).

He then proceeds to prove this for the $$8 \times 8$$ board, but also for the $$2^n \times 2^n$$ board, remarking:

The proof just given proceeds by mathematical induction... (p. 22).

As a spoiler, here is a proof:

The pasted image above comes from a nice article based on earlier work by Norton Starr:

Soifer, A. (2010). Norton Starr’s 3-Dimensional Tromino Tiling. Geometric Etudes in Combinatorial Mathematics, 221-225. Springer New York.

You can find further information about this problem on Starr's site here. In particular, you can find a list of related references as well as a gamefied version of the problem that can be played online (or purchased as an actual puzzle - a nice gift!).

Though the latter tromino problem is solved using induction, the former one is also quite nice. The first to formulate that problem was, apparently, prolific problem poser Murray S. Klamkin:

...back in $$1948$$ ... I had begun to submit a rather large number of problem proposals to the American Mathematical Monthly. ...Since probably at that that time, in retrospect, most of my proposals were not particularly good, they just got filed away. Unfortunately for me, this included one favorite one. This was to determine whether or not one could remove one square from a chess board and cover the deleted board with $$21$$ $$3 \times 1$$ trominoes. This was no loss to problem solvers, since several years later, Solomon Golomb's book on polyominoes came out which included this problem plus many more goodies (p. 73).

This remark comes from (N.B. Good luck tracking down part one of this article...):

Klamkin, M. S. (1994). Mathematical Creativity in Problem Solving and Problem Proposing II. In Eves' circles, (34), 73-95.

Sorry if the tangent here seems unrelated; problem histories can be surprisingly tough to figure out, so I thought it might be nice to include a bit of the back-story online.

• Thank, will see if I can track those down... – vonbrand Apr 3 '14 at 1:51
• @vonbrand If you are talking about tracking down part one of the Klamkin piece (which I would be most interested in seeing...) I believe the citation is: Crux Mathematicorum 11 (1985), 115, 218. – Benjamin Dickman Apr 3 '14 at 1:57

One example that I recently came across was to prove that the function $$f(x)=\begin{cases} e^{-1/x},&x>0\\ 0,&x\leq0 \end{cases}$$ is smooth (i.e. $$f\in\mathcal{C}^\infty$$). Here is a link to a proof online.

I like having students show that the Euler characteristic ($\chi=V-E+F$, where $V$, $E$, and $F$ are the number of vertices, edges, and faces, including the exterior face, of the graph) of a planar graph is always 2. Planar graphs are easy to define for those who have not seen them before, and the proof is a (relatively) straightforward induction on the number of edges in a graph.

Further, after giving the definition of a planar graph, there is ample opportunity for students to explore and come up with a conjecture on their own (assuming you have the time for this). This seems a much more natural way to show how induction is used by mathematicians, rather than just stating "Prove that...".

Another benefit is giving a concrete example of a topological invariant, likely the first seen by your students. Finally, it's not too difficult to motivate why non-math majors should care about graphs. There are dozens and dozens of applications (e.g. neural networks). It is likely that whatever the major of the student, there is some problems in that field for which graphs are useful tools.

• I'm doing this in my evening class tonight! – Santiago Canez May 20 '14 at 23:11
• Best example I've seen so far :) – Ruben May 21 '14 at 0:40
• Graph theory is a great place to explore for statements easy to conjecture and which "need" induction in some sense to prove. – kcrisman Mar 8 '16 at 15:34

I indeed think $$\sum_{k = 1}^n k = \frac{n(n + 1)}2$$ is not a good first example as writing the sum forwards and backwards is more clever and natural for a newcomer.

But proving “the sum of the $$n$$ first odd numbers is $$n^2$$”, while really close to the equality above, is a better example, because the induction part of the proof is really simple: $$\sum_{k = 1}^{n + 1}(2k-1)= \left(\sum_{k = 1}^n(2k-1)\right) + 2n + 1 = n^2 + 2n + 1 = (n + 1)^2$$.

Proof by induction is more necessary and useful in a computer science scenario, where some objects are defined in an inductive way: “a complete binary tree of height $$n$$ has $$2^n - 1$$ nodes”: straightforward for $$n = 1$$; for $$n \geqslant 2$$, its left and right child are binary trees of height $$n - 1$$, so it has $$2(2^{n - 1} - 1) + 1 = 2^n - 1$$ nodes.

Another example where a special method of inductive reasoning called infinite descent is useful: “show that $$\sqrt2$$ is irrational”. Let us assume there exist two natural numbers $$p, q$$ such that $$\sqrt2 = p/q$$. Then $$2q^2 = p^2$$, so $$p$$ is even, thus there exists some natural number $$p'$$ such that $$p = 2p'$$, therefore $$2q^2 = 4p'^2$$ gives $$q^2 = 2p'^2$$ so $$q$$ is even as well, i.e. $$q = 2q'$$ holds for some natural number $$q'$$. We then get $$2q'^2 = p'^2$$, so $$(p', q') = (p / 2, q / 2)$$ is a strictly lesser representation of $$\sqrt2$$. As there is no infinite decreasing sequence of natural numbers, this leads to a contradiction, so $$\sqrt2$$ is irrational.

• Infinite descent can easily be made into a proof by contradiction: Assume $n$ is the smallest natural such that ...; the descent step gives a smaller one; contradiction. – vonbrand Mar 16 '14 at 23:30
• Why is the first example bad but the second one good? "Writing the sum forwards and backwards" for $1, 3, \ldots, 2n-1$ also gives $n$ pairings adding up to $2n$; then the total is $n(2n)/2 = n^2$. – Benjamin Dickman Mar 30 '14 at 4:23
• I like the proof of the sum of the geometric series better than the arithmetic series, precisely because the arithmetic series have alternative, simple proofs. – vonbrand Apr 4 '14 at 14:19
• @ChrisCunningham Your edit reinstated the error I'd fixed. The last term in the sum has to be $(n+1)^2-n^2=2n+1$, not $2n+3$. – J.G. Jul 7 '19 at 17:03
• @J.G. Thanks -- I misread what you had written, and thought you had made the sum start at -1. I think I've made your edit the current version now. – Chris Cunningham Jul 8 '19 at 0:11

Prove that the Tower of Hanoi puzzle can be solved for any number of disks. Indeed, that it can be solved in $2^n - 1$ moves for $n$ disks.

• Nice, as that incorporates recursion in the solution. – vonbrand May 26 '14 at 13:08

Induction receives far too much attention as a proof technique. But, if you are to give it attention, it is probably worth-while going through the equivalence of the principle of induction and the well-ordering of the naturals. In fact, when I teach induction I proceed as follows: Suppose an inductive property does not hold for all naturals. Look at the set of counter-examples, and pick the smallest one. Arrive at a contradiction and conclude the property did hold for all naturals. I find that this approach is very natural (pun not intended). The equivalent formalism of prove case $k=1$, then prove $P(k)\implies P(k+1)$ is something I only introduce later. For the life of me I don't understand why this formalism is the standard one and not the "look at all counter-example....".

It is probably also a good idea to talk about the status of the principle of induction. It is not a theorem but rather a proof principle. It is ok not to accept it (though most mathematicians do). It is important to understand that what we accept by proof by induction is that a single recipe for proofs (i.e., for each $k$ we have a recipe for how to concoct a proof for $P(k)$) is accepted as a single proof for an infinitude of statement (i.e., all the $P(k)$ for all natural $k$). It is a good idea to talk about this in relation to the demand that proofs are finite. It is also a good idea to explain this in the context of the axiom of choice.

It is indeed quite hard to find good examples of proof by induction (which is part of the reason why I claimed that induction receives far too much attention). Other than the classical (more or less silly) exercises, some that actually do require induction include: the generalized associativity rule and other generalized algebraic rules but also proving properties of recursively defined sequences (e.g., monotonicity, boundedness etc.).

• Upvote for "induction receives far too much attention as a proof technique". – Jim Belk Mar 16 '14 at 2:13
• That being said, I think the reason to focus on the $P(k) \Rightarrow P(k+1)$ technique over the "minimal counterexample" technique is that $P(k) \Rightarrow P(k+1)$ is more like a direct proof, while "minimal counterexample" is essentially a proof by contradiction. – Jim Belk Mar 16 '14 at 2:20
• What is wrong with proof by contradiction? – Ittay Weiss Mar 16 '14 at 2:30
• They're a little bit harder to understand and follow, because everything that you prove during a proof by contradiction is false. A direct proof occurs in the "real world" of true statements, while a proof by contradiction occurs in an absurd world that you construct solely for the purpose of pointing out its absurdity. Since we all live in the real world, direct proofs tend to make more sense to the reader. In addition, proofs by contradiction usually convey less insight than direct proofs, since none of the intermediate results that were proved are actually true. – Jim Belk Mar 16 '14 at 2:35
• I must disagree on most accounts @JimBelk. People often engage in proof by contradiction in real life. E.g., "I did not eat that chocolate bar" claims little brother. Well, let's suppose you are telling the truth, then your face would not be smeared with chocolate. Hence you are lying! I do agree that at times a proof by contradiction may seem more obscure than a direct proof, but sometimes the opposite is true. What makes a proof easier to follow is not its mode (contrapositive, direct, by contradiction) but the flow of the arguments. – Ittay Weiss Mar 16 '14 at 2:42

Base problem

Some positive integers are written on the board. At each step one of the integers $n$ is erased and replaced with any number of positive integers that are all less than $n$. Of course, if the erased integer is $1$ then no new positive integers can be written on the board. Prove that no matter how this procedure is carried out the board must eventually become empty.

This problem is just the right difficulty and can ensure that students really understand what induction is.

General problem

Prove that the following game always terminates regardless of the initial configuration and the choices (of node, subtree and number of copies) throughout the game.

(1) Start with any finite tree rooted at $r$

(2) At each step:

(2.1) Select any node $x$ and a child node $y$ of $x$

(2.2) Remove the subtree rooted at $y$ (and of course the edge $(x,y)$ as well)

(2.3) If $x$ is not $r$, attach finitely many copies of the subtree rooted at $x$ to its parent node

For example, the following diagram shows one step, where the chosen subtree to be removed is shown in red and the subtree that would be copied is shown in green.

The base problem is equivalent to the special case of this general problem where the initial tree has depth at most $2$. This generalization is a harder problem that is an extension of the Hydra Game. A hint is to define a total ordering on trees:

For any finite trees $S,T$:

$S \le T$ iff:

Either:

$S$ is a leaf node

Or:

$S,T$ are both not leaf nodes

The subtrees of $S$ when ordered forms a lexicographically smaller sequence than that of $T$

Then one must show that at each step the whole tree decreases according to the ordering, and also that any decreasing sequence of trees must terminate. That last part is the hardest. Basically, induct on the tree depth first, which then allows inducting on the biggest subtree, and then induct on the number of copies of the biggest subtree.

Note that this proof shows that with the right definitions and inductions it is quite intuitive, and there is no need to introduce ordinals.

I suggest the following counter-example. (Added in edit: I agree with kcrisman comment that this may be misleading to beginners, and should probably be kept for people that master induction relatively well and start being lazy verifying the base case).

Theorem. In a (finite) color pencils box, all pencils must have the same color.

Proof. We proceed by induction on the number of pencils. If the box has one pencil, then obviously all its pencils have the same color. Now, assume that in all boxes of $n$ pencils, the pencils are all of the same color and let $X$ be a box with $n+1$ pencils. Order the pencils arbitrarily and consider the $n$ first pencils: by the induction hypothesis, they all have the same color, call it $c$. Consider now the $n$ last pencils: by the induction hypothesis, they all have the same color, call it $c'$. Since the $n-1$ central pencils have color $c$ and $c'$, we have $c=c'$ so that all $n+1$ pencils have the same color.

The goal here is to stress that if one fails to properly identify and test the base case, then things can go dead wrong.

• The problem in this "proof" is really in the step $n = 1$ to $n = 2$. An example of missing/faulty base case(s) would also be nice. – vonbrand Apr 4 '14 at 14:10
• This example is in some sense a problem of base case: given the induction step only works from $n=2$, then $n=2$ should be the base case, not $n=1$. The point is to show that the two steps have to work together. – Benoît Kloeckner Apr 5 '14 at 8:11
• – András Bátkai Apr 22 '14 at 21:51
• I saw a "proof" that $n > n + 10$ that illustrates the "missing base" very nicely. Details are left as an exercise :-) – vonbrand Apr 25 '14 at 0:37
• I usually do this one as "everyone has the same color eyes" - but have found it is not helpful until they really "get" induction; it is confusing when students are first introduced, unless they've had significant previous proof exposure. – kcrisman Mar 8 '16 at 15:22

Here is another one:

$$\color{blue}{\text{Prove that the power of 13 can be writen as a sum of two squares}}.$$

I will give two proofs of it. First one is more involved and includes following fact: $$(a^2+b^2)(x^2+y^2)= (ax+by)^2+(bx-ay)^2$$ yet second one takes step 2 and it is much more elegant.

1.st proof

Base: $$n=1$$, then $$13 = 2^2+3^2$$ and we are done.

We know that $$13^n = a^2+b^2$$ for some integers $$a,b$$. Then: $$\begin{eqnarray}13^{n+1} &=& 13\cdot 13^n\\ &=& (2^2+3^2)(a^2+b^2)\\ &=& (\underbrace{2a+3b}_x)^2+(\underbrace{3a-2b}_y)^2\\ &=& x^2+y^2 \end{eqnarray}$$

2.nd proof

Base cases $$n=1$$: $$13^1 = 2^2+3^2$$ and $$n=2$$: $$13^2 = 169 =25+144=5^2+12^2$$

Now we go from $$n\to n+2$$: $$\begin{eqnarray}13^{n+2} &=& 13^2\cdot 13^n\\ &=& 13^2(a^2+b^2)\\ &=& (\underbrace{13a}_x)^2+(\underbrace{13b}_y)^2\\ &=& x^2+y^2 \end{eqnarray}$$

Disclaimer:

It's not simple, but it might be useful. The context in which it happend is algorithms, but it would be great if someone could test if this approach is useful during other courses, e.g. when introducing induction. Reason why I'm writing about this here is, that when I did the exercise described below, my students (not all, but a lot) had this "being enlightened" face expression, and as it was not about the algorithm itself, then it had to be about the other thing and in that case it was induction (i.e. it seemed that they grasped something important about induction).

Exercise:

The task was on dynamic programming and was given as follows:

A company plans to organize a party. The hierarchy of employees is a rooted tree (not necessarily binary), and each employee can be characterized by a form of sociability, given by a positive number. Write a program that will pick the guests so that:

• no guest would meet their immediate superior at the party,
• the sum of sociability coefficients is maximal,
• the company founder (the root of the tree) has to be at the party.

The program should output a single number, namely the sum of sociability coefficients of the guests.

The algorithm to calculate it is easy, let the symbol $\mathcal{T}$ denote the set of abstract people with their hierarchies


where the result will be given by $\with$ as the founder has to be included. Now, the challenge is to prove that it is optimal (i.e. it returns the correct result). The proof is via induction on the structure of the tree, that is, we start from leaves and then go up to the root, with the assumption that each time when make the step in some node, all its subtrees are already done.

The base step is easy, as for each leaf we have $\sub(l) = \varnothing$ so \begin{align}\with(l) &= \soc(l) \\ \without(l) &= 0 \end{align} what is obviously true.

Now, for the induction step, $\with(t)$ requires all the subtrees to skip their roots, and besides that they are all independent, so we can just take the sociability of $t$ and add all the optimal subsolutions (we can use them because of the induction hypothesis) and that is exactly what the formula is doing. As for $\without(t)$ the $t$ itself isn't a guest, so from each subtree we can pick the best option and sum it all together. This works, but only because we know that the subsolutions were calculated correctly from induction hypothesis, the shape of the tree ensures, that there weren't any circular arguments.

Sometimes students benefit from an alternative proof: take an optimal solution and prove that one returned by the algorithm isn't worse. Again, prove it via induction on the structure of the tree, the hypothesis being that our algorithm returns an optimal subsolution for each node of the tree. Base case is easy, because there is no choice available in the leaves. For the inner nodes we show that our algorithm returns a pick of guests at least as good as the optimal solution (in $\with$ it follows from induction hypothesis and the fact that all the numbers are positive, for $\without$ it follows from properties of $\max$ function).

Some commentary:

Each time I did this it was an introductory course in programming, and for many the first time where they would see a non-linear induction (in fact this can be proved with induction on the height of the tree, but I did complicate it on purpose). Drawing a diagram with arrows, describing how the induction progresses and how it relies on the subtrees being already calculated helps a lot. After this exercise the topic would come back again several times and students would have much easier time proving that some algorithm (e.g. the Ackermann function) terminates.

Of course, it is hard to draw any reliable conclusions from this experience (it might be just a coincidence that it worked for me), so it would be great if someone could test it themselves. I'd also love to hear your opinions and suggestions.

I hope this helps $\ddot\smile$

Three connected induction proofs:

(1) For a really easy one: Every tree of $n$ arcs has $n+1$ nodes. ($0$ arcs $\implies$ $1$ node. Remove a leaf node and its incident arc; induct.)

(2) A bit more difficult: Every polygon triangulation can be $3$-colored. Assume every polygon has a triangulation. See below. Argue that the dual graph is a tree. Remove a leaf node by clipping off an "ear tip." $3$-color the remainder and return the ear triangle, coloring its tip different from its two neighbors.

(3) Every polygon has a triangulation. Prove there exists an interior diagonal. Induct on the two halves. Proved, e.g., in Discrete and Computational Geometry, p.4.

• (2) is wrong as it stands. Suppose that the polygon is a triangle, and its triangulation is $K_4$. Perhaps the theorem is intended to apply to a graph only if it is planar and it is a cycle and some chords of that cycle? That is, a polygon triangulation without extra vertices? – Rosie F Jul 23 '16 at 18:37
• @RosieF: In this case a triangulation is a maximal set of noncrossing interior diagonals connecting pairs of vertices. – Joseph O'Rourke Jul 24 '16 at 12:10

Computational geometry is a good source for basic induction proofs where non-inductive methods are either impossible or hard to conceive.

Also graph theory. Someone already mentioned Euler's Formula which is great. It's also simple to prove that every connected simple graph can be 6-colored using induction. (You can assume in such a graph that there exists a vertex whose degree is less than or equal to 5 -- or prove it separately.)

For a CS-oriented audience, proofs of correctness for recursive algorithms are a great way to motivate induction -- especially because induction and recursion go hand in hand. Here's a nice video proof from Udacity on the correctness of the Russian peasant's algorithm for integer multiplication: https://www.youtube.com/watch?v=GGBEiIuheTY

A simple consequnce of:

Postage Stamp Problem, which states that for any two relatively prime positive integers $$m,n$$, the greatest integer that cannot be written in the form $$am + bn$$ for nonnegative integers $$a, b$$ is $$mn-m-n$$,

is that every natural number greater or equal to $$mn-m-n+1$$ can be writen in a form $$am+bn$$ for some $$a,b$$.

And for some concrete $$m,n$$ it is a nice problem to solve in HS: Say $$m=3$$ and $$n=5$$, then prove that every natural number greater than $$8$$ can be writen in a form $$3a+5b$$.

Proof: Base cases: $$\begin{eqnarray}8 &=& 3\cdot 1+5\cdot 1\\ 9 &=& 3\cdot 3+5\cdot 0\\ 10 &=& 3\cdot 0+5\cdot 2 \end{eqnarray}$$ and now go from $$n\to n+3$$: If $$n=3a+5b$$ then

$$\begin{eqnarray}n+3 &=& 3\underbrace{(a+1)}_{a'}+5b\\ &=& 3\cdot a'+5\cdot b \end{eqnarray}$$

• For reference for others seeing this, this question is also known as the the coin problem, Frobenius problem, McNugget problem, etc. - see e.g. MathWorld or Wikipedia. – kcrisman Jan 2 '20 at 16:59
• (It's also a good example because of the base cases, because in your example you could do the same thing with $n\to n+5$ if one did the induction "the other way", and because it is very amenable to exploration before the answer is discovered.) – kcrisman Jan 2 '20 at 17:01

For what natural $$n$$ does there exist a square composed of $$n$$ squares?

Example: 1, 4, and 6 are valid, but one cannot construct a square from 2, 3, or 5 squares.

Proof:

Construct squares composed of 1, 6, and 8 squares. Then show by induction that if you can construct a square composed of $$n$$ squares, then you can construct a square composed of $$n+3$$ squares simply by cutting one of the squares into 4 more.

# Putnam 1963

Let $$\mathbb N$$ be the set of positive integers, and let $$f:\mathbb N\to\mathbb N$$ be a strictly increasing function such that $$f(2)=2$$ and $$f(m)f(n)=f(mn)$$ for all positive integers $$m,n$$ such that $$\gcd(m,n)=1$$. Find all such functions $$f$$.

# Watered down version:

Let $$\mathbb N$$ be the set of positive integers, and let $$f:\mathbb N\to\mathbb N$$ be a strictly increasing function such that $$f(3)=3$$ and $$f(m)f(n)=f(mn)$$ for all positive integers $$m,n$$ such that $$\gcd(m,n)=1$$. Show that $$f(n)=n$$ for all $$n$$.

# Proof:

Note that if $$f(m)=m$$ then $$f(n)=n$$ for all $$n since $$f$$ is strictly increasing. Thus $$f(2)=2$$. We now prove by induction that $$f(2^i+1)=2^i+1$$. It holds for $$i=1$$. Suppose it holds for $$i=j$$ for some $$j$$. Then $$f(2^{j+1}+2)=f(2)f(2^j+1)=2^{j+1}+2$$. Thus $$f(2^{j+1}+1)=2^{j+1}+1$$. Hence it holds for $$i=j+1$$. Hence it holds for all $$n$$. Q.E.D.

Alteration for the Putnam problem:

One simply needs to show $$f(3)=3$$, then the rest follows as above. Observe that $$f(3)f(5)=f(15)

The alterations to the problem are to avoid the convoluted extra base case (focus on the main induction) and to provide the solution $$f$$ to make the end goal more clear. It is interesting to note that one has to be more creative than usual, as a backwards induction argument is used. However the solution is still not too complicated to figure out.

Prove that the greedy algorithm for the change-making problem with Fibonacci denominations produces an optimal solution (uses the minimum number of coins possible).

This problem is not as easy as it looks. Note that there may be more than one optimal solution. It would also be instructive to try and minimize the number of times the induction axiom is used. (But no, I won't suggest that one should also try to prove this minimum. =P)

Although building up to it might be beyond the time available in many courses introducing induction, an interesting elementary example that seems unbelievable but is very easy to verify in any given case is Pick's Theorem.

Hmm, I'm surprised than no one mentioned de Moivre's formula: $$(\cos \phi +i\cdot \sin \phi)^n= \cos (n\phi) + i\cdot\sin (n\phi)$$

It is an excellent exercise to prove it. We must also use the addition theorems for sin and cos.

I often teach a short unit on induction in elementary calculus classes—it comes up very naturally when trying to prove a version of the power rule:

Lemma 1: (Product Rule) Let $$f$$ and $$g$$ be real valued functions on $$\mathbb{R}$$. At any point $$x$$ where both $$f$$ and $$g$$ are differentiable, $$(fg)'(x) = f'(x) g(x) + f(x) g'(x).$$

As it is not really germane to this discussion, I'll assume that the product rule has already been proved.

Theorem 2: (Power Rule, version 1) For any natural number $$n$$, $$\frac{\mathrm{d}}{\mathrm{d}x} x^n = nx^{n-1}.$$

Proof of Theorem 2 (by induction): As a basis for induction, note that $$\frac{\mathrm{d}}{\mathrm{d}x} x^1 = \lim_{h\to 0} \frac{(x+h)^1 - x^1}{h} = \lim_{h\to 0} \frac{h}{h} = 1 = x^0.$$ Suppose that there is some natural number $$k$$ such that $$\frac{\mathrm{d}}{\mathrm{d}x} x^k = k x^{k-1}.$$ Then \begin{align} \frac{\mathrm{d}}{\mathrm{d}x} x^{k+1} &= \frac{\mathrm{d}}{\mathrm{d}x} \left[ x \cdot x^k \right] \\ &= \left[ \frac{\mathrm{d}}{\mathrm{d}x} x \right] x^k + x \left[ \frac{\mathrm{d}}{\mathrm{d}x} x^k \right] && \text{(Product Rule)} \\ &= 1 \cdot x^k + k x \cdot x^{k-1} && \text{(Induction Hypothesis)} \\ &= (k+1) x^k, \end{align} which is the desired result. $$\square$$

It is worth noting, perhaps, that most elementary calculus texts prove this version of the power rule by appealing to the binomial theorem:

Theorem 3: (Binomial Theorem) Let $$a$$ and $$b$$ be positive real numbers and $$n$$ a natural number. Then $$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}.$$

Proof of Theorem 2 (using the binomial theorem): Let $$n$$ be a natural number. Then \begin{align} \frac{\mathrm{d}}{\mathrm{d}x} x^n &= \lim_{h\to 0} \frac{(x-h)^n - x^n}{h} \\ &= \lim_{h\to 0} \frac{ \left[ \sum_{k=0}^{n} \binom{n}{k} x^k h^{n-k} \right] - x^n}{ h} && \text{(Binomial Theorem)} \\ &= \lim_{h\to 0} \sum_{k=0}^{n-1} \binom{n}{k} x^k h^{n-k-1} \\ &= \binom{n}{n-1} x^{n-1} && \text{(all other terms have a factor of h)} \\ &= n x^{n-1}, \end{align} which is the claimed result. $$\square$$

1. Many elementary calculus students struggle with even basic arithmetic operations. Throwing binomial coefficients, factorials, and sigma notation at them is at this point in the class is a little unfair, unless one is willing to move the sequences and series material to the beginning of the class (this material is usually taught near the end of the second semester of calculus at American institutions). The sigma notation can be avoided, but it gets replaced with ellipses, which, in my opinion, is less rigorous and a bit hand-wavy.

2. The binomial theorem, itself, requires proof, and the classical proof is by induction:

Proof of Theorem 3: As a basis for induction, note that $$(a+b)^1 = a+b = \binom{1}{0} a^0 b^1 + \binom{1}{1} a^1 b^0 = \sum_{k=0}^{1} \binom{1}{k} a^k b^{n-k}.$$ Suppose that there is some natural number $$k$$ such that $$(a+b)^k = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}.$$ Then \begin{align} (a+b)^{k+1} &= (a+b) (a+b)^k \\ &= (a+b) \sum_{k=0}^{n} \binom{n}{k} a^k b^{k-n} \\ &= \big[\kern-2pt\big[ \text{several tedious steps involving combinatorial identities} \big]\kern-2pt\big] \\ &= \sum_{k=0}^{n+1} \binom{n+1}{k} a^k b^{n+1-k}, \end{align} as desired. $$\square$$

Note that I've skipped much of the computational detail here—a lot of those details are, themselves, rather off-topic for a calculus class. In order to use the binomial to prove the product rule, I also have to discuss with students the intermediate results that I've skipped here.

I am not going to argue that proving the product rule in calculus requires induction (I can't think of an alternative proof off the top of my head, but that doesn't mean anything). On the other hand, I think that induction is the best way to obtain the product rule (even if you choose to invoke the binomial theorem, there is an induction hiding behind the scenes), and it provides a good excuse to introduce induction.

In an American "Introduction to Proofs" or elementary "Discrete Mathematics" course, either of which is usually offered after students have taken calculus, I think that the first proof offers a nice call-back to calculus. Students should already know the product rule, and may even have seen some kind of proof (probably a mysterious proof involving the binomial theorem, which they probably won't have seen a proof of). Thus providing this as a first or second example gives some context for induction, and helps to connect earlier mathematical knowledge to new material.

Prove that, for all $$x$$ in $$\mathbb{N}$$, we have $$x+1 \neq x$$. (Requires use of proof by contradiction.)

Use only the following properties of addition on $$\mathbb{N}$$:

1. Addition is closed on $$\mathbb{N}$$.

2. $$x+1 \neq 1$$ for all $$x$$ in $$\mathbb{N}$$.

3. If $$x+1 = y+1$$, then $$x=y$$ for all $$x$$, $$y$$ in $$\mathbb{N}$$.

4. The Principle of Mathematical Induction.

OUTLINE

Base case

$$1+1 \neq 1$$ follows directly from (2).

Inductive step

Suppose $$x$$ in $$\mathbb{N}$$ and $$x \neq x+1$$.

Suppose to the contrary that $$x+1 = x+1+1$$.

Obtain the contradiction $$x=x+1$$ by applying (3).

Conclude (by contradiction) that $$x+1 \neq x+1+1$$

Conclude that for all $$x$$, if $$x$$ in $$\mathbb{N}$$ and $$x \neq x+1$$ then $$x+1 \neq x+1+1$$.

I wrote an article that explains mathematical induction in the easiest way possible using an easy-to-understand example. It was published in Medium's #1 Math Publication, so I guess it must be pretty good. Feel free to take a look.

The used example is: $$1 + 2 + \cdots (n-1) + n = \frac{n(n+1)}{2}$$
• This is an article-length proof that $1 + 2 + ... + (n-1) + n = \frac{n(n+1)}{2}$. You might put this at the top of your answer so folks know what induction problem you're suggesting (and since link rot is a thing). – Nick C Sep 12 '20 at 14:52