Simple Examples where Base Case of Induction is non-trivial

Question

I want to explain the importance of the base case of induction to a 10-year-old kid. But I am finding it difficult to find examples where solving the base case is non-trivial.

For example, the sum of $n$ natural numbers from $1$ to $n$, is $T(n) = \frac{n(n+1)}{2}$. Its base case would be $T(1) = 1$, which is trivial to see. I do not want examples like this. Neither I want complicated examples. Can somebody suggest some easy but non-trivial examples here?

---

Note: The same question has been asked before here. But the examples therein are difficult to understand except this one. But I think the base case of this example is not provable. I am looking for non-trivial base case examples that are solvable. I hope you understand my point.

Answer 1

Consider the McNugget numbers problem:

Every positive integer greater than $43$ may be written as $6a+9b+20c$ with nonnegative integers $a,b,c$.

This can be proven by induction: write $44$ to $49$ in such a form (base case), then if $k$ is expressible in the given form then so is $6+k$ (inductive step). For the base case you have to explicitly write $44$ to $49$ in the given form, which is non-trivial.