is this true for an induction proof

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.


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


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

Tags:

Induction

Proof Writing

Solution Verification

Related

Why do we need the local triviality condition when working with vector bundles? Prove $\lim_{x\to 0} f(x)$ exists $\implies\lim_{x\to 0} f(x^2)$ exists Improper integral of $\int_0^\infty \frac{dx}{(x^2+{\pi}^2)\cosh(x)}$ Function defined everywhere but continuous nowhere How do I solve this integral via integration by parts when it shows a recursion-like behavior? Prove/disprove: $ I_1 \cong I_2 \iff R/I_1 \cong R/I_2 $ On the Equivalent Norms for Subspaces Prove that $\varphi$ is continuous on the real numbers and $\varphi(x) = x$ $\mathbb{Q}(\sqrt{p+\sqrt{p}})$ is Galois over $\mathbb{Q} \iff p=n^2+1$ for a prime $p$. Is $\mathbb{Q} \times \mathbb{Q} \cup \mathbb{I} \times \mathbb{I}$ disconnected? If something is true, can you necessarily prove it's true? If the fiber and the base are Kähler manifolds is the total space also Kähler?

Recent Posts