# prove inequality by induction — Discrete math

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)$

• You need to show that the assumption implies that $(n+1)^2+1 \geq 3(n+1)$ – Namaste Mar 4 '15 at 17:35
• If $n\geq 3$, then $n^2\geq 3n$ so in particular $n^2+1>3n$. – Kim Jong Un Mar 4 '15 at 17:59

## 1 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$.

• Thanks, I am confused how you got $3n+2n$ because the original LHS is $n^2+1$ then wouldn't it be $(n^2+1)+1$? – Csci319 Mar 4 '15 at 17:46
• We are making use of the assumption that $n^2 + 1\geq 3n$. Remember, we can use the assumption to prove that the assumption implies the case for $n+1$. – Namaste Mar 4 '15 at 17:48
• oh Ok so whenever we make an assumption is will always be $n+1$, that makes things a little clear now. so we now have $(n^2+1)+1$ which equals $n^2+2n+2$ and on the RHS we have $3n+3$ so now the inequality is $n^2+2n+2 ≥ 3n+3$? – Csci319 Mar 4 '15 at 18:23
• Thanks, @user73985, for fixing my typo!! – Namaste Mar 5 '15 at 13:36