Simple Examples where Base Case of Induction is non-trivial? 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.
 A: 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.
A: You want something a 10-year old can understand. How about the following:
Prove $n^2 - n$ is even for all positive integers $n$ by induction. That is a standard argument. Next, by skipping the base case, the same reasoning in the inductive step alone also “proves” $n^2-n$ is always odd for all positive integers $n$.
In a similar way, you could show first that $n^3-n$ is always even or is always a multiple of $3$ by induction and then skip the base case to “prove” by induction that $n^3-n$ is always odd or is always not a multiple of 3.
An even more basic false result that is consistent for the inductive step is $n > n+1$ for all positive integers $n$.
If you are going to say these examples are cheating (from a 10 year old’s perspective), does the 10 year old understand the point that only verifying the inductive step is an incomplete  method of proof? A proof with a missing step is not a proof: it can lead to false results. That is the point, whether or not it is considered cheating by the 10 year old.
A: *

*Let $D$ be a nonnegative symmetric function on a set $X,$ and suppose for all $x\in X,\, D(x,x)=0.$ And suppose you're given a particular definition: $D(x,y):=\cdots.$ The definition is different in different cases.  Say you want to prove this: For $x_1,\ldots,x_n\in X,$ $$D(x_1,x_n) \le D(x_1,x_2) + D(x_2,x_3) + \cdots + D(x_{n-1},x_n). $$ The base case is just the triangle inequality, and can be nontrivial (depending on how $D$ is defined). But the induction step is easy.


*$\log_a p \cdot\log_bq \cdot\log_cr\cdots\log_k x$ stays the same when the bases $a,b,c,\ldots,k$ are permuted while the arguments $p,q,r,\dots,x$ remain fixed.


*There is no horse of a different color. Proof: Express a set of $n+1$ horses as the union of two subsets of size $n.$ By the induction hypothesis, all horses within either of those two sets are of the same color. If two horses, $A$ and $C,$ are not both within the same one of those two sets, pick a third horse $B$ that is. Then the color of $A$ is the same as that of $B$ and that of $B$ matches that of $C,$ and this relation is transitive. The base case here is $n=2.$ It is hard to prove the proposition in that case.
A: How about something completely made-up and informal?
Theorem: At every age $n$, a person owns infinitely many ice cream cones.
Proof: Proof by induction: Assume every person of age $n$ owns infinitely many ice cream cones. A person of age $n+1$ must have had infinitely many ice cream cones one year prior, and assuming a lower bound to the volume of an ice cream cone and an upper bound to the speed of ice cream consumption, you can only eat finitely many ice cream cones in a year. Therefore the supply could only have shrunk by a finite amount, and remains infinite at age $n+1$. QED.
Obviously, the flaw of this proof is the fact that people are not born with an infinite amount of ice cream, i.e. the base case is not fulfilled.
