# Not understanding the logic behind $2<k+1$ in Induction Proof Problem

$$2^k+1 = 2 · 2^k$$

$$< 2 · k!$$

$$< (k + 1)k!$$ (because $$2 < k + 1$$)

$$= (k + 1)!$$ (by definition of factorial function.)

I am not getting the third line. where did this $$2 < k + 1$$ appear.

This is from the book Discrete Mathematics and Its Application by Kenneth H Rosen chapter 5.1 Mathematical Induction (7th ed) Example 6.

Full Problem and it's Solution given below:

Use mathematical induction to prove that $$2^n < n!$$ for every integer $$n$$ with $$n ≥ 4$$. (Note that this inequality is false for $$n = 1, 2, and$$ $$3$$.)

Solution: Let $$P(n)$$ be the proposition that $$2^n < n!$$.
BASIS STEP: To prove the inequality for $$n ≥ 4$$ requires that the basis step be $$P (4)$$. Note that $$P (4)$$ is true, because $$2^4 = 16 < 24 = 4!$$

INDUCTIVE STEP: For the inductive step, we assume that $$P (k)$$ is true for an arbitrary integer $$k$$ with $$k ≥ 4$$. That is, we assume that $$2^k < k!$$ for the positive integer $$k$$ with $$k ≥ 4$$. We must show that under this hypothesis, $$P (k + 1)$$ is also true. That is, we must show that if $$2^k < k!$$ for an arbitrary positive integer $$k$$ where $$k ≥ 4$$, then $$2^k+1 < (k + 1)!$$. We have
$$2^k+1 = 2 · 2^k$$ (by definition of exponent)
$$< 2 · k!$$ (by the inductive hypothesis)
$$< (k + 1)k!$$ (because $$2 < k + 1$$)
$$= (k + 1)!$$ (by definition of factorial function.)
This shows that $$P (k + 1)$$ is true when $$P (k)$$ is true. This completes the inductive step of the proof. We have completed the basis step and the inductive step. Hence, by mathematical induction $$P (n)$$ is true for all integers $$n$$ with $$n ≥ 4$$. That is, we have proved that $$2^n < n!$$ is true for all integers $$n$$ with $$n ≥ 4$$.

• hi sdam1n. It is good that you have shown your work; that is important, and will be noticed here. But you should also use our standard typesetting system, MathJax. I paste the link for you below. Without MathJax, I don't much want to carefully study what you've written. math.meta.stackexchange.com/a/10164/688046 Commented May 10, 2021 at 18:51
• also, please replace the title of your question. It gives almost no idea of your question. Commented May 10, 2021 at 18:52
• Thanks! I am looking into it. Commented May 10, 2021 at 18:54
• I don't understand what do you want to prove exactly? @sdam1n
– PNT
Commented May 10, 2021 at 19:02
• @311411 I have done what i can. Commented May 10, 2021 at 19:15

You want to show by induction that $$2^n < n!$$ for $$n\geq 4$$. Induction consists of two parts: The start and the induction step.
We start with the inductions start where we just verify that the statement is true for the lowest $$n$$ possible, here we have $$n=4: 2^4 = 16 < 4! = 24$$. That is indeed correct.
Now we prove the induction step. To not confuse the notation another variable $$k$$ is used. We assume that the above statement is correct for some arbitrary $$k\geq 4$$. We want to show that - given this condition - the statement is true for $$k+1$$ as well. So our goal is to show that $$2^{k+1}< (k+1)!$$
After some simplification we get to the point you mentioned: $$2\cdot k! < (k+1)\cdot k!$$
The inequality $$2 simply comes from the property of the arbitrary chosen $$k$$ which is already greater or equal to $$4$$. So $$k+1\geq 5 > 2$$ and the proof is completed.