Q:Prove By induction $2^{n+1} > n^2$ for all positive integers.
Step 1: Base case: $n=1$, we get $4>2$
Step 2: Induction hypothesis: $n=k, 2^{k+1} > k^2$
Step 3: Induction Step:
to prove: $2^{(k+1)+1} > (k+1)^2$
Left hand side=$2^{k+1}.2$
How to proceed and prove after this step?
To prove $2^{k+2} > (k+1)^2$. Consider the left side \begin{align*} 2^{k+2} & = 2^{k+1} \, . 2\\ & > k^2 \, . 2 && (\text{by induction hypothesis})\\ & = k^2+k^2\\ & > k^2 + (2k+1) && (\text{for all } k \geq 3, k^2>2k+1)\\ & = (k+1)^2. \end{align*} So you need to adjust your base stpes to cover the missing cases from the inequality (namely $k=1,2$).
