1
$\begingroup$

The principle of mathematical induction says that if $S(n)$ is some mathematical assertion about the natural number $n$ such that if $S(1)$ is true, and if the truth of $S(n)$ implies the truth of $S(n+1)$, then $S(n)$ is true for every natural number $n$. Some books refer to this principle as weak induction.

Strong induction allows me to assume that $S(\, j \,)$ is true for all natural numbers $1 \leq j \leq n$; however, the book I am using does not mention it, so I assume that I cannot use it.

Question In general, is it permissible to use the truth of the base case during the inductive step when employing weak induction?

Here is the particular problem I am working on, which comes from Fitzpatrick's Advanced Calculus text.

I have to prove that if $n$ is a natural number, and $S(m)$ is the statement concerning the natural number $m$, "If m < n, then $n-m \in \mathbb{N}$". During the inductive step, I assumed that $m+1 < n$. I then reasoned that if I could show that $n-1$ is a natural number, then the proof follows immediately. However, in order to show that $n-1$ is a natural number, I demonstrated that if $n>m+1$, then $n>1$, which from the base case implies $n-1 \in \mathbb{N}$.

$\endgroup$
  • 3
    $\begingroup$ Yes, of course. $\endgroup$ – Andrés E. Caicedo Jun 6 '18 at 14:28
  • 2
    $\begingroup$ Yes, of course you can, since it has been established at the initial step: it's not a hypothesis. $\endgroup$ – Bernard Jun 6 '18 at 14:28
  • $\begingroup$ Thanks, guys. I can't believe I never realized that I could do that even though I've been using induction for years haha. $\endgroup$ – Benedict Voltaire Jun 6 '18 at 14:29
  • $\begingroup$ Btw. You can use strong induction in disguise by proving with weak induction the assertion $T(n):=S(k)\text{ is true for every }k\leq n$ $\endgroup$ – drhab Jun 6 '18 at 14:31
0
$\begingroup$

Yes, in general because you showed that this base case is true.

The point of (weak) mathematical induction is as follows. You show that the base case is true. If you show that if the nth case is true, then the n+1th case must be true, then this is what is really happening: if the first (base) case is true (which you proved already), then the second is true. It follows that if the second case is true (which it is), then the third is true. And so on, so forth. The base case is the "base" of your inductive argument in a sense, because after you show the "if n, then n+1", your base case sets the domino effect in motion.

$\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.