Proofs - Topic 1

Question 1

Year 1 - Chapter 7.5

What is proof by exhaustion?

Answer 1

Proving a mathematical statement by breaking the statement into smaller cases and proving each case separately.

Question 2

Year 1 - Chapter 7.5

How do you prove a statement by exhaustion?

Example:

Answer 2

Prove that all square numbers are a multiple of 4 or 1 more than a multiple of 4:

For odd numbers:

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

For even numbers:

• (2n)² = 4n²

Question 3

Year 1 - Chapter 7.5

What is proof by counter-example?

Answer 3

A counter-example is one example that doesn’t work for the statement, with this example being sufficient to disprove a statement.

Question 4

Year 1 - Chapter 7.5

How do you prove a statement by counter-example?

Example:

Answer 4

‘The sum of two consecutive prime numbers is always even.’

• 2 and 3 are both prime
• 2+3 = 5
• 5 is odd
• Therefore the statement is not true

Question 5

Year 2 - Chapter 1.1

What is proof by contradiction?

Answer 5

Proving a statement by using logical steps to show that the assumption leads to something impossible - either a contradiction of the assumption, or a contradiction of a fact you know to be true. To start a proof by contradiction, you assume that the statement given is not true. You can then conclude that your assumption was incorrect and that the original statement was true.

Question 6

Year 2 - Chapter 1.1

How do you prove a statement by contradiction?

Example:

Answer 6

‘Prove that √2 is an irrational number.’

• Assumption: √2 is rational
• √2 = a/b; no common factors, fraction cannot be reduced further
• 2 = a²/b²
• a² = 2b²
• a² must be even, so a is also even
• a = 2n
• (2n)² = 2b²
• 2n² = b²
• b² must be even, so b is also even
• If both a and b are even, they will have a common factor of 2, contradicting the statement that a and b have no common factors, therefore √2 is irrational