Let $n$ be a natural number greater than zero: $n \in \Bbb N^+$
The following statements are true:
- $P(20)$
- $P(n) \Leftrightarrow P(2n)\ \ \ for\ n < 20$
- $P(n) \Leftrightarrow P(n-4)\ \ \ for\ n > 20$
How can I prove, that $P(n)$ is true for all $n$ (That is clearly the case)? Especially, is it possible to prove it using mathematical induction?
I can prove it argumentatively, however I'm looking for a formal proof.
Edit: Brief argumentative proof: The statement is true for all multiples of 4 greater than 20, since they are so often reduced by 4 until they are equal to 20. Multiples of 4 less than 20 are so often doubled until they're greater than 20. Of course, those numbers remain multiples of 4.
Numbers that are not multiples of 4 are repeatedly doubled and reduced by 4. At the latest, when they have been doubled twice, they're also multiples of 4, since this is equivalent to a multiplication of four.
It could be proven that for any $m$ such that $4 | m$ if $\forall n > m\colon P(n) = P(n - 4)$; $\forall n < m\colon P(n) = P(2n)$ and $P(m)$ then $\forall n \in \mathbb{N}\colon P(n)$.
If $\ell \le {m \over 2}$ then $P(\ell) = P(2^k \cdot \ell)$ where $k$ is the minimum number such that $2^k \cdot \ell \ge m$. Clearly $4 | 2^k \cdot \ell$. Hence $P(2^k \cdot \ell) = P(2^k \cdot \ell - 4) = \ldots = P(m)$. Therefore $P(\ell)$ is true for all $\ell \le {m \over 2}$. Then $P\left({m \over 2}-1\right) \implies P(m - 2) \implies P(m+2)$.
Thus for all even numbers $k \ge m$, $P(k)$ is true. Let ${m \over 2} < \ell \le m$. $m < 2\ell \le 2m$, $P(\ell) = P(2\ell)$. Since $2\ell$ is an even number $\ge m$, $P(2\ell)$ is true. Hence so is $P(\ell)$.
Therefore we've proved that $P(\ell)$ is true for all $\ell \le m$. Then for arbitrary $n > m$, $P\left(n - \lceil{n-m \over 4}\rceil \cdot 4\right)$ is true hence so is $P(n)$.
Edited, in the original answer, I've only done that for $m=20$.