Can someone give me an example of a challenging proof by induction? [closed]

I'm about to give my first consultation and the topic is proof by induction. The students are new to calculus and I assume they don't know anything besides precalculus. Can anyone give me a proof by induction which is a bit different, challenging, maybe foreshadows other areas of calculus (derivation or whatever) because the prof who teaches them as well already have shown them a lot of easy ones. I'm glad even if you can give an example where it is hard to see that it can be proved by induction.

closed as too broad by user223391, Watson, Qwerty, Parcly Taxel, RamiroSep 24 '16 at 1:28

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

Here is one that my math professor showed us: show that for $n\ge 1$ a $2^n\times 2^n$ chessboard with one square removed can always be tiled by "L-shaped" pieces. That is, pieces formed by removing a corner from a $2\times2$ square.

• For $n \geq 0$, in fact. – Peter LeFanu Lumsdaine Sep 15 '16 at 8:39
• @Octopus: right… but carefully write down the definition of what it means to “tile a region with L-shaped pieces”, and unless you explicitly add some kind of non-emptiness condition, I guarantee you will find that it naturally includes the empty case. It’s true, lots of people do like to exclude the empty-case — but 99% of the time it’s because we have psychological hangups about it, it’s not something that emerges mathematically naturally! :-) – Peter LeFanu Lumsdaine Sep 15 '16 at 21:12
• MESE note about this problem and (some of) its history. – Benjamin Dickman Sep 16 '16 at 1:17
• @BenjaminDickman thanks for the post about the problem's history. It's fascinating indeed! – Alex Ortiz Sep 16 '16 at 1:25

I suggest Cauchy's proof (I believe it's Cauchy's) of the A.G.M. inequality, because it is non-standard and unsettling induction. It goes along the following lines:

1. Prove that if the inequality is true for $n$ numbers, it is true for $2n$ numbers.
2. Prove that if it is true for $n$ numbers, it is true for $n\boldsymbol{\color{red}-} 1$ numbers.

Point 1, together with the initialisation step implies the inequality is true for numbers of the form $2^k$. As any number belongs to some interval $\bigl(2^{k-1}..\,2^{k} \bigr]\mkern-4.5mu\bigr]$, point 2 ensures it is true for all numbers.

• To teach Cauchy's proof correctly, one ought to also prove that the induction technique is valid, based on normal induction alone. Namely, if for any $k \in \mathbb{N}$ we have both that $P(2^k)$ and that $P(k+1) \to P(k)$, then $P(k)$ for any $k \in \mathbb{N}$. That is an interesting induction exercise all on its own! Incidentally, a long time ago I had a classmate who insisted that Cauchy's proof was wrong... – user21820 Sep 15 '16 at 3:51
• @user21820: ??? I don't see why it should be wrong, except perhaps for axiomatic set theory reasons – a domain which I don't know well enough. Or the actual details were wrong? If I remember well, it's an exercise of Spivak's Calculus. – Bernard Sep 15 '16 at 7:44
• Of course it's not wrong (my classmate had a poor grasp of logic), but it is actually not that trivial to prove that such an induction technique is actually (meta-logically) provable from the standard induction axiom, to show that it is valid. And Spivak didn't justify the validity of the induction either, and left it to the reader's intuition, if I recall correctly. Anyway, ZF proves the standard induction axiom, and hence also proves this valid. – user21820 Sep 15 '16 at 8:19

I like this one.

Any $2^n\times 2^n$ grid with one square blacked out can be tiled with L shaped pieces of 3 units area.

Here is an example in the $4\times 4$ case.

$n^5-n$ is divisible by 10 (really is divisible by 30 but why work that hard). It is also a specific case of Fermat's little theorem.

The false proof, "All horses are the same color" is worth demonstrating.

https://en.wikipedia.org/wiki/All_horses_are_the_same_color

• The L shape tiling question was already posted when you posted your answer. – 6005 Sep 15 '16 at 6:49

