3
$\begingroup$

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

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

1 Answer 1

5
$\begingroup$

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

$\endgroup$
4
  • $\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
    Commented Mar 4, 2015 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
    Commented Mar 4, 2015 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
    Commented Mar 4, 2015 at 18:23
  • 1
    $\begingroup$ Thanks, @user73985, for fixing my typo!! $\endgroup$
    – amWhy
    Commented Mar 5, 2015 at 13:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .