Chapter 6 : Proof Techniques

Question 1

List out 2 types of Proof

Answer 1

1. Direct Proof
2. Indirect Proof

Question 2

List out the type of Proof in Direct Proof

Answer 2

1. Proof by construction

Question 3

List out 2 types of Proof in Indirect Proof

Answer 3

1. Proof by Contrapositive
2. Proof by Contradiction
   
   • Show the answer
   • Show the answer is wrong at the end

Sum of 2 even integers is odd
2i + 2j = c , where c is some integer
i + j = c / 2 ( Contradiction Happens )

Question 4

How can we Proof by Construction ( Direct Proof ) a statement?

Answer 4

Proof p → q
1. Assume p is True
2. Show q is True
3. Conclusion p → q is True

Question 5

How can we Proof by Contrapositive ( Indirect Proof ) a statement?

Answer 5

Proof p → q ≡ ~q → ~p
1. Identidy ~q → ~p
2. Assume ~q is True
3. Show ~p is True
4. ∴~q → ~p is True
5. p → q is True ( p → q ≡ ~q → ~p )

Question 6

How can we Proof by Contradiction ( Indirect Proof ) a statement?

Answer 6

Proof p is True ( Single Statement )
1. Assume ~p is True
2. Contradictio happen ( ~p is False )
3. ∴ p is True

Proof p → q is True
1. Assume p ^ ~q is True
2. Contradiction p ^ ~q is False
3. Conclusion p → q is True

~ ( p → q ) ≡ p ^ ~q
p → q is True
~ ( p → q ) is False
Assume ~ ( p → q ) is True

Question 7

What statement does Axioms ( Postulates ) mean?

Answer 7

1. A statement that is assumed to be true without a proof

• Example
  A straight line segment can be drawn between any two distinct points.” We don’t try to prove that; we accept it as a starting point

Question 8

What statement does Hypothesis mean?

Answer 8

1. Statements that has conditions of if parts of what we want to prove

• Example
  If a triangle is right-angled, then the square of the hypotenuse is the sum of the squares of the other two sides,” the phrase “If a triangle is right-angled” is the hypothesis.

Question 9

What does the Rules of Inference do?

Answer 9

1. Logical steps that used to draw conclusions and to move from one step to another

• Deliverable is New Theorems
• Rules of Inference pass in
  
  1. Axioms
  2. Hypothesis
  3. Previously Proven Theorems

Question 10

List out the basic definition below:
1. Even Number
2. Odd Number

Answer 10

1. n = 2k
2. n = 2k + 1

Question 11

What does a Direct Proof proofs?

Answer 11

1. Shows that a conditional statement p → q is true by showing that if p is true then q must also be true

Question 12

Proof that “if n is an odd integer, then n² is odd”

Answer 12

We assume that n is odd ( Hypothesis )
n = 2k + 1, where k is some integer ( Definition of Odd )

n = ( 2k + 1 ) ( 2k + 1 )
= 4k² + 4k + 1
= 2 ( 2k² + 2k ) + 1

Let r = 2k² + 2k . Then r is an integer ( Axiom ) therefore n² = 2r + 1
So, we have proved the theorem “if n is an odd integer, then n² is odd”

Question 13

What to write inside direct proof? ( 5 )

Answer 13

1. We assume that n is odd/even
2. n = 2k + 1 / n = 2k, where k is some integer
3. Equation n² = ( 2k + 1 )( 2k + 1 )
4. Let r = … . Then r is an integer therefore … is odd/even
5. So, we have proved the theorem “Question”

Question 14

Prove that “for every 2 integers a and b, if a and b are odd, then ab is odd”

Answer 14

Let i and j are integers
We assume that a and b are odd
a = 2i + 1 , b = 2j + 1 , where i and j is some integer
ab = ( 2i + 1 ) ( 2j + 1 )
= 2 ( 2ij + i + j ) = 1

Let r = 2ij + i + j . Then r is an integer therefore ab is odd
So we have proved the theorem “for every 2 integers a and b, if a and b are odd, then ab is odd”

Question 15

Give a direct proof if n is an even integer, then n² + 2n is also an even integer

Answer 15

We assume that n is an even integer
Let n = 2k

n² + 2n = ( 2k )² + 2( 2k )
= 4k² + 4k
= 2 ( 2k² + 2k )

Let r = 2k² + 2k . Then r is an integer therefore n² + 2n = 2r is even
So we have proved the theorem “if n is an even integer, then n² + 2n is also an even integer”

Question 16

Give a direct proof if n is an even integer, then n³ + n is also an even integer

Answer 16

We assume that n is an even integer
Let n = 2k

n³ + n = ( 2k ) ³ + 2k
= 8k³ + 2k
= 2 ( 4k³ + k )

Let r = 4k³ + 2k. Then r is an integer therefore n³ + n = 2r is even
So we have proved the theorem “if n is an even integer, then n³ + n is also an even integer”

Question 17

What is the formula for the Proof by Contrapositive?

Answer 17

1. p → q ≡ ~q → ~p

• So we need to identify ~q is ~p is true to verify that it is equal to p → q

Question 18

Prove that “if n is an integer and 3n + 2 is odd, then n is odd”

Answer 18

We assume that n is even ( n is odd in question )
Then n = 2k, where k is some integer.
Therefore
3n + 2 = 3 ( 2k ) + 2
= 6k + 2
= 2 ( 3k + 1 ) is even ( 2m )

So we have proved that ~q ( n is even, although n is odd in question ) → ~p ( the equation is even, although the question is odd )

Because the negation of the conclusion of the conditional statement implies that the hypothesis ( p ) is false, the original conditional statement is true.
So, we have proved the theorem “if n is an integer and 3n + 2 is odd, then n is odd”

Question 19

If x is a real number and 3x³-9x²+x-3 = 0 , then x = 3 using proof by contrapositive

Answer 19

We assume that If x is a real number and 3x³-9x²+x-3 = 0 , then x = 3 is false.
Assume x ≠ 3 then,
3x³-9x²+x-3 = 3x² ( x - 3 ) + 1 ( x - 3 )
= ( 3x² + 1 ) ( x - 3 )
( 3x² + 1 ) ≠ 0 and ( x - 3 ) ≠ 0

Because the negation of the conclusion of the contradictional statement implies that the hypothesis ( p ) is false, the original conditional statement is true

So, we have proved that If x is a real number and 3x³-9x²+x-3 = 0 , then x = 3

• Explanation
  (x - 3) ≠ 0: This explicitly states that if x is not equal to 3, then this factor is non-zero. For the entire product (3x² + 1)(x - 3) to be zero in this case, the other factor (3x² + 1) must be zero.

Question 20

What is the formula for the Proof by Contradiction?

Answer 20

1. ~ ( p → q ) ≡ p ^ ~q

Question 21

Give a proof by contradiction of the theorem : “If 3n + 2 is odd, then n is odd”

Answer 21

Suppose that 3n + 2 is odd and n is even ( p ^ ~q )
Then, n = 2r, where r is some integer
Hence 3n = 6r
3n + 2 = 6r + 2
3n + 2 = 2 ( 3r + 1 )
3n + 2 = 2k , where k = 3r + 1

Thus 3n + 2 is even, which is false ( Contradiction! )
So, we have proved the theorem “If 3n + 2 is odd, then n is odd”

Question 22

Give a proof by contradiction of the theorem : “If x² ≥ 25 then |x| ≥ 5”

Answer 22

Suppose that x² ≥ 25 then we need to show |x| < 5.
Then either x < 5 or x > -5
If x < 5 then x² < 25
IF x > -5 , we again have x² < 25

In either case, we have a contradiction. Hence |x| ≥ 5 So, we have proved the theorem "If x² ≥ 25 then |x| ≥ 5"

• Explanation
  The inequality ∣x∣<5 means that the distance of x from zero is less than 5. Let’s consider what numbers satisfy this condition on the number line:

Numbers that are less than 5 units to the right of zero satisfy this. These are all the numbers x such that 0≤x<5.
Numbers that are less than 5 units to the left of zero also satisfy this. These are all the numbers x such that −5<x≤0.

Question 23

Use a direct proof to prove that the sum of two odd integers is even

Answer 23

Let a and b are 2 odd integers
a = 2 i + 1 , where i is some integer
b = 2 j + 1 , where j is some integer

a + b = 2i + 1 + 2j + 1
= 2i + 2j + 2
= 2 ( i + j + 1 )
= 2k , where k = i + j + 1

Therefore, we have proved that a + b is even

Question 24

Use a proof by contradiction to prove that the sum of 2 even integers is even

Answer 24

Assume “Sum of 2 even integers is odd”
Let a and b are even integers
a = 2i, where i is some integer
b = 2j, where j is some integer

a + b = c , where c is some odd integer
2i + 2j = c
2 ( i + j ) = c
i + j = c / 2 → Always Fraction ( Contradiction Error )

i + j is integer but c / 2 is fraction and since c is odd integer
i + j ≠ c / 2 contradiction

We have proven that sum of 2 even integers is even

Question 25

Use proof by contradiction to prove that if x² ≥ 49 then |x| ≥ 7

Answer 25

Assume "if x² ≥ 49 then |x| < 7" is true Then either x < 7 or x > -7 If x < 7 then x² < 49 If x > -7 , we again have x² < 49 In either case, x² ≥ 49, we have contradiction So, we have proven that "if x² ≥ 49 then |x| ≥ 7"

Question 26

Show that if n is an integer and n³ + 5 is odd, then n is even using a proof by contrapositive

Answer 26

If n is odd, then n is an integer and n³ + 5 is even ( ~q → ~p ) n = 2k + 1 n³ + 5 = ( 2k + 1 ) ³ + 5 = 8k³ + 12k² + 6k + 6 = 2 ( 4k³ + 6k² + 3k + 3 ) Let m = 4k³ + 6k² + 3k + 3 where m is integer n³ + 5 = 2m which is an even integer We have proven that "if n is an integer and n³ + 5 is odd, then n is even"

Question 27

Show that if n is an integer and n³ + 5 is odd, then n is even using a proof by contradiction

Answer 27

Assume "if n is an integer and n³ + 5 is odd, then n is even" is true If n³ + 5 is odd, then n³ + 5 = 2i + 1 where i is some integer If n is odd, n = 2k + 1 where k is some integer n³ + 5 = 2i + 1 (2k)³ + 5 = 2i + 1 8k³ + 12k² + 6k + 6 = 2i + 1 8k³ + 12k² + 6k + 5 + 1 = 2i + 1 2 ( 4k³ + 6k² + 3k + 5 / 2 ) + 1 = 2i + 1 i = 4k³ + 6k² + 3k + 5 / 2 is a contradiction because i is an integer but 4k³ + 6k² + 3k + 5 / 2 is not an integer Hence, n³ + 5 is odd, then n is odd is not true So, we have proven that " if n is an integer and n³ + 5 is odd, then n is even"