I like this one, it is not that challenging but it is quite interesting:

Finite many lines divide a plane into regions. Show that these regions can be colored by two colors in such a way that neighboring regions have different colors.

We will do the proof using induction on the number $n$ of lines. The base case $n=1$ is straight forward, just color a half-plane black and the other half white.

For the inductive step, assume we know how to color any map defined by $k$ lines. Add the $(k+1)$st line. Keep the colors the same on one side of the line and on the other side invert the color of all regions. The process is illustrated below:

Note that regions that were adjacent previously continue to have different colors. Regions that share a segment of the $(k+1)$st line, which were part of the same region, now lie on opposite sides of the line and, therefore, have different colors. This shows that the map satisfies the required property and the induction is complete.

Elementary number theory

$\def\nn{\mathbb{N}}$Take any $x,y \in \nn$.

We say that $d$ is a gcd of $x,y$ iff $d \in \nn$ and $d \mid x,y$ and $k \mid d$ for any $k \mid x,y$.

Define $\gcd(x,y)$ recursively as $\cases{ x & if$y = 0$\\ \gcd(y,x) & if$x<y$\\ \gcd(x-y,y) & if$x \ge y > 0$}$.

1. Prove that $\gcd(x,y)$ terminates (is well-defined).

2. Prove that $\gcd(x,y)$ is a gcd of $x,y$.

3. Prove that $\gcd(x,y) = ax+by$ for some integers $a,b$.

The proof of (1) is a standard induction on the 'size' of the input, for which we could for example use $x+y$. The proof of (2) is also standard but more interesting; the base case is that $\gcd(x,0) = x$ and that $x$ is a gcd of $x,0$, and the inductive case requires proving that if $d$ is a gcd of $x-y,y$ then $d$ is a gcd of $x,y$. The proof of (3) is the nicest part of all; simply observe that both inputs in the recursive calls are always integer linear combinations of the original inputs, and hence at the end the output is also an integer linear combination!

This kind of induction is very important in all areas of mathematics where we use an inductive construction. This specific example is also very instructive because it gives a clear insight into Bezout's identity unlike many textbooks that pull the alternative definition of $\gcd(x,y)$ (as the minimum integer linear combination of $x,y$) out of thin air, or prove it by contradiction and well-ordering, which is not as constructive or intuitive.

Graph theory

Take any graph $G$.

We say that $G$ is $2$-vertex-connected iff removing any vertex from $G$ leaves it connected.

Prove that if $G$ has at least $3$ vertices then any $2$ vertices are in some cycle in $G$.

The proof I have makes use of the extremal principle, which is another extremely useful technique that arises from induction. Take any $2$ vertices $u,v$ in $G$. First note that $u$ has at least $2$ neighbours in $G$ (this uses the condition that $G$ has at least $3$ vertices). Thus $G - u$ has a path between any $2$ neighbours of $u$, and hence $G$ has a cycle through $u$. Let $C$ be a cycle in $G$ through $u$ that is closest to $v$ in $G$. Note that the cycle "closest to $v$" exists by well-ordering (which is from induction), and that there may be more than one such cycle (which is why I used "a"). Now it is not hard to prove that $C$ must pass through $v$ otherwise we can construct a cycle that is closer to $v$ in $G$.

Induction in the form of extremal principle is a very powerful tool because it allows extracting information 'for free'; existence of any kind of object immediately implies existence of a smallest instance of that kind, where the size of the relevant objects is a natural number. This generalizes to any well-order, and choosing the minimal ordinal that satisfies something is frequently used in set theory.

Inequalities

