Good, simple examples of induction?

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

Here is another one:

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

I will give two proofs of it. First one is more involved and includes the following identity: $$(a^2+b^2)(x^2+y^2)= (ax+by)^2+(bx-ay)^2$$ yet the 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}

Answer 10

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.

Answer 11

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

Answer 12

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.

Answer 13

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

\begin{align*} \newcommand{soc}{\mathtt{sociability}} \newcommand{sub}{\mathtt{subordinates}} \newcommand{with}{\mathtt{with}} \newcommand{without}{\mathtt{without}} \soc &: \mathcal{T} \to \mathbb{R}^+\\ \sub &: \mathcal{T} \to 2^\mathcal{T} \\ \end{align*} then in mathematical notation it would be \begin{align*} \with(t)&= \soc(t) + \sum_{s\ \in\ \sub(t)} \without(s), \\ \without(t) &= \sum_{s\ \in\ \sub(t)} \max\big\{ \with(s), \without(s) \big\}. \end{align*}

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$

Answer 14

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.

Answer 15

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 written 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 written 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}

Answer 16

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

Answer 17

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<m$ 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)<f(18)=f(2)f(9)<f(2)f(10)=f(2)^2f(5)\\\implies f(3)<4\implies f(3)=3$$

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.

Answer 18

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.

Answer 19

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 (i.e. the version pertaining to functions of the form $x \mapsto x^n$ for $n\in\mathbb{N}$):

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$

I have several complaints about this approach:

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

Answer 20

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)

Answer 21

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.

Answer 22

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.

Answer 23

Every natural number is odd or even.

Answer 24

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

Answer 25

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.

https://medium.com/cantors-paradise/a-comprehensible-introduction-to-mathematical-induction-aef1a61eedcf

The used example is: $$1 + 2 + \cdots (n-1) + n = \frac{n(n+1)}{2}$$

Answer 26

Simple proofs (Proofs 1-3)

1. Bernoulli Inequality

2. Inequality of AM - GM (There various proof using mathematical induction. You can use standard induction or forward-backward induction.)

3. Newton's Inequality

Since you said looking for proof of surprising facts you can refer following below. Proofs are relatively straightforward with basic knowledge but some parts may be challenging.

Uses two variables in base case.

Graph theory: Ramsey numbers

R(s, t) <= R(s-1, t) + R(s, t-1)

Double mathematical induction

Number of partitions of x1 + x2 + ... xm = n

Proof of Maclaurin Inequality using Induction\

A generalisation of AM-GM inequality

Double mathematical induction partitions
Maclaurin Inequality
Ramsey's theory: Littlewood's inequality
Forward backward induction

Answer 27

1)Finitely many lines divide a plane into regions. Show these regions can be coloured by two colours in such a way that neighboring regions have different colours.
2)Showthat there are $2^n%$ number of events in the event space corresponding to the sample space of n number of sample points.

Answer 28

• Draw $n$ 0's and $n$ 1's around the perimeter of the circle, in any order.
• Is there a way to match (is there a bijection of) 0's with 1's by drawing arcs in the interior of the circle between {0,1}-pairs such that no two arcs intersect?

The answer is yes, by picking a consecutive {0,1} along the perimeter, drawing an arc between them, "stitching it out of the picture," and proceeding by induction. I like this example because

• it's not obvious a priori (I daresay),
• induction is "the right way" to solve it,
• it fits perfectly in the template of ordinary mathematical induction, and
• it has minimal mathematical prerequisites. You need to know that there is a consecutive {0,1} along the perimeter, and that the problem doesn't depend on the geometry of a circle, but could be done for any closed curve. Both are "obvious."

Answer 29

I'm quite surprised that nobody so far has mentioned the

Existence of prime factorization of integers: Every integer $n \ge 2$ can be written as a finite product of prime numbers.

Proof. It is true for $n=2$ since $2$ is prime, so let $n \ge 2$ and assume that the claim has been proved for all integers from $2$ to $n$.

If $n+1$ is prime, there is nothing to prove. If $n+1$ is not prime, then we can write it as $n+1 = ab$ for two integers $a,b \in \{2, \dots, n\}$; by induction hypothesis, $a$ and $b$ can be written as products of prime numbers, so the same is true for $n+1$. $\square$

Uniqueness of the factorization is more difficult, though.