Mathematical Induction. Horses made me question my understanding [duplicate]

Question

This question already has an answer here:

• Questions on “All Horse are the Same Color” Proof by Complete Induction 6 answers

I recently read about the false inductive proof that all horses are the same colour. There are some mathSE threads about this already (MathSE_thread_1, MathSE_thread_2).

After reading this, I now realise I have never really understood mathematical induction. It seems obvious for sums, but when presented with this example I was stumped.

I have some questions:

Question 1. The inductive step

for all horses are the same colour goes roughly as follows:

Assume that there are n horses, numbered 1 to n. By induction horses 1 through (n-1) are the same colour, and similarly horses 2 through n are the same colour. The overlapping sets H_0 = {1,2,...,(n-1)} and H_1 = {2,3,...,n} imply that horse 1 and horse n are the same colour. Thus all horses are the same colour.

I have an issue with one of the statements:

By induction horses 1 through (n-1) are the same colour, and similarly horses 2 through n are the same colour.

I understand why horses 1 through (n-1) are the same colour (by hypothesis), but why can we just say horse n is the same colour? It seems to imply the numbering is arbitrary to me, but then induction is completely invalid unless we can define an order?

Question 2. The base case:

If we grant the inductive step reasoning (of which I am unsure whether that is valid), the induction relies on the fact that for some k, two distinct k-1 subsets have shared elements, from which we can conclude they are all the same colour. So the base case should be n=2 (or should it be n=3?).

However the trick used in the inductive step seems to imply the numbering of the horses is arbritary (as I briefly mentioned above), so a subset of size n=2 would seem to require we prove all subsets of size 2 have horses which are the same colour, which makes the induction step redundant?

General Question 3.

How do we choose what inductive steps are valid, and what base cases are required? I realise this is poorly phrased, but is there a way in general, or a set of heuristics to enable a valid basis to be chosen?

A slightly modified version of Mathematical Induction that seems to me more intuitive

Perhaps my understanding of induction is incorrect. It seems to me mathematical induction is more intuitive when presented as follows:

For each positive integer n > n_0, Let p(n) be a statement.

Step 1. We first show that If p(k) then p(k+1) is true for every positive integer k. To do this we choose an arbitrary k and show, by direct proof usually, this implies (k+1)

Step 2. Choose a base case n_0 on which we induct on to all n > n_0. Here we use the fact that we have shown that for an arbritrary k, k+1 is implied. Choosing a valid basis allows the "induction domino effect" to work its magic.

Then we have shown p(n) is true for every positive integer n > n_0

That seems to me easier to understand. Although do we need to explicitly show our base case implies n_0 + 1?

I suppose this is a different way of asking the same question I asked above, namely how do we choose valid base cases?

Hopefully this question isn't too rambling. Please let me know if anything requires clarification.

Answer 1

Answer 1: Assuming the inductive hypothesis, we can say that horses $\{2,...,n\}$ are the same color because that is a set of $n-1$ horses and the inductive hypothesis states that they must be the same color. The failure in the proof is that when $n=2$, the two "overlapping sets" do not overlap, so the inductive step from $n=1$ to $n=2$ is invalid.

Answer 2: You are correct that if all pairs of horses were the same color, then all horses would be the same color. The "proof" doesn't need to use induction, but it does, since it seems to me that the point of its existence is to advise caution when using induction.

Answer 3: We can tell which inductive steps are valid by whether they actually hold for all cases that follow from the base case. The failure of the horse proof is that there is a particular step $p(1) \rightarrow p(2)$ for which it fails to hold.

I only see two differences in your modified version of induction. The first is that you switched the ordering of the base case and the inductive step from the usual phrasing. This isn't actually a change, since the order you prove them in doesn't matter. The second is that it is usually phrased with the base case being $n=1$ or $n=0$. This is because if you want to start at some other value of $n$, you can easily have the statement $p'(n) = p(n-k)$ to shift everything around. So again, this isn't really a change.