Prove by induction that $∀n ≥ 3$ : $n^{2} + 1 ≥ 3n$
So I know I need to find my base case, would it be:
$n=3$
Then calculate the RHS and LSH
RHS:$3(3)=9$ LHs: $3^{2} + 1= 10$ we see that the LHS is greater than or equal to the RHS.
Now for the inductive step:
Assume that the formula is true for an arbitrary $∀n ≥ 3$
We now have to prove $n^{2} + 1 ≥ 3n$
This is where I get stuck, how can I prove this?
Edit : showing that the assumption applies to $(n+1)^2+1≥3(n+1)$
Best Answer
We need to prove that under the assumption of the induction hypothesis, $$n^2 + 1 \geq 3n\tag{Inductive Hypothesis}$$ it follows that:
$$(n+1)^2 +1 \geq 3(n+1)$$
$$\begin{align} (n+1)^2 + 1 & = n^2 + 2n + 1 + 1 \\ & = (n^2+ 1) + 1 + 2n \\ &\geq 3n + 2n +1\tag{Use of Inductive hypothesis}\end{align}$$
Now it's up to you to argue that $$3n +2n +1\geq 3(n+1)= 3n + 3\quad \forall n\geq 3$$
To do this, convince yourself that $2n+1 \geq 3$ for all $n\geq 1$, though we only are concerned with $n\geq 3$.