is this true for an induction proof

Question

If I prove $P(0),$ "for all $n: P(n) \Rightarrow P(n+2)$", and "for all $n: P(n) \Rightarrow P(n+3)$", it still may not be true that $P(n)$ is true for all naturals $n.$

If so how can we be sure about $n+1.$

Answer 1

If you prove $P(0)$ and $\forall n(P(n)\to P(n+2))$ then you have proven $P$ is true of any even natural number. (Since we have $P(0)$ and $P(0)\to P(2),$ and thus $P(2),$ and we have $P(2)\to P(4)$ and thus $P(4)$ and so on.)

Similarly, if you prove $P(0)$ and $\forall n(P(n)\to P(n+3))$ then you have proven $P$ is true of any natural number that is a multiple of $3.$

Generalizing, if you prove $P(0)$ and $\forall n(P(n)\to P(n+k))$ then you have proven that $P$ is true of every multiple of $k.$

When you do so for $k=1,$ you show it for every multiple of $1,$ i.e. every natural number.

Answer 2

Yes that is true. You must always have some overlap with the base case in an induction proof. In this case you do not. If you just prove $P(0)$ is true, then that doesn't necessarily mean $P(1)$ is true. In other words, it is possible that no $P(k)$ is true for $k>0.$

Answer 3

Your question is not entirely clear, but it appears you are asking about step sizes other than $1$. Note that this is mathematically correct, but by doing so, you've not actually proven the proposition for all natural numbers.

Sometimes that's fine. Suppose you wanted to prove something only for even non-negative numbers. In this case, showing $P(0)$ in addition to $P(n) \rightarrow P(n+2)$ would be sufficient to establish the result.

Now let's say you need to prove a result for all natural numbers, but for some reason, establishing $P(n) \rightarrow P(n+2)$ is significantly easier or more obvious than showing $P(n) \rightarrow P(n+1)$. In this case, using a different step size is fine as long as you establish more base cases. For example with a step size of $2$, you need to establish both $P(1)$ and $P(2)$ (along with $P(n) \rightarrow P(n+2)$) to show $P(n)$ holds for all natural numbers. This is because $P(1) \rightarrow P(3) \rightarrow P(5) \rightarrow... P(2k+1) \rightarrow... $

while

$P(2) \rightarrow P(4) \rightarrow P(6) \rightarrow... P(2k) \rightarrow... $ so there are two inductive chains for odd and even separately, which together cover all the natural numbers. You can do the same for other step sizes, as long as you establish the requisite number of base cases.

Answer 4

If you consider $P(n)$ to be the statement "$n$ can be written as a sum $n=2a+3b$ for two non-negative integers $a,b$", then you can prove $P(0)$, "for all $n: P(n) \implies P(n+2)$", "for all $n: P(n) \implies P(n+3)$", but you cannot prove "for all $n: P(n) \implies P(n+1)$".

To be specific, $P(1)$ is not true, while $P(n)$ is true for all other positive integers $n$.