The nature of proof

Develop rigorous proof skills: understand logical implication, quantifiers and equivalence; apply proof by contradiction, existence and uniqueness proofs; prove inequalities using algebraic identities and AM-GM.

Proof · MEX-12-01

Sub-topics

Language and methods of proof

Use the language of logic precisely: implication, converse, contrapositive, negation and equivalence; apply quantifiers (

\forall

\exists

); construct and evaluate counterexamples; identify valid argument forms.

Proof techniques

Apply proof by contradiction to establish irrationality of surds and logarithms; construct existence and uniqueness proofs; prove results involving rational and irrational numbers.

Proving inequalities

Prove algebraic inequalities using the identity

a^2 \geq 0

for all real

a

; apply the AM-GM inequality in two and three variables; prove and apply inequalities involving two or more variables.

Open Math

The nature of proof

Proof · MEX-12-01

Name:

Date:

Language and methods of proof

Q1Straightforward

What is the contrapositive of the statement "If

n

is even, then

n^2

is even"?

A.If $n^2$ is even, then $n$ is even.
B.If $n$ is odd, then $n^2$ is odd.
C.If $n^2$ is odd, then $n$ is odd.
D.If $n$ is even, then $n^2$ is odd.

Q2Straightforward

What is the negation of the statement "There exists an integer

x

such that

x^2 < 0

A.There exists an integer $x$ such that $x^2 \geq 0$ .
B.For all integers $x$ , $x^2 > 0$ .
C.For all integers $x$ , $x^2 \geq 0$ .
D.There exists an integer $x$ such that $x^2 = 0$ .

Q3Straightforward

Which of the following is the converse of "If

a

is divisible by 6, then

a

is divisible by 2"?

A.If $a$ is divisible by 2, then $a$ is divisible by 6.
B.If $a$ is not divisible by 6, then $a$ is not divisible by 2.
C.If $a$ is not divisible by 2, then $a$ is not divisible by 6.
D.If $a$ is divisible by 3, then $a$ is divisible by 6.

Q4Straightforward

The statement "For all real numbers

x

x^2 > x

" is false. Which of the following values of

x

is a counterexample?

A. $x = 2$
B. $x = -3$
C. $x = \dfrac{1}{2}$
D. $x = 10$

Q5Moderate

Which of the following logical argument forms is valid?

A. $P \Rightarrow Q$ ; $Q$ is true; therefore $P$ is true.
B. $P \Rightarrow Q$ ; $P$ is false; therefore $Q$ is false.
C. $P \Rightarrow Q$ ; $Q$ is false; therefore $P$ is false.
D. $P \Rightarrow Q$ ; $P$ is false; therefore $Q$ is true.

Q6Moderate

Which of the following is logically equivalent to the statement

P \Rightarrow Q

A. $Q \Rightarrow P$
B. $\lnot P \Rightarrow \lnot Q$
C. $P \Rightarrow \lnot Q$
D. $\lnot Q \Rightarrow \lnot P$

Q7Moderate

Disprove the following statement by finding a counterexample:

"If

n^2

is divisible by 4, then

n

is divisible by 4."

Q8Moderate

Prove by the contrapositive method:

"If

n^2

is even, then

n

is even."

Clearly state the contrapositive and prove it directly.

Q9Moderate

The statement "For all real numbers

x

|x| > 0

" is false. Which of the following is the best counterexample?

A. $x = 1$
B. $x = -5$
C. $x = 0$
D. $x = 0.001$

Q10Challenging

Prove by the contrapositive method:

"For all integers

n

, if

n^2

is divisible by 3, then

n

is divisible by 3."

Consider all possible remainders when

n

is divided by 3.

Q11Challenging

Prove that the product of two odd integers is odd.

Q12Challenging

Consider the statement: "There exists a real number

x

such that

x^2 + 1 = 0

."

(a) Write the negation of this statement.
(b) Determine whether the original statement is true or false, and justify your answer.

Proof techniques

Q13Straightforward

Prove by contradiction that

\sqrt{2}

is irrational.

Q14Straightforward

In a proof by contradiction that

\sqrt{3}

is irrational, which is the correct first assumption?

