How much Base Proof is required?

Question

If I were looking to use the Theory of Strong Induction, to prove the statement that:

The Set of All Even Numbers is equal to the Set of All Odd Numbers multiplied by $2^n$, where $n \geq 1$

$$ \mathbb{E} = \mathbb{O} \cdot \{2^n \mid n \geq 1 \} $$

How much Base Proof would be required to show or infer that it is true?

1. $2 = 1 \cdot 2^1$
2. $4 = 1 \cdot 2^2$
3. $6 = 3 \cdot 2^1$
4. $8 = 1 \cdot 2^4$
5. $10 = 5 \cdot 2^1 \dots$

I get that for Strong Induction you have to show all the base proofs up to a certain point. But in this case, what would that minimum requirement be? Is there a minimum amount required, or is this what makes a Conjecture? Because the base proof requires an infinite number of base proofs, to prove the statement and relies more on a formula for its proof over Strong Induction?

Answer 1

We wish to prove by strong induction all integers $m\ge1$ are of the form $2^n(2a+1)$ for integers $a,\,n\ge0$. The following statement of the principle of strong induction is sufficient:

Let $P$ denote a predicate of positive integers. If $\forall k<m(P(m))\implies P(m)$, then $\forall m(P(m))$.

There is no base case. Clearly $P(1)$ because $\forall k<1(P(k))$ is vacuously true ($0$ "doesn't exist" from the perspective of quantification over positive integers). Since $P(1)$, $\forall k<2(P(k))$, so $P(2)$, and so on.

The hard part is proving $\forall k<m(P(k))\implies P(m)$. Your proof of that might require considering small values of $m$ especially, but that's up to you to find out for whichever $P$ concerns you.