Proving mathematical induction with arbitrary base using (weak) induction

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

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

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

Answer

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

• 
  

  Base Case: $Q'(0)$ says that $00$, 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+1n_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
  

We can now conclude that $\forall n Q'(n)$, i.e., $\forall n \Big(n