Introduction to Mathematical Proofs

Show your work for each problem.

1.
What is a mathematical proof?
1. a)A guess about whether something is true
2. b)A formula to memorize
3. c)A single example that works
4. d)A logical argument showing why a statement must be true
Answer: A logical argument showing why a statement must be true
A mathematical proof is a logical argument that demonstrates why a statement must be true for all cases, using definitions, axioms, and previously proven theorems.
2.
What is the difference between an axiom and a theorem?
1. a)They are the same thing
2. b)Axioms are false; theorems are true
3. c)A theorem is accepted without proof; an axiom is proven
4. d)An axiom is accepted without proof; a theorem is proven
Answer: An axiom is accepted without proof; a theorem is proven
Axioms are statements we accept as true without proof - they are our starting points. Theorems are statements that have been proven true using axioms and other theorems.
3.
If $n$ is an even number, we can write $n = 2k$ where $k$ is an integer. If $n = 12$ , what is $k$ ?
Answer: 6
Since $12 = 2k$ , we solve for $k$ : $k = 12 \div 2 = 6$ . This confirms 12 is even because $12 = 2 \times 6$ .
4.
If $n$ is an odd number, we can write $n = 2k + 1$ . If $n = 15$ , what is $k$ ?
Answer: 7
Since $15 = 2k + 1$ , we solve: $2k = 15 - 1 = 14$ , so $k = 7$ . Check: $2(7) + 1 = 15$ .
5.
In a proof by contradiction, what do we do first?
1. a)Prove the statement directly
2. b)Give several examples
3. c)State the conclusion first
4. d)Assume the opposite of what we want to prove
Answer: Assume the opposite of what we want to prove
In proof by contradiction, we assume the opposite of what we want to prove is true. Then we show this leads to a logical impossibility (contradiction), proving our original statement must be true.
6.
Why is showing $2 + 4 = 6$ NOT a proof that 'the sum of two even numbers is even'?
1. a)It only proves one specific case, not all cases
2. b)We need to use subtraction instead
3. c)The calculation is wrong
4. d)6 is not even
Answer: It only proves one specific case, not all cases
There are infinitely many pairs of even numbers. Testing $2 + 4 = 6$ only proves that ONE pair works. A proof must show ALL pairs work, which requires using variables like $2m + 2n = 2(m+n)$ .
7.
Let $a = 2m$ and $b = 2n$ be even numbers. Complete: $a + b = 2m + 2n = 2(\square)$ . What goes in the box?
Answer: m+n
$a + b = 2m + 2n = 2(m + n)$ . Since $m + n$ is an integer, $2(m+n)$ is even. This proves the sum of two even numbers is always even!
8.
Prove that the product of two odd numbers is odd. Let $a = 2m + 1$ and $b = 2n + 1$ .
Answer: 2(2mn+m+n)+1
1. Write out $(2m + 1)(2n + 1)$ expanded 4mn+2m+2n+1
2. Factor 2 out of the first three terms: $4mn + 2m + 2n + 1 = 2(\square) + 1$ . What goes in the box? 2mn+m+n
3. Is $2(2mn + m + n) + 1$ in the form $2k + 1$ ? yes
9.
Which statement correctly describes circular reasoning in a proof?
1. a)Ending with QED
2. b)Starting with a definition
3. c)Using too many steps
4. d)Using the conclusion as part of the proof
Answer: Using the conclusion as part of the proof
Circular reasoning occurs when you assume what you're trying to prove. For example, saying 'X is true because X is true' doesn't actually prove anything - it just goes in circles.
10.
In the proof that $\sqrt{2}$ is irrational, we assumed $\sqrt{2} = \frac{a}{b}$ with no common factors. We showed both $a$ and $b$ must be even. What common factor do they share?
Answer: 2
If both $a$ and $b$ are even, they both have 2 as a factor. This contradicts our assumption that they share no common factors. This contradiction proves $\sqrt{2}$ cannot be written as $\frac{a}{b}$ .
11.
Prove: The sum of an even number and an odd number is odd.
Answer: 2(m+n)+1
1. Let the even number be $a = 2m$ . The odd number is $b = 2n + \square$ . What number goes in the box? 1
2. Calculate $a + b = 2m + (2n + 1)$ 2m+2n+1
3. Factor 2 out of the first two terms: $2m + 2n + 1 = 2(\square) + 1$ . What goes in the box? m+n
4. Is $2(m+n) + 1$ odd? yes
12.
The statement 'All prime numbers are odd' seems true for 3, 5, 7, 11, 13... What disproves this statement?
1. a)1 is not prime
2. b)15 has many factors
3. c)9 is odd but not prime
4. d)2 is prime but even
Answer: 2 is prime but even
2 is prime (only divisible by 1 and itself) but it is even. One counterexample is enough to disprove a universal statement. This shows why we need proofs, not just examples!
13.
Prove by contradiction: There is no largest integer.
Answer: N+1
1. Assume the opposite: there IS a largest integer. Call it $N$ . Is $N + 1$ also an integer? yes
2. Is $N + 1 > N$ ? yes
3. We found an integer larger than $N$ . What is it? N+1
4. This contradicts that $N$ is the largest. Therefore, our assumption was... false
14.
Why must $a$ be even when $a^2$ is even? Suppose $a$ were odd, $a = 2k + 1$ . Then $a^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ . What is the remainder when $a^2$ is divided by 2?
Answer: 1
$2(2k^2 + 2k)$ is a multiple of 2, so dividing $a^2$ by 2 leaves remainder 1: $a^2$ would be odd. So if $a$ were odd, $a^2$ would be odd. Therefore, if $a^2$ is even, $a$ cannot be odd, so it must be even.
15.
If ' $P$ implies $Q$ ' is true, which of the following must also be true?
1. a)'Not $Q$ implies not $P$ ' (contrapositive)
2. b)' $Q$ implies $P$ ' (converse)
3. c)'Not $P$ implies not $Q$ ' (inverse)
4. d)All of the above
Answer: 'Not $Q$ implies not $P$ ' (contrapositive)
The contrapositive ('Not $Q$ implies not $P$ ') is always logically equivalent to the original statement. The converse and inverse are NOT guaranteed to be true. Example: 'If it rains, the ground is wet' is true, but 'If the ground is wet, it rained' is not always true (sprinklers!).
16.
Prove: If $n^2$ is odd, then $n$ is odd.
Answer: $n$ is odd
1. We'll prove the contrapositive. If $n$ is even, then $n^2$ is...? even
2. If $n = 2k$ (even), what is $n^2$ ? 4k^2
3. Complete: $4k^2 = 2(\square)$ . What goes in the box? 2k^2
4. Since $2(2k^2)$ is even, we proved: if $n$ is even then $n^2$ is even. By contrapositive, if $n^2$ is odd, then $n$ is... odd