Induction with Base Case Not 1

Sometimes in proving induction, the statements $P(n)$ does not always hold true at $n = 1$, but starts to be true at some value instead, let's say $n_{0} \in \mathbb{N}$.

Let's think about this as a domino again. If the $1^{\text{st}}$ one doesn't fall, take the $(n_{0})^{\text{th}}$ as a starting point. Next, we have to prove that for every positive integer $k \geq n_{0}$, if the $k^{\text{th}}$ falls, the $(k+1)^{\text{th}}$ also falls. If we can prove it, we can conclude that $P(n)$ always holds true for every positive integer $n \geq n_{0}$.

Generalized induction:

Let $n_{0} \in \mathbb{N}$, and we are given the following:

1. $P(n_{0})$ is true.
2. $\forall k \in \mathbb{Z}$ and $k \geq n_{0}$, if $P(k)$ is true, $P(k+1)$ is always true.

Then we can say that $P(n)$ is true for all $n \geq n_{0}$. $_\square$

Now we see that if we want to prove $P(n)$ to be true, we need to prove those 2 statements, which is similar to proving by normal induction.

Now let's try an example.

Prove that $2^{n} < n!$ for every positive integer $n \geq 4$.

---

Let $P(n)$ be the statement "$2^{n} < n!$".

We see that the statement is not true for $n=1,2,3,$ so we start with $n=4$ instead. Clearly, $2^{4} = 16 < 24 = 4!$. Now we try to prove the induction step.

Let $P(k): 2^{k} < k!$ be true for $k \geq 4$, then we need to prove $P(k+1): 2^{k+1} < (k+1)!$ to be true.

Since $2^{k} < k!$ is true by assumption, we get $2^{k}\times 2 < k! \times 2$ is true. Again, since $k \geq 4 ,$ we get $k+1 > 2.$ Hence, we have

$2^{k}\times 2=2^{k+1} < k! \times 2 < k!(k+1)=(k+1)!.$

Therefore, $2^{k+1} < (k+1)!,$ which means $P(k+1)$ is true for every $k \geq 4$ if $P(k)$ is true.

Thus by induction, we get $P(n)$ is true for every $n \geq 4$. $_\square$

Everything is the same as proving induction, just the base case is not equal to 1. Let's try the exercise!

1. Prove that $n^{2} > 2n + 1$ for all positive integer $n \geq 3$.

2. Prove that $n^{n} > n!$ for all positive integer $n \geq 2$.

3. Challenge for advanced: Prove that $\sqrt[n]{n!} \geq \sqrt{n}$ for all positive integers $n \geq 2$.

Hint: Claim that $\displaystyle \dbinom{n}{r}\times \frac{1}{n^{r}} \leq 1$ and try to make it as binomial expansion.