Can someone give me an example of a challenging proof by induction? 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.
 A: 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$ }$.
  
  
*
  
*Prove that $\gcd(x,y)$ terminates (is well-defined).
  
*Prove that $\gcd(x,y)$ is a gcd of $x,y$.
  
*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.
A: 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$.
A: 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!)
A: 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.
A: 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.
A: 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.
A: 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.)
A: 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:


*

*Prove that if the inequality is true for $n$ numbers, it is true for $2n$ numbers.

*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.
A: 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.
A: 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.]
A: 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
A: 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.
A: 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!
A: 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.
A: 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.
