Show by induction that $(n^2) + 1 < 2^n$ for intergers $n > 4$

Question

So I know it's true for $n = 5$ and assumed true for some $n = k$ where $k$ is an interger greater than or equal to $5$.

for $n = k + 1$ I get into a bit of a kerfuffle.

I get down to $(k+1)^2 + 1 < 2^k + 2^k$ or equivalently:

$(k + 1)^2 + 1 < 2^k * 2$.

A bit stuck at how to proceed at this point

Answer 1

$$2^{k+1}=2\left(2^k\right)>2(k^2+1)=2k^2+2=k^2+k^2+2\overset{(*)}>k^2+2k+2=(k^2+1)+1$$ So, it remains to show that $k^2>2k$ for $k>4$. But $$k^2-2k=k(k-2)>0$$ for all $k>2$.

Answer 2

First, show that this is true for $n=5$:

$5^2+1<2^5$

Second, assume that this is true for $n$:

$n^2+1<2^n$

Third, prove that this is true for $n+1$:

$(n+1)^2+1=$

$n^2+\color\green{2}\cdot{n}+1+1<$

$n^2+\color\green{n}\cdot{n}+1+1=$

$n^2+n^2+1+1=$

$2\cdot(\color\red{n^2+1})<$

$2\cdot(\color\red{2^n})=$

$2^{n+1}$

---

Please note that the assumption is used only in the part marked red.

Answer 3

$\displaystyle 2^n = (1+1)^n > \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\binom{n}{3}>n^2+1 $ iff $n>5$. (*)

The case $n=5$ is proved by inspection.

(*) This seems to be a cubic inequality but it reduces to an easy quadratic.