How to make sure that inductive proofs keep up with reality?

Question

In my math course, I'm requested to use inductive reasoning to prove that

$$ d_n = \frac{n^2 - 3n}{2} $$

is the equation to describe the number of diagonals inside a convex $n$-gon with $n \ge 4$.

Now, as I understand it, I first need to show that this holds up for $n = 4$, then for $n = k$ and then that it holds up for $n + 1$, too, so the "domino-stones fall down in order".

But how does this make sure that this really works for all n-gons? There might be an equation that works for $n = 4, n = 5, n = 6, ...$, but at some point stops to corresponding with real n-gons.

How does inductive proving "keep track of reality" this way? Why is assuming $d_n$ to be true for let's say 4 ensure it's still true for $n = 1000000$ with real n-gons? The equation might not even lead to contradictions, it might describe some process absolutely correctly, but I don't get how it surely describes the number of diagonals in an n-gon with certainty. For me it seems that this connection is lost once we derived a possible formula and try our proofs.

Can inductive reasoning this way really prove this? Or is it in reality needed to understand how that proof was derived to be sure that it is correct?

Answer 1

Inductive reasoning does not hinge on some 'educated guess' or formula which holds for the first $N$ or so natural numbers. It relies on the 'Induction Principle'. If we have some statement $P(n)$ which depends on a natural number $n$ and which may or may not be true, and we prove that

• $P(0)$ holds

• If $P(n)$ holds, then $P(n + 1)$ holds,

then by the Induction principle, the statement holds for all $n \in \mathbb{N}$.

We can also change $0$ by some other natural number $T$ and concluce the statement holds for all $n \geq T \in \mathbb{N}$.

In your particular example, prove the statement holds for $n = 4$, and then prove it holds for $n + 1$ if it holds for $n$. Hint: how many additional diagonals can you draw if you add one vertex?

Answer 2

Borrowing the language of Alexander Geldhof, here is another way to look at it.

If you've followed the steps for induction correctly, you've proved $P(0)$ and $P(n) \Rightarrow P(n+1)$.

Now, let's assume that what you said is true, i.e. that it works for some values and then suddenly stops. I.e. $P(0)$, $P(1)$, $P(2)$, ... $P(m)$ are true but $P(m+1)$ is not true.

But, that contradicts what you proved above i.e. $P(n) \Rightarrow P(n+1)$. So that can't happen.

In other words, if $P$ were true for a bunch of values and then suddenly stopped, you would not be able to prove $P(n) \Rightarrow P(n+1)$ (unless, of course, you make a mistake in the proof).