A question about induction proofs?

Question

From all the ones I've seen, they usually involve writing a formula for P(k+1). So my question is if that's necessary. Suppose P(1) is already verified. Then based on the assumption that P(k) is true, P(k+1) is necessarily true since P(1) is true. Then set k = 1. So besides verifying a formula for P(1), what's the point of writing a formula for P(k+1) after assuming it for P(k)? It seems like the proof is already contained in the logic.

Answer 1

Let's say we want to prove $$1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}.$$ Now, it's true when $n=1$, so we suppose that it's true when $n=k,$ and try to prove it when $n=k+1.$ So, we assume that $$1^2 + 2^2 + 3^2 + ... + k^2 = \frac{k(k+1)(2k+1)}{6}\tag{1}$$ and we try to deduce from that that $$1^2 + 2^2 + 3^2 + ... + (k+1)^2 = \frac{(k+1)(k+2)(2k+3)}{6}.\tag{2}$$

I think you'll agree that it take more work to get from (1) to (2) than simply observing that $1=1.$ What you need to do is ask yourself, "How can I use (1) to deduce (2)?" Well, (1) gives a formula for the first $k$ terms on the left-hand side of (2), so we can convert (2) to $$ \frac{k(k+1)(2k+1)}{6} +(k+1)^2 = \frac{(k+1)(k+2)(2k+3)}{6}.\tag{3}$$

Now we have to prove (3), and that's straightforward algebra. Make sure you understand how we used the assumption of (1) to aid in proving (2). It's what induction is all about.

Answer 2

If you prove only one or two or a finite number of cases for P you can’t conclude that P is always true.

The trick with induction is precisely to show that

• BASE CASE: P(m) is true for some value m (at least one)
• INDUCTIVE STEP: if P(k) is true then P(k+1) is true

in this way you can extend P(n) to all integers $n\ge m$.

Answer 3

Let P(k) stand for any k horses are the same color.

Then P(1) is true.

According to you, since P(1) is true, then P(2) is true. Do you really believe that?