25
$\begingroup$

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.

$\endgroup$
11
  • 30
    $\begingroup$ One small piece of unsolicited advice. What is interesting and challenging (to you) may not be well-received by the average beginning calculus student. Unless they are particularly gifted students, don't take this too far outside their comfort level, or you'll lose them completely. $\endgroup$ Commented Sep 14, 2016 at 20:11
  • $\begingroup$ I wrote a proof by induction for the highest power of a prime $p$ dividing $n!$ math.stackexchange.com/questions/110553/… $\endgroup$
    – Will Jagy
    Commented Sep 14, 2016 at 20:15
  • 5
    $\begingroup$ Isn't Wiles' proof of Fermat's Last Theorem a proof by induction? :) $\endgroup$
    – Exit path
    Commented Sep 15, 2016 at 4:06
  • 4
    $\begingroup$ The answer to the question in the title is "yes". $\endgroup$ Commented Sep 15, 2016 at 11:25
  • 2
    $\begingroup$ Some posts from the past which might be worth looking at in connection with this: Examples of mathematical induction, Good examples of double induction, Examples of "exotic" induction at MO. It might be worth looking also among questions tagged induction+examples or induction+big-list. $\endgroup$ Commented Sep 16, 2016 at 5:20

15 Answers 15

30
$\begingroup$

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.

$\endgroup$
4
  • 15
    $\begingroup$ For $n \geq 0$, in fact. $\endgroup$ Commented Sep 15, 2016 at 8:39
  • 3
    $\begingroup$ @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! :-) $\endgroup$ Commented Sep 15, 2016 at 21:12
  • 1
    $\begingroup$ MESE note about this problem and (some of) its history. $\endgroup$ Commented Sep 16, 2016 at 1:17
  • $\begingroup$ @BenjaminDickman thanks for the post about the problem's history. It's fascinating indeed! $\endgroup$
    – Alex Ortiz
    Commented Sep 16, 2016 at 1:25
24
$\begingroup$

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.

$\endgroup$
3
  • 8
    $\begingroup$ 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... $\endgroup$
    – user21820
    Commented Sep 15, 2016 at 3:51
  • 1
    $\begingroup$ @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. $\endgroup$
    – Bernard
    Commented Sep 15, 2016 at 7:44
  • 3
    $\begingroup$ 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. $\endgroup$
    – user21820
    Commented Sep 15, 2016 at 8:19
16
$\begingroup$

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:

enter image description here

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.

$\endgroup$
15
$\begingroup$

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. enter image description here

$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

$\endgroup$
1
  • 4
    $\begingroup$ The L shape tiling question was already posted when you posted your answer. $\endgroup$ Commented Sep 15, 2016 at 6:49
6
$\begingroup$

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.

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

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$.

$\endgroup$
4
  • $\begingroup$ @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$. $\endgroup$ Commented Sep 15, 2016 at 4:12
  • 6
    $\begingroup$ 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. $\endgroup$
    – user21820
    Commented Sep 15, 2016 at 4:15
  • 2
    $\begingroup$ I know this is 6+ years late, but this is a very fun problem, so I will just describe the sets A and B. Let $A_1=\{1\}$ and $B_1=\{2\}$ and $A_{n+1} = A_n \cup \{x+2^n~:~x\in B_n\}$ and $B_{n+1}=B_n \cup \{x+2^n~:~x\in A_n\}$. So the first few pairs of $A_n$ and $B_n$ are {1},{2}; {1,4}, {2,3}; {1,4,6,7}, {2,3,5,8}. $\endgroup$
    – Dan C
    Commented Jan 1, 2023 at 4:28
  • $\begingroup$ For the proof, the main thing that you need besides induction is Ovabzvny Gurberz (decode that with rot13.com) $\endgroup$
    – Dan C
    Commented Jan 1, 2023 at 4:30
5
$\begingroup$

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!)

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ An interesting exercise, but not what was asked for. $\endgroup$
    – jwg
    Commented Sep 15, 2016 at 10:07
  • 1
    $\begingroup$ @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. $\endgroup$
    – Yakk
    Commented Sep 15, 2016 at 11:14
  • $\begingroup$ Sorry, but the proofs of these implications are not induction proofs, although they resemble induction proofs. $\endgroup$
    – jwg
    Commented Sep 15, 2016 at 15:27
  • $\begingroup$ @jwg You appear to have a different definition of "induction proof" than I do. What is your definition of "induction proof"? $\endgroup$
    – Yakk
    Commented Sep 15, 2016 at 15:59
  • 1
    $\begingroup$ "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. $\endgroup$
    – celtschk
    Commented Sep 16, 2016 at 7:51
4
$\begingroup$

The König's Tree Lemma:

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.

$\endgroup$
0
3
$\begingroup$

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.)

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – user21820
    Commented Sep 15, 2016 at 4:39
  • $\begingroup$ 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. $\endgroup$
    – user21820
    Commented Sep 15, 2016 at 4:48
  • $\begingroup$ 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. $\endgroup$
    – Mark Joshi
    Commented Sep 15, 2016 at 5:08
  • $\begingroup$ 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. $\endgroup$
    – user21820
    Commented Sep 15, 2016 at 5:19
  • $\begingroup$ 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! $\endgroup$
    – user21820
    Commented Sep 15, 2016 at 8:34
2
$\begingroup$

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.

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

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!

$\endgroup$
1
  • $\begingroup$ A copy of the problem here for ease of access: Problem 6. Let $a_1, a_2, \ldots, a_n$ be distinct positive integers and let $M$ be a set of $n-1$ positive integers not containing $s=a_1+a_2+\cdots+a_n$. A grasshopper is to jump along the real axis, starting at the point 0 and making $n$ jumps to the right with lengths $a_1, a_2, \ldots, a_n$ in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in $M$. $\endgroup$
    – D.R.
    Commented Jan 22 at 8:11
2
$\begingroup$

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.]

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ Commented Sep 28, 2016 at 13:52
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The question isn't asking for a problem which is hard without induction, but rather one where the induction proof itself is hard. $\endgroup$ Commented Sep 16, 2016 at 23:11
  • $\begingroup$ I edited my post and put a harder induction problem. $\endgroup$ Commented Sep 16, 2016 at 23:31

Not the answer you're looking for? Browse other questions tagged .