Someone mentioned the AM-GM inequality, but I do not see the point in teaching Cauchy's proof since I have never found the technique useful anywhere else. Instead, I recommend teaching the smoothing technique (see here and here for two examples). In the case of the AM-GM inequality, simply note that if not all are equal to the mean $m$ then there are two of them, which we shall call $x,y$, such that $x < m < y$. Now simply push $x,y$ together while keeping their sum constant, until one hits $m$. Their product will increase (by trivial algebra), and we have at least one more equal to the mean. By induction, in finitely many steps all will be equal to the mean and the product has increased, thus the inequality and equality case follow.

• If you want a reasonably hard problem that can be solved by induction, see matheducators.stackexchange.com/a/2449/1550. – user21820 Sep 15 '16 at 4:27
• I don't think a graph theory problem is appropriate for a calculus class, but the number theory problem is nice – Jacob Maibach Sep 19 '16 at 15:48
• @JacobMaibach: The question said "maybe foreshadows", so I decided to give examples of what I felt every student ought to learn but few do. =) – user21820 Sep 19 '16 at 16:10

Prove that, for all positive integers $n$, there exists a partition of the set of positive integers $k\leq 2^{n+1}$ into sets $A$ and $B$ such that

$$\sum_{x\in A} x^i = \sum_{x\in B} x^i$$

for all integers $0\leq i\leq n$.

• @user21820 at $n=1$ all we care about is the exponents $i=0$ and $i=1$. $1^0+4^0 = 2^0+3^0$ and $1^1+4^1=2^1+3^1$ so it is true for $n=1$. – Carl Schildkraut Sep 15 '16 at 4:12
• Oh sorry I thought $n = 2$... So you actually mean that the same partition works for all $i$ in the range $[0..n]$? Interesting.. it would be nice if you included a proof sketch. – user21820 Sep 15 '16 at 4:15
Let $T$ be a rooted tree with an infinite number of nodes, each with a finite number of children. Then $T$ has a branch of infinite length.

The proof is easy, but can be used as introduction to some advanced ideas.

Show equivalence of these three statements:

• Greatest Lower Bound: Every non-empty set of natural numbers has a least member.

• "Weak" Induction: Suppose for all natural numbers n, P(n) implies P(n+1), and P(0) is true. Thus P(n) is true for all natural numbers n.

• "Strong" Induction: Suppose for all natural numbers n, if P(i) is true for all i < n, then P(n) is true. Then P(n) is true for all natural numbers n.

• An interesting exercise, but not what was asked for. – jwg Sep 15 '16 at 10:07
• @jwg How so? They are proofs. The easy way to do it is to form a circle of implies, and 2/3 legs are clearly induction proofs. The bound part foreshadows the difference between discrete and non-discrete situations, (where similar lower bounds have different implications), which a good calculus course should run into shortly. – Yakk Sep 15 '16 at 11:14
• Sorry, but the proofs of these implications are not induction proofs, although they resemble induction proofs. – jwg Sep 15 '16 at 15:27
• @jwg You appear to have a different definition of "induction proof" than I do. What is your definition of "induction proof"? – Yakk Sep 15 '16 at 15:59
• "Greatest Lower Bound $\implies$ Weak Induction" obviously isn't an induction proof. "Weak Induction $\implies$ Strong Induction" is quite trivial (if $P(i)$ is true for all $i<n$, then of course either $n=0$ (where any statement is vacuously true for all $i<n$) or it is especially true for $i=n-1$) and that proof neither is, nor resembles an induction proof. So the only remaining proof is "Strong Induction $\implies$ Greatest Lower Bound". I wonder where you get two induction proofs here. – celtschk Sep 16 '16 at 7:51

The proof that any polygon in the plane can be triangulated without adding any new vertices.

Assume for n-1 vertices.

Take a vertex, v, with interior angle less than 180 degrees. Take the two vertices next to it. Draw a line between them. If this doesn't intersect (or contain) the polygon we have divided into a smaller polygon and a triangle and so we can apply the inductive hypothesis. Otherwise, we slide the two ends towards the vertex, eventually it will not intersect the polygon. Take the last vertex, w, the line crosses and draw a line from v to w. Then apply the inductive hypothesis.

