1

Having proved that the property holds for the first case (most often 1), in the second step we need to assume that it's true for some $k \ge 1$. Why not $k>1$

Aemilius
  • 3,699
  • Hi! Why do we make the assumption of $P(k)$ being true? –  Oct 12 '17 at 06:03
  • 2
    Induction is a sort of unlimited chain of Modus Ponens. We have proved $P(0)$ and $P(k) \to P(k+1)$, for arbitrary $k$. Having proved $P(0)$, we can "instantiate" the induction step with $k=0$ to get: $P(0) \to P(0+1)$; by MP we get $P(1)$. Now repeat with $k=1$ to get from the induction step: $P(1) \to P(1+1)$ and by MP again we get $P(2)$. And so on... – Mauro ALLEGRANZA Oct 12 '17 at 06:09
  • It works if we do not "break" the chain. – Mauro ALLEGRANZA Oct 12 '17 at 06:09

3 Answers3

3

If you continue the proof it will go something like: Assume the statement is true for some $k \geq 1$, then we want to show that it holds for $k+1$. Taking only $k>1$ you're proving that the statement holds for $k+1>2$, so you've missed the case where $k+1=2$.

3

Suppose you take $k > 1$. So for some $k > 1$ you show that "if $P(k)$ is true, then $P(k+1)$ is also true".

This means you can use the following chain of implications:

  • If $P(2)$ is true, then $P(3)$ is true.
  • If $P(3)$ is true, then $P(4)$ is true.
  • If $P(4)$ is true, then $P(5)$ is true.
  • etc.

However, in order to start this chain you have to start at $k = 2$ since the first step in the chain says:

  • If $P(2)$ is true, then $P(3)$ is true.

Now, you mentioned that you started your proof by showing that $P(1)$ is true. This becomes useless because you can't use it to start the chain. What is missing in your chain is the step:

  • If $P(1)$ is true, then $P(2)$ is true.

You can add this part to your chain by assuming $k \geq 1$ in the induction step. Then the chain of implications becomes

  • If $P(1)$ is true, then $P(2)$ is true.
  • If $P(2)$ is true, then $P(3)$ is true.
  • If $P(3)$ is true, then $P(4)$ is true.
  • If $P(4)$ is true, then $P(5)$ is true.
  • etc.

and you can use $P(1)$ to start the chain.

Flatfoot
  • 136
1

It's because if you don't you loose the connection with the first case. The idea is that you should in principle be able to step from the first case to any integer.

If you don't assume it's only valid for some $k>1$ and prove that it's valid for $k+1$ then that step would only be valid if you step from $2$ and higher.

For counter example where this goes wrong we could consider the statement $P(n): n\ne 2$. First since $1\ne2$ we have that $P(1)$ is true. Now assume that $P(k)$ is true for some $k>1$ then $k+1>2$ so $k+1\ne 2$. This would mean that all positive integers are different from $2$ (which obviously isn't true).

skyking
  • 16,654