2
$\begingroup$

I am trying to prove the following example, however I seem to be getting a little stuck:

For $n\in\mathbb N$, $n\ge 4, n^2>3n$

What I have Done: Base Case:$ n=4$, LHS: $4^2 = 16$, RHS: $3\cdot 4 = 12$

$16\gt 12$, so True

Assume true for $n=k$, $k^2 > 3k$

Should be true for $n=k+1$

$(k+1)^2 \gt 3(k+1)$

This is where I am stuck!

Any help would be appreciated!

$\endgroup$
1
$\begingroup$

Paul's answer is perfectly fine, but it seems you may still be struggling with how exactly he coaxed out the inequality you are looking for by using the induction hypothesis. I'll try to expand on this--let me know if a step(s) doesn't make sense.


First, for $n\geq 4$, let $S(n)$ denote the statement $$ S(n) : n^2 > 3n. $$ You already took care of the base case. Thus, fix some $k\geq 4$ and assume that $S(k)$ is true where $$ S(k) : \color{blue}{k^2 > 3k}. $$ To be shown is that $S(k+1)$ follows where $$ S(k+1) : \color{purple}{(k+1)^2 > 3(k+1)}. $$ Starting with the left-hand side of $S(k+1)$, \begin{align} \color{purple}{(k+1)^2} &= \color{blue}{k^2}+2k+1\tag{expand}\\[0.5em] & \,\color{blue}{>3k}+2k+1\tag{by $S(k)$, the ind. hyp.}\\[0.5em] &> 3k+3\tag{since $k\geq 4$}\\[0.5em] & \,\,\color{purple}{>3(k+1)},\tag{factor out $3$} \end{align} we end up at the right-hand side of $S(k+1)$, completing the inductive step.

Thus, by mathematical induction, the statement $S(n)$ is true for all $n\geq 4$. $\blacksquare$

$\endgroup$
  • $\begingroup$ Can I just ask how you got from line 2, to line 3? from "3k+2k+1" to 3k +3 $\endgroup$ – RandomMath Apr 19 '15 at 21:11
  • $\begingroup$ @RandomMath Sure. It's really because $k\geq 4$: $$ 3k+2k+1 > 3k+3\Longleftrightarrow 2k+1>3\Longleftrightarrow 2k>2. $$ Surely, $2k>2$ when $k\geq 4$. Wouldn't you agree? $\endgroup$ – Daniel W. Farlow Apr 19 '15 at 21:14
  • $\begingroup$ Oh I see! That makes sense now! I'll take a look at more examples to get my head around these specific types of proofs! Thanks $\endgroup$ – RandomMath Apr 19 '15 at 21:24
  • $\begingroup$ @RandomMath Not to promote my own answers...but you may find this list to be beneficial. I've answered a number of induction problems, and I generally try to strive for clarity. You may find some of my answers in that list to be of some use. Good luck! $\endgroup$ – Daniel W. Farlow Apr 19 '15 at 21:26
2
$\begingroup$

$(k+1)^2=k^2+2k+1>3k+2k+1>3k+3=3(k+1)$

$\endgroup$
  • $\begingroup$ The way I thought about it is like this: By using the assumption: k^2>3k, if you add 1 to both sides you get: k^2 +1 > 3k + 1: which implies (k+1)^2 > 3k+1, since 3k+1<3k+3, therefore the statement is true - Would this be the right way of going about it? $\endgroup$ – RandomMath Apr 19 '15 at 9:54

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.