Prove by Induction: $n \le 3 \sqrt{n} +4$. How to work with the Square-root?

Question

I want to prove the statement $$n \le 3 \sqrt{n} +4$$

for every $n$ belongs to $N$ by induction.

So what I have done so far is proving for $p(1)$ is true and assuming that $p(n)$ is true. Now, I want to prove that $p(n+1)$ is also true; $$n+1 \le 3 \sqrt{n+1} +4 +1$$

Well basically I add $1$ to both side of the inequation to get $n+1$ on the left hand side, but I am not sure how to work with the square-root. Should I leave the $n$ under the square-root unchanged in this step? and what should I do next?

@AndréNicolas, I just $100$ as an example. Maybe I should erase my answer? — Ivo Terek, Oct 12 '14 at 18:45
It would be easier to work with $\frac{(n-4)^2}{3} \leq \sqrt{n}$ I think. Also, in your statement for $p(n+1)$ you can't just change the value under the square root to $n+1$ when you add 1 to each side. — user141592, Oct 12 '14 at 18:46
Ok. I just didn't wanted you to think that I copied your counter-example - I just thought the same thing (: — Ivo Terek, Oct 12 '14 at 18:48
The number $100$ springs to mind immediately, I would guess more than half of of the people looking at the problem would use it. — André Nicolas, Oct 12 '14 at 18:52

score 5 · Accepted Answer · answered Oct 12 '14 at 18:45

5

It is false. Take $n = 100$. Then: $$100 = n > 3\sqrt{n} + 4 = 34.$$

answered Oct 12 '14 at 18:45

Ivo Terek

77,665

The inequality fails for all $n \ge 17$. – Ben Frankel Oct 12 '14 at 18:50
Is there any formal way to prove if its wrong? my professor won't let it be really easy.... – FarahFai Oct 12 '14 at 18:54
2

Don't worry, showing a counter-example is a "formal" way to prove that the inequality is false. – Ivo Terek Oct 12 '14 at 18:55

score 1 · Answer 2 · answered Oct 12 '14 at 18:55

1

With $x^2=n$ (which is valid for $n\geq 0$), you have $$ n-3\sqrt{n}-4=x^2-3x-4=(x+1)(x-4)\geq 0 $$ whenever $x\geq 4$. So in particular, when $n>16$, your inequality is false.

answered Oct 12 '14 at 18:55

Kim Jong Un

14,794
1
24
49

Prove by Induction: $n \le 3 \sqrt{n} +4$. How to work with the Square-root?

2 Answers2