What are some good, elementary and maybe also interesting proofs by induction? I am hosting a one-time class/talk on the concept of infinity for some (talented) high-school students. I want to teach them about proof by induction and I want them to do some exercises (you learn math by doing!). I am therefore looking for easy, elementary and maybe also intersting exercises for someone with little to no experience in proving statements. Some examples that came to mind:

*

*Proving $n \leq n^2$.

*Proving $n! \leq n^n $.

*Proving that the angle sum in an $n$-sided polygon is $(n-2)180^\circ$ for $n \geq2$.

*Proving Bernoulli's Inequality: $(1+x)^n \leq 1+nx$ for all $x \geq -1$.

I have looked at the thread Examples of mathematical induction but most if not all of the examples given here I think are too difficult for the audience.
Any inputs are welcome and appreciated! The result and its' induction proof need not be 100% rigorous, the point is to illustrate the induction proof in simple settings.

A few problems I often use when teaching induction:

*

*You have a collection of $3^n$ coins and a balance. All coins except one are genuine, and one of them weighs more than the rest. Prove you can always find which one is counterfeit using only $n$ weighings on the balance.

*Now do this where you have $3^n - 1$ coins, where either there is a single heavier counterfeit or all coins are the same weight, and the goal is to determine which is the case. You again have $n$ weighings.

*You have a $1 \times n$ chocolate bar. You eat the bar by breaking off a piece from the left of whatever size you’d like, eating it, and repeating until the bar is fully eaten. How many different ways can you eat the chocolate bar? (It’s $2^n$.)

*You have a “jumbled inequality” consisting of $n \ge 2$ blanks with inequality signs < and > interspersed, such as _ < _ > _ > _ < _. The goal is to fill the blanks in so that each consecutive pair of numbers is properly related. Prove you can always fill in $n$ blanks with the numbers 1, 2, …, $n$, using each of those numbers exactly once.

*You have a $2^n \times 2^n$ checkerboard with exactly one square removed. Prove you can cover the rest with L-shaped triominoes without overlap.

*Prove that all rational numbers can be written as continued fractions.

*Prove that all rational numbers can be written as Egyptian fractions.

*You can make a hexagonal pyramid of cans as follows. The top layer has one can. The second has seven arranged in a hexagon with a side length of one. The third has 19 in a hexagon with a side length of two. Prove that a tower of $n$ layers has exactly $n^3$ cans.

Hope this helps!
