I was asked to prove the Principle of Cauchy Induction

Question

Question: Carefully prove the Principle of Cauchy Induction: Suppose $P(n)$ is a property that a natural number $n$ may or may not have. Suppose that

• $P(2)$ holds,
• For every $n ≥ 2$, if $P(n)$ holds, then $P(2n)$ holds, and
• For every $n ≥ 3$, if $P(n)$ holds, then $P(n − 1)$ holds.

Then $P(n)$ holds for every natural number $n ≥ 2$.

Answer 1

Proof would be done by standard induction with help of a)b)c) then i think.

Since $P(2)$ holds according to a) first step of standard Induction argument is already given.

By b) we can deduce then from $P(2)$ that $P(4)$ also holds.

From P(4) we conclude by applying c) that P(3) holds.

Last step would be to derive the standard induction step $P(n)\Rightarrow P(n+1)$.

Suppose for $n\geq 3\ $ $P(n)$ holds ,then $P(2n)$ holds according to b).

Hence by succesivly applying c) ($P(k)\Rightarrow P(k-1)$) starting with $k=2n$ after finite number of $n-1$ steps we arrive at $n+1$ and conclude that $P(n+1)$ holds

Answer 2

Suppose it is not true.

A smallest integer $m\geq2$ must exist with $\neg P(m)$ and it easy to prove on base of (a), (b), (c) that $m\geq4$.

Then also $\neg P(m+1)$ and one of $m$ and $m+1$ is even and can be written as $2k$ where $k$ is an integer that satisfies $2\leq k<m$.

Then also $\neg P(k)$ but this contradicts the minimality of $m$.

Answer 3

There is this general induction principle:

Theorem (Well-founded Induction): Let $X$ be a set and $R \subseteq X \times X$ a binary wellfounded relation. Then for a predicate $P\colon X \to \text{bool}$ if we have $$\forall x. (\forall y. y\ R\ x \Rightarrow P(y)) \Rightarrow P(x)$$ then we have $\forall x. P(x)$.

---

Definition (Well-founded Relation) A relation is called wellfounded if there are no infinite descending chains, i.e. there are no $x_1, x_2, \ldots$ such that $x_{n+1}\ R\ x_n$ for all $n$.

---

Example: Let $X = \mathbb{N}$ and $R$ be the relation such that $\forall n. n\ R\ (n+1)$. You may verify (informally on paper) that this relation is well-founded. Then the inner formula in the main assumption, namely $$\forall y. y\ R\ x \Rightarrow P(y)$$ is vacuous for $x = 0$ (you have to show $P(0)$ in the surrounding formula in an ad-hoc way) and becomes $P(x-1)$ for all $x \geq 1$. Overall, we get $$P(0) \wedge \forall x \in \mathbb{N}_{\geq 1}. P(x-1) \Rightarrow P(x)$$ This is the usual induction principle on natural numbers.

If you trust this principle, it is easy to prove your theorem: Set $X = \mathbb{N}_{\geq 2}$ and $R$ as follows:

1. $\forall n. n\ R\ 2n$
2. $\forall n. (2n + 2)\ R\ (2n + 1)$

The first bullet point relates every number to its doubled number. The second relates every even number to the number one smaller. E.g. we have $2\ R\ 4, 4\ R\ 6, \ldots$ and $2\ R \ 1, 4\ R\ 3, \ldots$. This relation is well-founded because descending chains look as follows: we can hop down even numbers by the first bullet point or we can hop from an odd number one up to an even number and then down even numbers.

Now we indeed fulfill the main assumption from the theorem: $$\forall x. (\forall y. y\ R\ x \Rightarrow P(y)) \Rightarrow P(x)$$ Namely, for even $x$ by your second assumption from the original post. And for odd $x$ by your third assumption from the original post. Hence, the theorem's assumptions are fulfilled and we can conclude $\forall x. P(x)$.

Answer 4

By standard induction you can prove that $P(2^k)$ holds for any $k$.

Base case: Holds for $P(2)$ and inductive case: If $P(2^k)$ holds so does $P(2^k)$.

For every natural number $m\ge 3$ there is a natural $k$ so that $2^k \le m < 2^{k+1}$ and $k \ge 2$.

As it holds for $2^{k+1}$ and $2^{k+1}> 3$ then it holds for $2^{k+1}-1$ and inductively of $2^{k+1} -(2^k - m)$

If that last line is breezy consider.

Let $Q_k(m)$ be the statement "$P(2^{k+1}-m)$ if $2^{k+1}-m)\ge 3".

Base case: If $m=0$ then $P(2^{k+1})$ is true as we proved above so $Q_k(0)$ is true.

Base case: If $Q_k(m)$ is true then $P(2^{k+1}-m)$ is true and $P(2^{k+1}-m-1)= Q_k(m+1)$ is true.

And that's it. It is true for all $n=2^k$ and $n=2^{k+1}$ and all $n: 2^k \le n \le 2^{k+1}$. So it is true for all natural $n \ge 2$.