12.B.E: Exercises for Proofs

Exercise \(\PageIndex{1}\)

In each case prove the result and either prove the converse or give a counterexample.

1. If \(n\) is an even integer, then \(n^{2}\) is a multiple of \(4\).
2. If \(m\) is an even integer and \(n\) is an odd integer, then \(m + n\) is odd.
3. If \(x = 2\) or \(x = 3\), then \(x^{3} - 6x^{2} + 11x - 6 = 0\).
4. If \(x^{2} - 5x + 6 = 0\), then \(x = 2\) or \(x = 3\).

Answer

2. If \(m = 2p\) and \(n = 2q + 1\) where \(p\) and \(q\) are integers, then \(m + n = 2(p + q) + 1\) is odd. The converse is false: \(m = 1\) and \(n = 2\) is a counterexample.
4. \(x^{2} - 5x + 6 = (x - 2)(x - 3)\) so, if this is zero, then \(x = 2\) or \(x = 3\). The converse is true: each of \(2\) and \(3\) satisfies \(x^{2} - 5x + 6 = 0\).

Exercise \(\PageIndex{2}\)

In each case either prove the result by splitting into cases, or give a counterexample.

1. If \(n\) is any integer, then \(n^{2} = 4k + 1\) for some integer \(k\).
2. If \(n\) is any odd integer, then \(n^{2} = 8k + 1\) for some integer \(k\).
3. If \(n\) is any integer, \(n^{3} - n = 3k\) for some integer \(k\). [Hint: Use the fact that each integer has one of the forms \(3k\), \(3k + 1\), or \(3k + 2\), where \(k\) is an integer.]

Answer

2. This implication is true. If \(n = 2t + 1\) where \(t\) is an integer, then \(n^{2} = 4t^{2} + 4t + 1 = 4t(t + 1) + 1\). Now \(t\) is either even or odd, say \(t = 2m\) or \(t = 2m + 1\). If \(t = 2m\), then \(n^{2} = 8m(2m + 1) + 1\); if \(t = 2m + 1\), then \(n^{2} = 8(2m + 1)(m + 1) + 1\). Either way, \(n^{2}\) has the form \(n^{2} = 8k + 1\) for some integer \(k\).

Exercise \(\PageIndex{3}\)

In each case prove the result by contradiction and either prove the converse or give a counterexample.

1. If \(n > 2\) is a prime integer, then \(n\) is odd.
2. If \(n + m = 25\) where \(n\) and \(m\) are integers, then one of \(n\) and \(m\) is greater than \(12\).
3. If \(a\) and \(b\) are positive numbers and \(a \leq b\), then \(\sqrt{a} \leq \sqrt{b}\).
4. If \(m\) and \(n\) are integers and \(mn\) is even, then \(m\) is even or \(n\) is even.

Answer

2. Assume that the statement “one of \(m\) and \(n\) is greater than \(12\)” is false. Then both \(n \leq 12\) and \(m \leq 12\), so \(n + m \leq 24\), contradicting the hypothesis that \(n + m = 25\). This proves the implication. The converse is false: \(n = 13\) and \(m = 13\) is a counterexample.
4. Assume that the statement “\(m\) is even or \(n\) is even” is false. Then both \(m\) and \(n\) are odd, so \(mn\) is odd, contradicting the hypothesis. The converse is true: If \(m\) or \(n\) is even, then \(mn\) is even.

Exercise \(\PageIndex{4}\)

Prove each implication by contradiction.

1. If \(x\) and \(y\) are positive numbers, then \(\sqrt{x + y} \neq \sqrt{x} + \sqrt{y}\).
2. If \(x\) is irrational and \(y\) is rational, then \(x + y\) is irrational.
3. If \(13\) people are selected, at least \(2\) have birthdays in the same month.

Answer

2. If \(x\) is irrational and \(y\) is rational, assume that \(x + y\) is rational. Then \(x = (x + y) - y\) is the difference of two rationals, and so is rational, contrary to the hypothesis.

Exercise \(\PageIndex{5}\)

Disprove each statement by giving a counterexample.

1. \(n^{2} + n + 11\) is a prime for all positive integers \(n\).
2. \(n^{3} \geq 2^n\) for all integers \(n \geq 2\).
3. If \(n \geq 2\) points are arranged on a circle in such a way that no three of the lines joining them have a common point, then these lines divide the circle into \(2^{n-1}\) regions. [The cases \(n = 2\), \(3\), and \(4\) are shown in the diagram.]

Answer

2. \(n = 10\) is a counterexample because \(10^3 = 1000\) while \(2^{10} = 1024\), so the statement \(n^{3} \geq 2^n\) is false if \(n = 10\). Note that \(n^{3} \geq 2^n\) does hold for \(2 \leq n \leq 9\).

Exercise \(\PageIndex{6}\)

The number \(e\) from calculus has a series expansion

\[e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots \nonumber \]

where \(n! = n(n - 1) \cdots 3 \cdot 2 \cdot 1\) for each integer \(n \geq 1\). Prove that \(e\) is irrational by contradiction. [Hint: If \(e = m/n\), consider

\[k = n! \left(e- 1 - \frac{1}{1!} - \frac{1}{2!} - \frac{1}{3!} - \cdots - \frac{1}{n!} \right). \nonumber \]

Exercise \(\PageIndex{7}\)

Show that \(k\) is a positive integer and that

\[k = \frac{1}{n+1} + \frac{1}{(n+1)(n+2)} + \cdots < \frac{1}{n}. ] \nonumber \]