Induction, horses of the same color and manual checking of all $n$'s

Question

I suppose that you know the induction proof why all horses are of the same color and how it fails on $n=1$.

(just in case a few links: https://web.stanford.edu/~dntse/classes/cs70_fall09/cs70-2_notes3.pdf https://www.math.hmc.edu/funfacts/ffiles/30002.8.shtml)

The question is:

The proof(reasoning) fails on the step with n=1. For all other it is correct. But the proof by induction (not the strong one) doesn't require us to check all values of $n$. We just need to show some correct base case(0 or 1 in this problem) and prove that if something is true for $n$ is also true for $n+1$, which was done in this case (as I understand it).

Please share your thoughts about this, I've searched for several hours but wasn't been able to find any explanation.

Answer 1

But the proof by induction (not the strong one) doesn't require us to check all values of $n$. We just need to prove that if something is true for $n$ is also true for $n+1$, which was done in this case...

This is wrong. Induction requires a base case (generally this is checking whether argument holds for the smallest possible number that is given in the argument in weak induction). Then in inductive assumption, we assume the argument holds for all $n$ greater than the $n$ value we used in base case; then show whether it is true for $n+1$. It is not just $n$ and $n+1$, we need a base case and we also need to assume for all $n$ before proving for $n+1$.

Further information, I saw a good explanation in university, since it can be helpful, I will also share that one:

Let $P_0, P_1,P_2,...$ be statements. Then in classic induction:

If $P_0$ holds (base case) and each $P_n$ implies $P_{n+1}$ ($P_n \implies P_{n+1}$, inductive assumption), then $P_n$ holds for all $n$.

Answer 2

Ok, I didn't mention the base case (corrected), but I'm aware of it (it can be n = 0 or n=1). I understand that we make the assumption that $P_n$ must hold for all values $< n$ in case of strong induction, and logically in case of simple induction. B.t.w. from wikipedia:

The proof consists of two steps:

The base case: prove that the statement holds for the first natural number n. Usually, n = 0 or n = 1.

The inductive step: prove that, if the statement holds for some natural number n, then the statement holds for n + 1.

I ask another thing: in proving by induction we generally don't check the correctness of $P$ at specific values of $n$, but we did it in this case. Why?

Answer 3

It's all about the logic and the structure of the argument. That is, if you carefully lay out the logic you may find that the step does not work for certain $n$. So it is not as if beforehand we say "Hmm, I wonder if the step will go through for $n=117$ ... I better check!", but rather as you go through the proof you may find that some part of the argument just cannot be completed.

In particular, when in the horses argument you first take out horse $a$, and later on horse $b$, then you can only logically infer that all the horses in the two sets of remaining horses $S \setminus \{a \}$ and $S \setminus \{ b \}$ are the same color, and that would require for there to be a third horse $c$ that is in both of those sets ... so when there is no third horse, as when $n=2$, you can't make that logical step. Of course, when there is a third horse, as when $n>2$, you can.

So the structure of the argument will dictate that there may be different cases to check, and which specific ones. Of course, in many inductive proofs the structure of the argument is such that no further cases need to be separated, and the logic really does work for all $n$. It all depends on what specifically you are trying to prove, and how you are trying to prove it.