4
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ If your only point is that it's important to verify the base case, you could falsely state that $T(n) = \frac{n(n + 1)}{2} + 1$ and "prove" it by only doing the inductive step. $\endgroup$ May 21 at 5:30
  • $\begingroup$ @MarkSaving I get your point. But that is cheating (this is what the kid would say). :P $\endgroup$
    – IY3
    May 21 at 5:32
  • $\begingroup$ The finite Ramsey's theorem bound $R(r,s)\leq\binom{r+s-2}{r-1}$ is easy enough to state and understand and isn't as trivial as you might think. $\endgroup$ May 21 at 5:35
  • $\begingroup$ The base case usually is trivial. Trivially true or trivially false. But you need the base case to be true in order for induction to proceed. That's the point that should be emphasized to your student. $\endgroup$
    – quasi
    May 21 at 5:47
  • 1
    $\begingroup$ I think @KCd's point may be that either the base case is usually either trivial or really complicated, there aren't many in-between cases that would be suitable for a child. $\endgroup$
    – Barmar
    May 21 at 13:50
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Good one! I myself took time to prove the base case. $\endgroup$
    – IY3
    May 21 at 6:16
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer. For the examples where induction is correct, the base case is simple here, i.e. $n = 1$. Isn't it? $\endgroup$
    – IY3
    May 21 at 6:23
  • $\begingroup$ Yes, the base case is easy to check. My point is to get the 10-year old to do a valid inductive proof first in order to point out that if that easy step is skipped then the same reasoning in the other part (inductive step) can “prove” incorrect results. The lesson is that even if the base case is easy, if you ignore it then you could “deduce” false results. So the base case is important to check even if it is easy. $\endgroup$
    – KCd
    May 21 at 6:34
  • $\begingroup$ Yes yes. I got that point already. :) $\endgroup$
    – IY3
    May 21 at 6:36
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.