What is a good example to show high school students why a proof for induction is a reasonable kind of proof?

Question

I teach average-level high school students who have not had much beyond Algebra 1. I want to show them why induction makes sense. I want the sort of problem where it is intuitive that a statement is true for n=3 provided it is true for n=2, etc. All the ones in the textbooks I find involve proving conjectures that I feel one would not discover by looking at n=1, then n=2, then n=3, etc, or they are too hard/abstract for my students, or it is not immediately clear why one would think to do an inductive proof on them (e.g. the typical summation problems). I'm thinking about say, you are reading a textbook, and it says something like "and clearly that follows by induction"....so, the kind of theorem that naturally makes you think of an inductive proof. I found one that I like, which is the following:

Proving that $n!\geq 2^n$ for $n\geq 4$. I like this one because we can see it is true for 4, that is, we know that $$4\cdot3\cdot 2\cdot 1\geq 2\cdot 2\cdot 2 \cdot 2$$ and so then because $5\geq 2$, it follows from a preservation property of inequalities that $$5\cdot 4\cdot 3\cdot 2\cdot 1\geq 2\cdot 2\cdot 2\cdot 2\cdot 2$$

With this sort of example, the students can see why a proof by induction makes sense: we just keep using previous knowledge. We look at the case for $n=4$ and see it works, and then almost immediately from that we see that it works for $n=5$, etc.

The problem with this example is that is starts at $n=4$. I want something that starts at $n=1$ as the first induction example I give them, and I don't just want to do $$(n+4)!\geq 2^{n+4},$$ because I think that would confuse them more. Any ideas?

I have been to this question: Examples of mathematical induction but it did not help, as I needed a much simpler example for my students.

Answer 1

How about showing that the number of subsets of a given set $A$ with $n$ elements is $2^n$? It is easy to exhaust $n=1$, $n=2$ and $n=3$ by simply writing them down and then the inductive argument is that when you add another element then you can form all the old subsets with or without that new element... This seems quite intuitive IMO.

A more number-related example which may be too simple could be to show that there are $10^n-1$ natural numbers with $n$ or less decimal digits. Maybe that seems too obvious but then you could show that there are $5^n$ with $n$ decimal digits or less NOT using even digits (noting that zero is even).

These were all I could come up with right now.

Answer 2

Once a student spots a pattern, induction is a natural approach to formalize the proof. I would suggest looking up various interesting patterns (or ask your kids for some) and then get them to demonstrate that it is true via induction.

I would suggest the sum of the first $n$ odd numbers. If you play around with it, it is very easy to see that the sum is always a square number.

An induction proof is almost immediate. You can bring in the gauss reference as summing of an arithmetic progression. You can also give a pictorial proof of sequentially adding layers of a square.

I did this with middle school teachers and they loved it. They came up with several different ways of showing it, after seeing the pattern. They also tried finding a sum to give cubes, which is somewhat trickier. Visualizing peeling apart a cube is helpful here, if they are not mathematically inclined.