I attempted a proof of mathematical induction using an arbitrary base case, but was unsuccessful (and hence this question). Below is what I was trying to do and along with my thinking; if anyone can point me in the right direction I'd appreciate it.

The induction I am using: Let $P$ be a property about the natural numbers $\mathbb{N}$ with $0\in\mathbb{N}$, and let $P(n)$ denote the statement that the property $P$ holds for $n\in\mathbb{N}$. Suppose $P(0)$. Furthermore suppose that for each natural number $k$, $P(k)$ implies $P(k+1)$. Then $\forall nP(n)$.

What I am trying to prove: Let $P$ be a property about the natural numbers $\mathbb{N}$ with $0\in\mathbb{N}$, and let $P(n)$ denote the statement that the property $P$ holds for $n\in\mathbb{N}$. Suppose for $n_0\in\mathbb{N}$, $P(n_0)$. Furthermore suppose that for each natural number $k\geq n_0$, $P(k)$ implies $P(k+1)$. Then $\forall n\geq n_0 P(n)$.

My attempted proof: define $Q(n)$ to be $n\geq n_0 \to P(n)$. Then we wish to prove $\forall nQ(n)$. We induct on $n$.

Base case (for ordinary induction): $Q(0)$ is $0\geq n_0\to P(0)$. Since $n_0\in\mathbb{N}$, $0\geq n_0$ implies that $n_0=0$. Since $P(n_0)$, $P(0)$, which proves the base case.

Inductive step: we want to show $\forall n(Q(n)\to Q(n+1))$. To do this, we assume $k\geq n_0 \to P(k)$ and try to show $k+1\geq n_0 \to P(k+1)$.

Since $k\geq n_0 \to P(k)$, we first prove the case where $k\geq n_0$ and $P(k)$. By the hypothesis of the proof, we see that $P(k+1)$, which proves the case for $k+1$.

This is where I am having trouble: For $k<n_0$, I am unable to show the implication for $k+1$.

So my questions would be: (1) is the overall approach for the proof correct? (2) If so, how might I go on to prove the case when $k<n_0$?

Thanks in advance. (This is not homework, by the way.)

  • 1
    $\begingroup$ For $n\in\Bbb N$ let $Q(n)$ be the statement $P(n+n_0)$. $\endgroup$ Commented Apr 5, 2012 at 1:49

2 Answers 2


No, you’re off on the wrong track even with the base case. If $n_0>0$, $Q(0)$ is true not because $n_0=0$, but because $0\not\ge n_0$, and the implication $0\ge n_0\to P(0)$ is vacuously true. A much better idea is to let $Q(n)$ be the statement $P(n+n_0)$ for each $n\in\Bbb N$ and prove $\forall n Q(n)$. I’ll leave it at that for now to give you a chance to finish it off on your own.

Added: A version of your argument can be made to work, but it’s easier if you replace your $Q(n)$ by the logically equivalent $Q'(n)$: $n<n_0\lor P(n)$.

  • Base Case: $Q'(0)$ says that $0<n_0\lor P(0)$. If $n_0>0$, this is certainly true. If $n_0=0$, then $P(0)$ is $P(n_0)$, which is true by hypothesis, so in this case $Q'(0)$ is again true. There are no other possibilites.

  • Induction Step: Assume $Q'(k)$ for some $k\ge 0$. We want to show $Q'(k+1)$, i.e., that $(k+1<n_0)\lor P(k+1)$. If $k+1<n_0$ there is nothing to prove: $Q'(k+1)$ is certainly true. Assume, then, that $k+1\ge n_0$. There are two possibilities: $k+1=n_0$, and $k+1>n_0$. If $k+1=n_0$, then $P(k+1)$ is $P(n_0)$, which is true by hypothesis, so $Q'(k+1)$ is true in this case. (Note that up to here the argument is very similar to that of the base case.) Otherwise, $k+1>n_0$, and therefore $k\ge n_0$. Now we finally use the induction hypothesis $Q'(k)$, which says that $k<n_0\lor P(k)$. Since in this case we have $k\ge n_0$, the disjunct $k<n_0$ is false, and therefore $P(k)$ must be true. By hypothesis $P(k)\to P(k+1)$, so $P(k+1)$ is true, and therefore $Q'(k+1)$ is true. This completes the induction step.