A.Assume $\sqrt{3}$ is irrational.
B.Assume $\sqrt{3} = \dfrac{p}{q}$ for integers $p, q$ with $\gcd(p,q)=1$ and $q \neq 0$ .
C.Assume $3$ is not a perfect square.
D.Assume $p^2 = 3q^2$ for some integers $p$ and $q$ .

Q15Straightforward

Which of the following correctly describes a proof of **uniqueness** of the additive inverse of a real number

a

A.Show that $-a$ exists and that $a + (-a) = 0$ .
B.Show that if $a + x = 0$ and $a + y = 0$ , then $x = y$ .
C.Show that $a + 0 = a$ for all real $a$ .
D.Show that there is no real number $b$ such that $a + b \neq 0$ .

Q16Moderate

Prove by contradiction that

\sqrt{5}

is irrational.

Q17Moderate

Prove that the sum of a rational number and an irrational number is irrational.

Q18Moderate

Prove by contradiction that

\log_2 3

is irrational.

Q19Moderate

Which of the following numbers is rational?

A. $\sqrt{7}$
B. $\pi$
C. $\dfrac{22}{7}$
D. $\sqrt{2} + \sqrt{3}$

Q20Moderate

Prove by contradiction: "If

n^2

is odd, then

n

is odd."

(This can also be proved by contrapositive — here, use a direct proof by contradiction instead.)

Q21Challenging

Prove that

\sqrt{2} + \sqrt{3}

is irrational.

Q22Challenging

Prove that the product of a non-zero rational number and an irrational number is irrational.

Q23Challenging

Prove that there is no rational number

x

such that

x^2 = 12

Q24Challenging

Proof by **construction** (direct existence proof) means:

A.Assuming the desired object does not exist, then deriving a contradiction.
B.Proving that the object's properties follow logically from axioms.
C.Directly exhibiting or building an example that satisfies the required condition.
D.Using mathematical induction to show existence for all natural numbers.

Proving inequalities

Q25Straightforward

Prove that

a^2 + b^2 \geq 2ab

for all real numbers

a

and

b

.

State the condition for equality.

Q26Straightforward

Prove that

x^2 - 4x + 4 \geq 0

for all real numbers

x

, and hence prove that

x^2 + 4 \geq 4x

Q27Straightforward

The AM-GM inequality for two non-negative numbers

a

and

b

states:

A. $\dfrac{a + b}{2} \leq \sqrt{ab}$
B. $\dfrac{a + b}{2} \geq \sqrt{ab}$ , with equality iff $a = b$
C. $a + b \geq ab$ , with equality iff $a = b = 1$
D. $\sqrt{ab} \geq \dfrac{a+b}{2}$ , with equality iff $a = b$

Q28Moderate

Prove the AM-GM inequality: for all non-negative real numbers

a

and

b

\frac{a + b}{2} \geq \sqrt{ab}

and state when equality holds.

Q29Moderate

Prove that for all real numbers

a

b

c

a^2 + b^2 + c^2 \geq ab + bc + ca

Q30Moderate

Prove that for all positive real numbers

a

and

b

\frac{a}{b} + \frac{b}{a} \geq 2

and state when equality holds.

Q31Moderate

Given that

x

and

y

are positive real numbers with

x + y = 10

, use the AM-GM inequality to find the maximum possible value of

xy

Q32Moderate

Given that

a

and

b

are positive real numbers with

a + b = 6

, find the maximum possible value of

ab

using the AM-GM inequality.

Q33Challenging

Prove that for all real numbers

a

and

b

(a + b)^2 \leq 2(a^2 + b^2)

Also state the condition for equality.

Q34Challenging

Prove the Cauchy-Schwarz inequality for two pairs of real numbers:

(a_1 b_1 + a_2 b_2)^2 \leq (a_1^2 + a_2^2)(b_1^2 + b_2^2)

for all real

a_1, a_2, b_1, b_2

Q35Challenging

For

x > 0

, find the minimum value of

x + \dfrac{16}{x}

using the AM-GM inequality.

Q36Challenging

Given

x + y = 20

with

x, y > 0

, find the maximum value of

xy

Worked solutions and answers at openmath.au/year-12/extension-2/the-nature-of-proof