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
$$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$.
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.
$\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.
