Direct Proof

Show your work for each problem.

1.
What is the first step in a direct proof?
1. a)Use proof by contradiction
2. b)Find a counterexample
3. c)Assume the hypothesis is true
4. d)Prove the conclusion directly
Answer: Assume the hypothesis is true
In a direct proof, we start by assuming the hypothesis (the 'if' part) is true, then use logical steps to reach the conclusion.
2.
According to the definition, an even integer can be written as:
1. a) $2k + 1$ for some integer $k$
2. b) $k/2$ for some integer $k$
3. c) $2k$ for some integer $k$
4. d) $k^2$ for some integer $k$
Answer: $2k$ for some integer $k$
An even integer is any integer that is divisible by 2, so it can be written as $2k$ where $k$ is any integer. For example: $6 = 2 \times 3$ , $-8 = 2 \times (-4)$ .
3.
If $n = 2k + 1$ for some integer $k$ , what is the remainder when $n$ is divided by $2$ ?
Answer: 1
$2k$ divides evenly by 2, and the extra $+1$ is left over, so the remainder is $1$ . A remainder of 1 when dividing by 2 is exactly what makes $n$ odd: $2k + 1$ is the definition of an odd number.
4.
What does QED stand for?
1. a)Quite easily done
2. b)Question every detail
3. c)Quod erat demonstrandum
4. d)Quickly end discussion
Answer: Quod erat demonstrandum
QED stands for 'quod erat demonstrandum', which is Latin for 'which was to be demonstrated'. It marks the successful completion of a proof.
5.
If $a = 2m$ and $b = 2n$ , then $a + b = 2(\square)$ . What goes in the box? Write it in terms of $m$ and $n$ .
Answer: m + n
$a + b = 2m + 2n = 2(m + n)$ . This factored form shows that the sum is even because it's 2 times an integer.
6.
Why is checking examples not the same as a proof?
1. a)Examples take too long
2. b)Examples can't cover all of the infinitely many cases
3. c)Examples are always wrong
4. d)Examples are harder than proofs
Answer: Examples can't cover all of the infinitely many cases
There are infinitely many integers, so we can never check all cases by example. A proof using variables and definitions covers all cases at once.
7.
Prove: If $n$ is even, then $n^2$ is even.
Answer: n^2 = 4k^2 = 2(2k^2)
1. $n$ is even, so $n = 2k$ for some integer $k$ . Then $n^2 = (2k)^2 = \square\, k^2$ . What number goes in the box? 4
2. Factor out 2: $4k^2 = 2(\square)$ . What goes in the box? 2k^2
3. $2k^2$ is an integer, so $n^2 = 2 \cdot (\text{integer})$ . What is $n^2$ ? even
8.
If $n = 2k + 1$ , expand $(2k + 1)^2$ into the form $ak^2 + bk + c$ . What is $b$ , the coefficient of $k$ ?
Answer: 4
$(2k+1)^2 = (2k)^2 + 2(2k)(1) + 1^2 = 4k^2 + 4k + 1$ , so $a = 4$ , $b = 4$ and $c = 1$ . This can be rewritten as $2(2k^2 + 2k) + 1$ , showing it's odd.
9.
Prove: The product of two odd numbers is odd.
Answer: 2(2jk + j + k) + 1
1. Let $a = 2j + 1$ and $b = 2k + 1$ . Expand: $(2j + 1)(2k + 1) = \square\, jk + 2j + 2k + 1$ . What number goes in the box? 4
2. Factor 2 out of the first three terms: $4jk + 2j + 2k + 1 = 2(\square) + 1$ . What goes in the box? 2jk + j + k
3. $2jk + j + k$ is an integer, so $ab = 2 \cdot (\text{integer}) + 1$ . What is $ab$ ? odd
10.
What is circular reasoning in a proof?
1. a)Starting over multiple times
2. b)Going in a circle while writing
3. c)Using too many steps
4. d)Assuming what you're trying to prove
Answer: Assuming what you're trying to prove
Circular reasoning occurs when you use the conclusion (what you're trying to prove) as part of your reasoning. This makes the proof invalid because you haven't actually proven anything.
11.
In the factorization $n^3 - n = (n-1) \cdot n \cdot (n+1)$ , how many consecutive integers are multiplied together?
Answer: 3
The expression factors into three consecutive integers: $(n-1)$ , $n$ , and $(n+1)$ . This is key to proving that $n^3 - n$ is divisible by 3.
12.
Prove: If $a$ is even and $b$ is odd, then $a + b$ is odd.
Answer: 2(m + k) + 1
1. Let $a = 2m$ and $b = 2k + 1$ . Write $a + b$ in terms of $m$ and $k$ : 2m + 2k + 1
2. Factor 2 out of the first two terms: $2m + 2k + 1 = 2(\square) + 1$ . What goes in the box? m + k
3. $m + k$ is an integer, so $a + b = 2 \cdot (\text{integer}) + 1$ . What is $a + b$ ? odd
13.
To prove $n^3 - n$ is divisible by 3, we use the fact that among any 3 consecutive integers:
1. a)None are divisible by 3
2. b)All are divisible by 3
3. c)At least two are divisible by 3
4. d)Exactly one is divisible by 3
Answer: Exactly one is divisible by 3
Every integer has remainder 0, 1, or 2 when divided by 3. In three consecutive integers, we cycle through all three remainders, so exactly one has remainder 0 (divisible by 3).
14.
Prove: If $n$ is an integer, then $n^2 + n$ is even.
Answer: n(n + 1)
1. Factor out $n$ : $n^2 + n = n(\square)$ . What goes in the box? n + 1
2. What can we say about $n$ and $n+1$ ? consecutive integers
3. Among two consecutive integers, how many are even? 1
4. Therefore, the product $n(n+1)$ is always: even
15.
If we want to prove ' $a$ divides $b$ ' using direct proof, we show $b = a \times k$ for some integer $k$ . What value of $k$ shows that 3 divides 12?
Answer: 4
Since $12 = 3 \times 4$ , we have $k = 4$ . This demonstrates that 3 divides 12 because 12 can be expressed as 3 times an integer (4).
16.
Prove: The sum of an even number and its square is even.
Answer: 2(k + 2k^2)
1. Let the even number be $n = 2k$ . Then $n + n^2 = 2k + (2k)^2 = 2k + \square\, k^2$ . What number goes in the box? 4
2. Factor out 2: $2k + 4k^2 = 2(\square)$ . What goes in the box? k + 2k^2
3. $k + 2k^2$ is an integer, so $n + n^2 = 2 \cdot (\text{integer})$ . What is $n + n^2$ ? even
17.
Which statement best describes an axiom?
1. a)A statement that needs verification
2. b)A statement that has been proven true
3. c)A statement that is always false
4. d)A statement accepted as true without proof
Answer: A statement accepted as true without proof
An axiom is a fundamental statement that is accepted as true without proof. Axioms serve as the foundation from which theorems are derived. Examples include 'a = a' (reflexive property) and 'if a = b, then b = a' (symmetric property).