(see my book Proof Patterns for further discussion and more examples.)

• This is ok only if you have already proven the JCT (Jordan curve theorem) for polygons; if not how do you define "triangulation" and "interior angle" in the first place? See math.stackexchange.com/a/1877524/21820 for an elementary proof of the JCT for polygons. I do not think there is a significantly simpler rigorous proof. – user21820 Sep 15 '16 at 4:39
• By the way, your proof is incorrect. The line may not intersect the polygon but the triangle may enclose the rest of the polygon, and the induction fails. – user21820 Sep 15 '16 at 4:48
• you can define interior or exterior according to the parity of how many times a ray crosses the polygon from a given point. You can also prove the Jordan curve theorem that way. – Mark Joshi Sep 15 '16 at 5:08
• I am very well aware of that purported proof, and please write it out to see that to make it rigorous is not going to be easy! Even the published version of that proof leaves out the details of the crucial part of the proof, so it seems much simpler than it really is. – user21820 Sep 15 '16 at 5:19
• Your edited answer has fixed the error I mentioned earlier, but note that although it is intuitive, as written it is not a good example of a rigorous proof because intuition is very bad for general mathematical objects. In particular, multiple ways of sliding work, but you need to explicitly pick one and prove that there is a last vertex crossed, and that connecting $v,w$ leads to the polygon being split into two non-overlapping regions. If you read my linked proof, it is not so simple as you may think! – user21820 Sep 15 '16 at 8:34

Another idea: The set of triangular numbers modulo $n$ yields $\mathbb{Z}/n\mathbb{Z}$ iff $n$ is a power of $2$.

This problem arose in my secondary school problem solving class (under a friendlier guise/phrasing). A few write-ups indicating how induction is used to prove the result can be found online with just a bit of googling.

Here is one presentation under the name of Daniel Finkel's Circle Toss Game from the New York Times' Numberplay blog, and here is another in a wordpress blog that attributes an earlier proof to D Knuth in his book The Art of Computer Programming (vol. 3).

Earlier idea: How about proving the Inclusion-Exclusion Principle (IEP) by induction?

ProofWiki link can be found here.

