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.

When I first studied Proof by induction in highschool, the very simple but interesting proof of $\sum_{i=1}^ni = \frac{n(n+1)}{2}$ was presented to me. I thought this to be very intuitive and quite straightforward. I believe this is quite well suited for your audience.
