Question

Prove by mathematical induction that n^2+n < 2^n whenever n is an integer greater

than 4.

Answer 1

$\text{\underline{Inducive base:} We check for $n=5$, then we have the following: } \\ 5^2 + 5 = 30 < 32 = 2^5 \\ \text{which shows that the statement is true for } n=5.\\ \text{\underline{Inducive hypothesis:} we now assume that the statement is true for every $k > 4$ i.e} \\ k^2 + k < 2^k , k<4\\ \text{\underline{Inductive step:}}\\ (k+1)^2+k+1\\ =k^2+k+2k+2 < 2^k+2^k + 2\quad -(*)\\ \text{Note that $2^k= \displaystyle{\sum^k_{r=0}\begin{pmatrix}k\\r \end{pmatrix}}$} \\ \implies 2^{k+1}= 2\cdot\displaystyle{\sum^k_{r=0}\begin{pmatrix}k\\r \end{pmatrix}}\\ \implies \text{for k > 4, }2^k>2n+2\\ \text{From * we have that}\\ (k+1)^2+k+1<2^k+2^k\\ =2\cdot 2^k = 2^{k+1}\\ \text{Hence we have our result}$