Basic mathematical induction regarding inequalities [duplicate]

These are just the examples from my textbook, but I don't think it did not explain well.

One of the problem was to prove the inequality

$$n<2^n$$

for all integers $n$.

I understand we assume if $P(n)$ is true, $P(k+1)$ is true.

Thus $k+1< 2^{k+1}$

But in the text book, they added one more line that I don't understand:

$$k+1<2^k+1 \le 2^k+2^k=2\cdot2^k=2^{k+1}$$

I understand $$k+1<2^{k+1}$$

But how do I know $2^k+1$ is larger than $k+1$, and smaller than $2^{k+1}$?

I have one another example just in case,

proving $2^n<n!$ using induction.

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

I understand we should start with $2^{k+1}<(k+1)!$, but

Where did $2\cdot k!$ come from? Textbook says it came from inductive hypothesis, but I still don't get it.

Please advise.

Solution 1:

We assume that $$k < 2^k$$ add one to both sides, we get $$k+1 < 2^k + 1$$

But we also know that $2^k + 1 < 2^k + 2^k$ since $1 < 2^k$ for every natural $k$. This means we have $$2^k + 1 < 2^{k+1}$$ which completes our induction.

So, to answer your question, you need to know that $2^k > 1$ for every natural k, so that $2^k + 1 < 2^{k} + 2^{k}$. This technique comes up often in inductions using inequalities.

For your next example, assume $$2^k < k!$$ We have that $$(k+1)! = (k+1)k!$$

But we assumed that $2^k < k!$ so we have $$2\cdot 2^k < (k+1)k!$$ (I'm making the assumption that $n \geq 4$) and hence $$2^{k+1} < (k+1)!$$ completing our induction.

Solution 2:

You need to prove that $P(n) \Rightarrow P(n+1)$. So you take an arbitrary $n$ and suppose P(n) true. This gives you that

$$n < 2^n$$

You add one to each side, and you get

$$n+1<2^n+1$$

Now, you know that $\forall n \in \mathbb{N}, 2^n \geq 1$, hence

$$n+1<2^n+1 \leq 2^n+2^n = 2^{n+1}$$

And this is exactly P(n+1)