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.