Why does the conclusion of induction proofs hold even when the base case is greater than $1$?

Question

The principle of mathematical induction states that if $X\subseteq \mathbb{N}$ satisfying $1\in X$ and if $k\in X$ for all $k<n$, then $n\in X$. Then $X=\mathbb{N}$.

Now, consider the claim: $2^n<n!$ for all $n\geq 4$. This claim can be proved by induction, but the base case is $4$, how does the conclusion follow that $X=\mathbb{N}$? Isn't $1,2,3$ not in $X$?

That is, $X=\{4,5,\dots\}$ but $\mathbb{N}=\{1,2,\dots\}$.

Answer 1

You're correct; suppose you want to prove that $$2^n<n!$$ for all $n\geq 4$. Then, to use induction in the form you have, you need to have:

Let $X$ be the set of natural numbers such that $2^{n+3}<(n+3)!$

rather than just applying it directly. That is, you apply a shift and then use induction. Generally, since $\{1,2,3,\ldots\}$ and $\{4,5,6,\ldots\}$ are "isomorphic" in a sense (i.e. if you only know how elements are related by the successor function, then the sets are related by $n\mapsto n+3$) you can feel okay with moving around the base case (but you don't get lower elements by proving it for higher elements, of course - $X$ does not contain $-2$, $-1$ or $0$ as I've defined it).

You could, in fact, prove the statement:

Let $X\subseteq \mathbb N$. If $n\in X$ and $k\in X$ implies $k+1\in X$, then $\{n'\in \mathbb N : n'\geq n\}\subseteq X$.

which is a slightly different form from what you have (but equivalent for $n=1$).