0
$\begingroup$

Let's say I have a claim, $P(n)$, that I want to show true for all $n \in \mathbb{N^+}$.

I would start by showing $P(1)$ holds. Then for the inductive step, I would take an arbitrary integer $m > 1$, and assume $\forall i \in \mathbb{N^+}\: i < m$, $P(i)$ holds.

My question is the subtle difference betwen letting $m \geq 1$ or $m > 1$. If it were $m \geq 1$, then it would be redundant if you examined $m=1$, as you would have a vacuous statement so you're proving $P(1)$ unconditionally, but that's exactly what we did in the base case!

So I would think $m > 1$ would be better style, but I'm not sure what's more commonly accepted in the mathematics community. I've seen it written both ways, but using the non-strict inequality seems iffy to me.

$\endgroup$
1
$\begingroup$

In fact, you need to make sure that the arbitrary case includes the base case, otherwise you can't make the inductive step. You could have the case where $P(1)$ is true, but $P(1)$ does not imply $P(2)$ for some reason.

For example, there's a false proof that "all horses in a group are the same horse" that goes something like this:

  1. In a group of 1 horse, all horses are the same horse.
  2. If, in a group of $n$ horses, they're all the same horse, then in a group of $n+1$ horses, they're all the same horse. PROOF: Take the group of $n+1$ horses and remove one horse. You now have a group of $n$ horses, which by assumption are the same horse. Replace the horse you removed and remove a different one, all $n$ horses are again the same horse. Therefore all the horses in the group are the same horse, so the statement is true for $n+1$.
  3. Therefore, all horses in any group are the same horse.

The failure is specifically because when you have a group of 2 horses you can't remove 1 horse, then replace it and remove another, and use that to compare the horses in the group, because you've never had any other horses to compare against.

$\endgroup$
  • $\begingroup$ Thank you. I'm wondering if you could clarify why you can't make the inductive step if the arbitrary case doesn't include the base case, as here it seems like you would need two base cases, one for $n=1$ and one for $n=2$. But in my scenario, I don't exactly see why taking $m>1$ would invalidate the proof if you're just proving $P(m)$. $\endgroup$ – rb612 Oct 26 '17 at 6:55
0
$\begingroup$

In the context you describe, you are correct that $m>1$ is what you need. Indeed if you used $m\geq1$ then for $m=1$ the set of inductive assumptions would be empty and the induction argument you make using them for $m=1$ might be false. That is why mathematical induction uses two steps.

If the context were slightly different, where the inductive step was stated as: assume $P(m)$ holds to prove $P(m+1)$ holds, then you would use "for $m\geq1$." That may be the kind of situation in which you saw it used.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.