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

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

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

  • $\begingroup$ 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$? $\endgroup$
    – Csci319
    Mar 4 '15 at 17:46
  • $\begingroup$ 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$. $\endgroup$
    – amWhy
    Mar 4 '15 at 17:48
  • $\begingroup$ 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$? $\endgroup$
    – Csci319
    Mar 4 '15 at 18:23
  • 1
    $\begingroup$ Thanks, @user73985, for fixing my typo!! $\endgroup$
    – amWhy
    Mar 5 '15 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.