Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)

share|improve this question
1  
For $n\in\Bbb N$ let $Q(n)$ be the statement $P(n+n_0)$. –  Brian M. Scott Apr 5 '12 at 1:49
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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? –  russell11 Apr 5 '12 at 2:31
    
@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. –  Brian M. Scott Apr 5 '12 at 2:47
    
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. –  russell11 Apr 5 '12 at 3:13
    
@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. –  Brian M. Scott Apr 5 '12 at 3:25
    
Ah, I get it now. Thanks for all your help. –  russell11 Apr 5 '12 at 3:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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