So I've recently started a new chapter in my discrete mathematics course on proof methods. I have come across this problem in my textbook but I'm having a very hard time understanding where to start and what to look for. In all honesty, all the proofs for the theorems look correct to me.

Each of the following theorems is either valid or invalid, but the proof given is incorrect even if the theorem is valid. Explain briefly what mistake was made in each case:

  1. Theorem: Let $f$, $g$ and $h$ be three functions from $\mathbf{N}$ into $\mathbf{R}^+$. If $f \in O(g)$ and $g \in O(h)$, then $f \in O(h)$.

    Proof: Consider three unspecified functions $f$, $g$ and $h$ $\mathbf{N}$ into $\mathbf{R}^+$. Assume that $f \in O(g)$ and $g \in O(h)$. Since $f \in O(g)$, there is a real number $c$ and a positive integer $n_0$ such that for every $n \ge n_0$, $f(n) \le cg(n)$. Similarly, for every $n \ge n_0$, $g(n) \le ch(n)$. Therefore, for every $n \ge n_0$, $f(n) \le cg(n) \le c(ch(n)) = c^2 h(n)$. Hence $f \in O(h)$ using the constants $c^2$ and $n_0$.

  2. Theorem: If $n^2 + n - 6 \ge 0$, then $n \ge 2$.

    Proof: When $n \ge 2$, we know that $n^2 \ge 4$, so $n^2 + n \ge 6$, and therefore $n^2 + n - 6 \ge 0$.

  3. Theorem: No matter how we choose an integer $n$, the value $n^3 + n$ will be even.

    Proof: We use a proof by contradiction. Assume that the theorem is false. That is, $n^3 + n$ is odd. This is not true, as we can see by choosing $n = 2$ ($2^3 + 2 = 10$, which is even). So we have found a contradiction, which means the theorem is true.

Any help would be greatly appreciated. Thank you!

  • $\begingroup$ What is $O(g)$? $\endgroup$ – Robert Shore Mar 21 '19 at 18:41
  • 1
    $\begingroup$ For Theorem 2, check out what happens when $n = -100.$ You'll see (I think) that this is a counterexample to the theorem. What happens when you apply the supposed proof to this counterexample? Does that help you see why it's not actually a proof? $\endgroup$ – Robert Shore Mar 21 '19 at 18:44
  • $\begingroup$ For the second theorem, you're only proving that every $n\geq 2$ satisfies $n^2+n-6\geq 0$ but not in the other direction... $\endgroup$ – Dr. Mathva Mar 21 '19 at 18:46
  • $\begingroup$ For the third theorem, the assumption to be disproved should be $n^3+n$ isn't always even instead of '$n^3+n$ is odd'... $\endgroup$ – Dr. Mathva Mar 21 '19 at 18:48

Apply the proof of theorem 1 to the particular functions $f(n) = 2, g(n) = n, h(n) = \frac {n^2}{16}$. Find the best $n_0$ and $c$ to show $f \in O(g)$, and then check that against the final line of the proof.

For 2, the theorem is $n^2 + n - 6 \ge 0 \implies n \ge 2$. That is, from $n^2 + n - 6 \ge 0$, you can prove that $n \ge 2$. Is that what their "proof" does?

For 3, here is a very similar proof:

Theorem for all $n$, $n$ is odd.

Proof: Suppose not, then $n$ is even, but that is false, because when $n = 1$, $n$ is not even. A contradiction, so the theorem is true.

Can you spot the error in this version?


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.