3

I am new to this stack exchange and if I have any wrongdoing please let me know. My question is how to prove the following inequality:

$2^{n+1}>n^2$ assuming $n \in \mathbb{N}$

My thought is to prove this by mathematical induction.

Let $P(n)$ be the proposition $P(1)$ is true as $4 = 2^2 > 1^2 = 1$

Assume $P(k)$ is true for some positive integer $k$ i.e. $2^{k+1}>k^2$

then $2^{(k+1)+1} = 2 \cdot 2^{k+1} > 2 \cdot k^2$ (By induction assumption)

But I get difficulty here. How can I show that $2 \cdot k^2 > (k+1)^2$ such that $P(k+1)$ is true? Thank you for your help.

balddraz
  • 7,558
Raymond Autumn
  • 31

2 Answers2

1

$2^{n+1}>n^2$ is true for $n\in\{1,2,3\}$. Let $n\ge 4$. By Binomial Theorem:

$$2^{n+1}=(1+1)^{n+1}=\binom{n+1}{0}+\binom{n+1}{1}+\cdots +\binom{n+1}{n+1}$$

$$>2\cdot \binom{n+1}{2}=n(n+1)>n^2$$

user236182
  • 13,324
  • Sorry I cannot really know why the sum of binomial coefficient will be larger than 2*(n+1, 2). May you provide some hint to me? Many thanks! – Raymond Autumn Oct 05 '15 at 21:31
  • @RaymondAutumn If $n\ge 4$, then $\binom{n+1}{0}+\binom{n+1}{1}+\cdots +\binom{n+1}{n+1}=\binom{n+1}{2}+\binom{n+1}{n-1}+\text{others};$ and note $\binom{n+1}{n-1}=\binom{n+1}{2}$. – user236182 Oct 05 '15 at 22:09
0

Hint

$$2^{k+2}=2\cdot 2^{k+1}>2 \cdot k^2 \ge (k+1)^2$$ for $k\ge 3.$

mfl
  • 29,399
  • Assume k >=3

    then k > sqrt(2) + 1 <=> (k-1)^2 > 2 <=> k^2 - 2k > 1 <=> k^2 > 1 + 2k <=> 2k^2 > k^2 + 2k +1 <=> 2k^2 > (k+1)^2

    But it sounds strange to start with saying that k > sqrt(2)+1, isn't it?

     – Raymond Autumn Oct 05 '15 at 20:44