Can someone give me an example of a challenging proof by induction? [closed]

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.

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.

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.

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

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.