(This came to mind as I recently read over MO 249523 on Dwork's Theorem, in which induction is used a few times, and the IEP is used a few more!)

Prove that every natural number $n \geq 24$ is a sum of $5$'s or $7$'s. For example, $29 = 5 + 5 + 5 + 7 + 7$ and $33 = 5 + 7 + 7+ 7 + 7$.

[Comment: It is possible to prove this using normal induction or strong induction. There are also more direct ways to do this problem.]

• For $a$ and $b$ relatively prime, max number you cannot make is $ab - (a+b)$. Here, that is $35-12 = 23$; so you can make all positive numbers $geq 24$. – Benjamin Dickman Sep 28 '16 at 13:52

Here is an example which has as additional challenge the need for a proper generalisation.

Show that following is valid: If $A_1+\cdots+A_n=\pi,\text{ with } 0<A_i\leq \pi, 1\leq i\leq n$, then \begin{align*} \sin A_1+\cdots +\sin A_n\leq n\sin\frac{\pi}{n}\tag{1} \end{align*}

Let us denote with $P(k)$ the claim for a given $k$ and suppose as induction hypothesis $P(k)$ to be true.

If we look at the induction step $P(k+1)$: \begin{align*} \sin A_1+\cdots +\sin A_k+\sin A_{k+1}=\pi\qquad \text{with }\qquad 0<A_i\leq \pi,1\leq i\leq k+1 \end{align*}

it is not that clear how to make use of $P(k)$.

One attempt could be to group $A_k$ and $A_{k+1}$ together, so that $A_1+\cdots+(A_k+A_{k+1})=\pi$. Applying the assumption $P(k)$ yields \begin{align*} \sin A_1+\cdots +\sin A_{k-1}+\sin\left(A_k+A_{k+1}\right)\leq k\sin \frac{\pi}{k} \end{align*}

But it's not at all clear how to deduce $P(k+1)$: \begin{align*} \sin A_1+\cdots +\sin A_k+ \sin A_{k+1}\leq (k+1)\sin \frac{\pi}{k+1} \end{align*}



Generalisation is the key to conveniently solve this problem. Instead of requiring that the $A_i$'s add to $\pi$ we reformulate the condition in a more general setting. We consider the proposition $Q(n)$:

If $0<A_i\leq \pi, 1\leq i\leq n$, then \begin{align*} \sin A_1+\cdots+\sin A_n\leq n\sin\left(\frac{A_1+\cdots+A_n}{n}\right) \tag{2} \end{align*}

Note, that $Q(n)$ implies $P(n)$. Since, if we put $A_1+\cdots+A_n=\pi$ in (2) we obtain (1).

So, let's have a look at $Q(n)$:

We can see at a glance that $Q(1)$ is true.

Now, assuming the validity of $Q(k)$ and $0<A_i\leq \pi, 1\leq i\leq k+1$, we obtain

\begin{align*} \sin A_1&+\cdots \sin A_k+\sin A_{k+1}\\ &=k \sin \left(\frac{\sin A_1+\cdots +\sin A_k}{k}\right)+\sin A_{k+1}\\ &=(k+1)\left[\frac{k}{k+1}\sin\left(\frac{\sin A_1+\cdots +\sin A_k}{k}\right) +\frac{1}{k+1}\sin A_{k+1}\right]\\ &\leq (k+1)\left[\sin \left(\frac{k}{k+1}\left(\frac{A_1+\cdots+A_k}{k}\right)+\frac{1}{k+1}A_{k+1}\right)\right]\tag{3}\\ &=(k+1)\sin\left(\frac{A_1+\cdots+A_{k+1}}{k+1}\right) \end{align*}

and the result follows by induction.

In step (3) we use for $m,n>0$ and $0<\alpha,\beta\leq \pi$ the validity of \begin{align*} \frac{m}{m+n}\sin \alpha +\frac{n}{m+n}\sin \beta\leq \sin\left(\frac{m}{m+n}\alpha+\frac{n}{m+n}\beta\right) \end{align*}

The proof of this inequality could be left as challenge.

Note: This is example 2.4.1 in Poblem-Solving Through Problems by Loren. C. Larson.

• On the interval $[0,\pi]$ Sine function is concave down. Therefore we can use the Jensen's inequality to prove this nice result. – Bumblebee Dec 23 '16 at 4:15
• @Nil: Good observation! :-) – Markus Scheuer Dec 23 '16 at 8:19

Very good question!

The problem six of the IMO 2009 can be founded here:

https://www.imo-official.org/year_info.aspx?year=2009

The idea that is used in the problem is so simple, is an induction argument, but is challenging! That problem was the most difficult in that year and so, by score, that problem is ranked as on of the hardest problems in all the history of the International Mathematical Olympiad!!! No more words, enjoy it!

Quite a tricky (for beginners) induction proof: show that if $*$ is an associate binary operation on a set $S$, then the value of $$a_1*a_2*\cdots*a_n$$ is independent of the bracketing.

Construct the natural numbers $\mathbb{N}$ by using the Peano Axioms. Denote by $\varphi:\mathbb{N}\rightarrow\mathbb{N}$ the map defining the injective map associating each number to the "next one".

Show that the map $+:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ defined by $$n+1=\varphi(n),\qquad n+\varphi(m)=\varphi(n+m)$$ ís a commutative associative operation.

• The question isn't asking for a problem which is hard without induction, but rather one where the induction proof itself is hard. – Noah Schweber Sep 16 '16 at 23:11
• I edited my post and put a harder induction problem. – LaloVelasco Sep 16 '16 at 23:31