Examples of natural proofs by induction exercises which needs 3 or more base cases?

Question

I am teaching proof by induction next week, so I am looking for new some good examples. I'd like some natural (so not just some linear recursion depending on three previous terms) problems where three or more base cases are needed.

The mathematical objects should be easy (so no graph theory).

My go-to example is the following: Prove that for every $n \geq 6$, one can find a subdivision of a square into $n$ smaller squares. The base cases are for $n=6,7,8$, and the induction proof boils down to that if $n$ is possible, then $n+3$ is possible (by subdividing a square in the subdivision into 4 smaller squares).

Answer 1

The question is

Examples of natural proofs by induction exercises which needs 3 or more base cases?

I think an elementary natural proof of the parity of the Somos-4 sequence is a nice exercise. Given the Somos-4 sequence of positive integers that satisfies $$ s_n s_{n-4} = s_{n-1}s_{n-3}+s_{n_2}^2,\quad s_n s_{n-5} = -s_{n-1}s_{n-4} +5s_{n-2}s_{n-3} $$ for all integer $n$, with initial terms $ s_1=s_2=s_3=s_4=1, $ then any five consecutive terms of the sequence has exactly one even term and the rest are odd. More precisely, $s_n$ is even iff $n$ is a multiple of $5$. The proof has two cases depending on $n$ being a multiple of $5$. The five base cases are for $n=1$ to $n=5$.

Answer 2

One type of proof is, prove any (optionally positive) integer can be written as $5k + 7j$ for integers $k$, $j$. You first prove that it is possible to make $1, 2, 3, 4, 5$. Then by induction any number follows by adding $5$ to a previous case. And any coprime pair of integers works, doesn't have to be $5$, $7$.