We can now conclude that $\forall n Q'(n)$, i.e., $\forall n \Big(n<n_0\lor P(n)\Big)$, which clearly implies that $\forall n\ge n_0 \big(P(n)\big)$, as desired.

  • $\begingroup$ Thanks. Following your suggestion, I managed to prove $\forall nP(n+n_0)$ by inducting on $n$, but I am unsure how to get to $\forall n (n\geq n_0 \to P(n))$ from there. Also I don't think I assumed $n_0 > 0$ so I don't understand your objection. Assuming $0\geq n_0$, the only possibility is for $n_0$ to be $0$. ...Or am I completely misunderstanding something? $\endgroup$
    – russell11
    Commented Apr 5, 2012 at 2:31
  • $\begingroup$ @russell: Substitute $m=n+n_0$ in $\forall nP(n+n_0)$: $m\ge n_0$ iff $n\ge 0$, so you have $\forall m\ge n_0 P(m)$, which is what you were really trying to prove. It’s quite true that in the base case you didn’t assume that $n_0>0$; you implicitly assumed that $n_0=0$ when you assumed that $0\ge n_0$, and since $n_0$ can be greater than $0$, this is illegitimate. $\endgroup$ Commented Apr 5, 2012 at 2:47
  • $\begingroup$ Thanks, I get the proof now. However for my original $Q(0)$, i.e., $0\geq n_0 \to P(0)$, I still do not see the error in my reasoning. When proving $p\to q$, doesn't it suffice to assume $p$ and derive $q$? To me (if I am understanding this) it seems like you are saying we need to explicitly say "suppose $\neg p$; then the implication is vacuous", which seems unnecessary. $\endgroup$
    – russell11
    Commented Apr 5, 2012 at 3:13
  • $\begingroup$ @russell: The problem is that $n_0$ is fixed ahead of time. The statement to be proved in the base case is $0\ge n_0\to P(0)$; you have to show that this is true without making any assumptions about $n_0$, so your argument has to have two cases. (1) If $n_0>0$, the implication is vacuously true. (2) If $n_0=0$, then by hypothesis $P(0)$ is true. A version of your argument actually can be made to work; I’ll add something on that to my answer in a few minutes. $\endgroup$ Commented Apr 5, 2012 at 3:25
  • $\begingroup$ Ah, I get it now. Thanks for all your help. $\endgroup$
    – russell11
    Commented Apr 5, 2012 at 3:28

Recall that the standard Induction Principle can be equivalently stated using sets instead of properties (a straightforward consequence of the Axiom Schema of Comprehension):

Let $X$ be a subset of $\mathbb{N}$ such that

  1. $0\in X$.
  2. If $n\in X$, then $n+1\in X$.

Then $X=\mathbb{N}$.

We will apply this as follows:

If $k=0$ this is the standard Induction Principle and there is nothing to prove.

If $k>0$, there is a unique $k'\in\mathbb{N}$ such that $k=k'+1$. Consider the sets $$A=\{n\in\mathbb{N}:n\leq k'\}\;\text{ and }\;B=\{n\in\mathbb{N}:n\geq k\;\text{ and }\;P(n)\}.$$ Clearly, $A\cup B\subseteq\mathbb{N}$, and that $A\cap B=\emptyset$. Moreover,

  1. $0\in A$.
  2. If $n\in A$, either $n<k'$ or $n=k'$. The former case implies $n+1\leq k'$, so $n+1\in A$. The latter case implies $n+1=k$. But the base case $P(k)$ of the hypothesis holds, so $k\in B$. That is, $n+1\in B$. If $n\in B$ then $n\geq k$ and $P(n)$. But the induction hypothesis tells us that $P(n+1)$ holds, so $n+1\in B$.

Then $A\cup B = \mathbb{N}$.

Then we can conclude that $B = \mathbb{N}-A$, i.e., $P(n)$ holds for all $n\geq k$, as desired.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .