Introduction to Proofs

Proofs are fundamental to Mathematics, serving as the rigorous justification of mathematical statements. A proof consists of a sequence of logical deductions starting from axioms, definitions, or previously established results, leading to the conclusion.

In this chapter, we explore various methods of proving mathematical propositions, focusing on procedural techniques aligned with the NCERT syllabus for Classes 9 to 11.

Direct Proof Method

Direct proof involves starting from the given assumptions and using logical deductions to arrive at the statement to be proved.

Straightforward Approach

This approach uses a chain of logical arguments, applying axioms, definitions, and previously proved theorems to deduce the conclusion directly.

Worked Illustration

Example 1: Show that if \(x^2 - 5x + 6 = 0\), then \(x = 3\) or \(x = 2\).

Solution:

Given:

\[ x^2 - 5x + 6 = 0 \]

Factorize the quadratic:

\[ x^2 - 5x + 6 = (x - 3)(x - 2) = 0 \]

By the zero product property:

\[ (x - 3) = 0 \quad \text{or} \quad (x - 2) = 0 \]

Solving each:

\[ x = 3 \quad \text{or} \quad x = 2 \]

Hence, the statement is proved.

Explanation

The proof uses factorization and the zero product property to deduce the roots of the quadratic equation.

Example 2: Prove that the function \(f: \mathbb{R} \to \mathbb{R}\) defined by \(f(x) = 2x + 5\) is one-one.

Solution:

To prove \(f\) is one-one, show that \(f(x_1) = f(x_2) \implies x_1 = x_2\).

Assume \(f(x_1) = f(x_2)\):

\[ 2x_1 + 5 = 2x_2 + 5 \]

Subtract 5 from both sides:

\[ 2x_1 = 2x_2 \]

Divide both sides by 2:

\[ x_1 = x_2 \]

Hence, \(f\) is one-one.

Practice Set

• Show that if \(x^2 - 7x + 12 = 0\), then \(x = 3\) or \(x = 4\).
• Prove that the function \(g(x) = 3x - 1\) is one-one.
• Prove that the sum of two even numbers is even using direct proof.

Answer Key

• Factorize \(x^2 - 7x + 12 = (x - 3)(x - 4) = 0\), so \(x = 3\) or \(x = 4\).
• Assume \(g(x_1) = g(x_2)\), then \(3x_1 - 1 = 3x_2 - 1\), so \(x_1 = x_2\), hence one-one.
• Let two even numbers be \(2m\) and \(2n\). Their sum is \(2m + 2n = 2(m + n)\), which is even.

Quick Reference

Concept	Key Formula/Property
Zero Product Property	\(ab = 0 \implies a=0 \text{ or } b=0\)
One-One Function	\(f(x_1) = f(x_2) \implies x_1 = x_2\)

Glossary

• Direct Proof: A method of proof starting from given assumptions to reach the conclusion directly.
• One-One Function: A function where each output corresponds to exactly one input.
• Zero Product Property: If the product of two numbers is zero, then at least one of the numbers is zero.

Mathematical Induction

Mathematical induction is a method of proving statements that are asserted for all natural numbers \(n \geq j\), where \(j\) is a starting integer.

The principle states that if:

• Base Case: The statement is true for \(n = j\).
• Inductive Step: Assuming the statement is true for \(n = k\), it is also true for \(n = k + 1\).

Then the statement is true for all \(n \geq j\).

Worked Illustration

Example 3: Show that for the matrix \(A = \begin{bmatrix} \cos \theta & \sin \theta \\ -\sin \theta & \cos \theta \end{bmatrix}\),

\[ A^n = \begin{bmatrix} \cos n\theta & \sin n\theta \\ -\sin n\theta & \cos n\theta \end{bmatrix} \]

Solution:

Define the statement \(P(n): A^n = \begin{bmatrix} \cos n\theta & \sin n\theta \\ -\sin n\theta & \cos n\theta \end{bmatrix}\).

Base Case (n=1):

\[ A^1 = A = \begin{bmatrix} \cos \theta & \sin \theta \\ -\sin \theta & \cos \theta \end{bmatrix} \]

So, \(P(1)\) is true.

Inductive Step: Assume \(P(k)\) is true:

\[ A^k = \begin{bmatrix} \cos k\theta & \sin k\theta \\ -\sin k\theta & \cos k\theta \end{bmatrix} \]

We want to prove \(P(k+1)\):

\[ A^{k+1} = A^k A = \begin{bmatrix} \cos k\theta & \sin k\theta \\ -\sin k\theta & \cos k\theta \end{bmatrix} \begin{bmatrix} \cos \theta & \sin \theta \\ -\sin \theta & \cos \theta \end{bmatrix} \]

Multiply the matrices:

\[ = \begin{bmatrix} \cos k\theta \cos \theta - \sin k\theta \sin \theta & \cos k\theta \sin \theta + \sin k\theta \cos \theta \\ -\sin k\theta \cos \theta - \cos k\theta \sin \theta & -\sin k\theta \sin \theta + \cos k\theta \cos \theta \end{bmatrix} \]

Using trigonometric identities:

\[ = \begin{bmatrix} \cos (k+1)\theta & \sin (k+1)\theta \\ -\sin (k+1)\theta & \cos (k+1)\theta \end{bmatrix} \]

Thus, \(P(k+1)\) is true.

By the principle of mathematical induction, \(P(n)\) is true for all \(n \geq 1\).

Practice Set

• Prove by induction that \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\).
• Show by induction that \(2^n > n^2\) for \(n \geq 5\).
• Prove that \(\sum_{k=1}^n k^3 = \left( \frac{n(n+1)}{2} \right)^2\) by induction.

Answer Key

• Base case \(n=1\): \(1 = \frac{1(1+1)}{2} = 1\). Inductive step: Assume true for \(n=k\), prove for \(n=k+1\) by adding \(k+1\) to both sides.
• Base case \(n=5\): \(2^5=32 > 25=5^2\). Inductive step: Assume true for \(n=k\), prove for \(n=k+1\) using \(2^{k+1} = 2 \cdot 2^k > 2k^2\) and compare with \((k+1)^2\).
• Use base case \(n=1\) and inductive step by adding \((k+1)^3\) to the sum.

Quick Reference

Step	Description
Base Case	Verify statement for initial value \(n=j\)
Inductive Step	Assume true for \(n=k\), prove for \(n=k+1\)

Glossary

• Mathematical Induction: A proof technique to establish statements for all natural numbers.
• Base Case: The initial step verifying the statement for the starting value.
• Inductive Hypothesis: The assumption that the statement holds for \(n=k\).
• Inductive Step: The step proving the statement for \(n=k+1\) using the hypothesis.

Proof by Cases

Proof by cases involves splitting the hypothesis into several mutually exclusive cases and proving the conclusion for each case.

Worked Illustration

Example 4: Show that in any triangle \(ABC\),

\[ a = b \cos C + c \cos B \]

Solution:

Let \(ABC\) be any triangle. Draw a perpendicular \(AD\) from vertex \(A\) to side \(BC\) (extended if necessary).

Since any triangle is either acute, obtuse, or right angled, split into three cases:

• Case (i): \(\angle C\) is acute.
• Case (ii): \(\angle C\) is obtuse.
• Case (iii): \(\angle C\) is right angle.

For each case, use trigonometric ratios in right triangles \(ADB\) and \(ADC\) to express \(a\) in terms of \(b\), \(c\), and cosines of angles.

For example, in Case (i):

\[ BD = c \cos B, \quad CD = b \cos C, \quad a = BD + CD = c \cos B + b \cos C \]

Similarly, verify for other cases.

Since the statement holds in all cases, it is proved by cases.

Practice Set

• Prove that the absolute value function satisfies \(|x| = x\) if \(x \geq 0\) and \(|x| = -x\) if \(x < 0\) by cases.
• Show that for any integer \(n\), \(n^2 \equiv 0 \text{ or } 1 \pmod{4}\) by cases.
• Prove that the function \(f(x) = x^2\) is increasing for \(x \geq 0\) and decreasing for \(x \leq 0\) by cases.

Answer Key

• Check definition of absolute value for \(x \geq 0\) and \(x < 0\) separately.
• Consider cases \(n = 2k\) and \(n = 2k+1\) for integer \(k\) and compute \(n^2 \pmod{4}\).
• Analyze derivative or difference \(f(x+h) - f(x)\) for \(x \geq 0\) and \(x \leq 0\).

Quick Reference

Case	Condition	Result
1	\(x \geq 0\)	\(|x| = x\)
2	\(x < 0\)	\(|x| = -x\)

Glossary

• Proof by Cases: A method where the hypothesis is divided into cases and the conclusion is proved in each.
• Mutually Exclusive Cases: Cases that do not overlap and cover all possibilities.

Indirect Proof Methods

Indirect proofs establish the truth of a statement by proving an equivalent or related statement, often by contradiction or contrapositive.

Proof by Contradiction

Assume the negation of the statement to be proved. If this assumption leads to a contradiction, the original statement is true.

Worked Illustration

Example 5: Prove that the set of all prime numbers is infinite.

Solution:

Assume the contrary: the set of prime numbers is finite, listed as \(P_1, P_2, \ldots, P_k\).

Consider:

\[ N = P_1 P_2 \cdots P_k + 1 \]

Since \(N\) is greater than any listed prime, it is either prime or composite.

• If \(N\) is prime, it is not in the list, contradiction.
• If \(N\) is composite, it has a prime divisor not in the list, contradiction.

Hence, the assumption is false, and there are infinitely many primes.

Proof by Contrapositive

To prove \(p \implies q\), prove its contrapositive \(~q \implies ~p\).

Worked Illustration

Example 6: Prove that the function \(f(x) = 2x + 5\) is one-one using contrapositive.

Solution:

Original statement: \(f(x_1) = f(x_2) \implies x_1 = x_2\).

Contrapositive: \(x_1 \neq x_2 \implies f(x_1) \neq f(x_2)\).

Assume \(x_1 \neq x_2\), then:

\[ 2x_1 + 5 \neq 2x_2 + 5 \]

Thus, \(f(x_1) \neq f(x_2)\), proving the contrapositive and hence the original statement.

Proof by Counterexample

To disprove a universal statement, provide a single example where the statement fails.

Worked Illustration

Example 8: Disprove the statement: "For each natural number \(n\), \(2^{2^n} + 1\) is prime."

Solution:

Check \(n=5\):

\[ 2^{2^5} + 1 = 2^{32} + 1 = 4294967297 \]

This number is composite since:

\[ 4294967297 = 641 \times 6700417 \]

Thus, the statement is false, and \(n=5\) is a counterexample.

Practice Set

• Use proof by contradiction to show \(\sqrt{2}\) is irrational.
• Prove by contrapositive: If \(x^2\) is even, then \(x\) is even.
• Find a counterexample to disprove: "All continuous functions are differentiable."

Answer Key

• Assume \(\sqrt{2}\) is rational, express as \(\frac{p}{q}\), derive contradiction on parity.
• Contrapositive: If \(x\) is odd, then \(x^2\) is odd; prove by direct calculation.
• Counterexample: \(f(x) = |x|\) is continuous but not differentiable at \(x=0\).

Quick Reference

Method	Description
Contradiction	Assume negation leads to contradiction
Contrapositive	Prove \(~q \implies ~p\) instead of \(p \implies q\)
Counterexample	Single example disproving a universal statement

Glossary

• Proof by Contradiction: Proving a statement by showing its negation leads to a contradiction.
• Contrapositive: The statement \(~q \implies ~p\) equivalent to \(p \implies q\).
• Counterexample: An example that disproves a universal statement.