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?

  • $\begingroup$ Your inequality derection is wrong! The inequality holds in the opposite direction for every $n \geq 4$. $\endgroup$ Sep 30 '17 at 17:31
  • $\begingroup$ You are right, but the practice problem asks for what I wrote. $\endgroup$
    – onoma
    Sep 30 '17 at 17:37
  • $\begingroup$ If you agree with me; why do you try to prove a false statement? $\endgroup$ Sep 30 '17 at 17:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – onoma
    Sep 30 '17 at 17:45
  • $\begingroup$ 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$ $\endgroup$
    – 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.$


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.