Theorems & Proof Corrections [discrete mathematics]

Question

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!

Answer 1

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?