# Disprove inequality by induction

EDIT: This is the explicit text of the practice problem:

Find out, by induction, whether for $n \geqslant 1$, it is true that $n^2 - 3n - 1 \leqslant 0$.

———

I am learning to use induction. I am asked to prove by induction whether the property $n^2 - 3n - 1 < 0$ holds for all $n\geqslant 1$.

This is obviously false, but I am finding it hard to prove by induction. I am not sure what I am allowed to do.

Base case: P(1) = -3 < 0.

Inductive step: Assuming the property is true for $n$, prove that it is also true for $n+1$.

$(n+1)^2 - 3(n+1) - 1 < 0$.

$n^2+ 2n + 1 -3n -3 - 1 < 0$

$n^2 -3n - 1 < -2n + 2$

Since, by inductive hypothesis, $n^2 -3n - 1 < 0$, then $0 \leqslant -2n+2$. (Is it ok to state it like this?)

Can I just plug a 2 in the inequality and end the proof there? Or do I have to disprove $-2n+2 \geqslant 0$?

I did not know what to do, so I started a new proof by induction. I tried to disprove that $-2n + 2 \geqslant 0$ for all $n \geqslant 1$.

Base case: $P(1) = 0 \geqslant 0$

Inductive step: Assuming the property is true for some $n$, prove that is is also true for $n+1$.

$-2(n+1) + 2 \geqslant 0$

$-2n -2 + 2 = -2n < 0$ (for all positive integers)

Is there a more straightforward way to disprove the first property? Even if there is, would it be correct to do it the way I did?

• Your inequality derection is wrong! The inequality holds in the opposite direction for every $n \geq 4$. – Davood Khajehpour Sep 30 '17 at 17:31
• You are right, but the practice problem asks for what I wrote. – onoma Sep 30 '17 at 17:37
• If you agree with me; why do you try to prove a false statement? – Davood Khajehpour Sep 30 '17 at 17:42
• I thought the practice problem was asking me to disprove by induction (that is why I wrote "Disprove" in the title of the question). But from your responses, I am understanding that it is not possible to disprove by induction? I thought that if I found a contradiction in the induction process, that would be a valid disproof. – onoma Sep 30 '17 at 17:45
• One can disprove the statement "for all $n\geq 1$ one has $n^2-3n-1<0$" by finding an example of an $n$ which satisfies the hypothesis but not the conclusion, i.e. finding an $n\geq 1$ where $n^2-3n-1$ is not negative. This is called "disproof by counterexample." All you need is one such $n$, for example $n=10$ (nothing special about $10$ apart from that it is easy to do arithmetic with and is easy to see works) we have $n^2-3n-1=100-30-1=69\not\lt 0$ – JMoravitz Sep 30 '17 at 17:48

you can not prove this by induction, since your inequality is wrong, plug in for example $$n=4$$ this gives $$16-12-1=3>0$$

Excercise: For every $n\geq 4$ show that : $$n^2-3n-1 > 0.$$

Base: $4^2-3 \times 4 -1 = 3 > 0 . \quad \checkmark$

Suppose that the statment holds for $k=n$:

$$n^2-3n-1 > 0;$$ on the otherhand we know that:

$$(2n+1)-3=2n-2 \geq 2 \times 4 -2 =6 > 0;$$ adding both sides togetter we get :

$$\big(n^2+2n+1\big)-\big(3n-3\big)-1 > 0+0 \ \Longrightarrow \ (n+1)^2-3(n+1)-1 > 0;$$

So we have showed the statement for $k=n+1.$