Class 12 PCM . Mathematics . Mathematics Part II . Proofs in Mathematics

Chapter 14: Proofs In Mathematics

Ch 14

Mathematics

Class 12 PCM

Lecture 1

Introduction

Reference video · Lecture 1Introduction

What Is a Mathematical Proof?

  • Proof: A sequence of statements, each justified by a definition, axiom, previously established proposition, or valid rule of logic.
  • Purpose: A proof uses deductive reasoning to establish that a mathematical proposition is true.

Direct Proof: Straightforward Approach

Worked example

Show that if x2−5x+6=0x^2-5x+6=0, then x=3x=3 or x=2x=2.

  1. Begin with the given equation.
    x2−5x+6=0x^2-5x+6=0
  2. Factor the quadratic expression.
    (x−3)(x−2)=0(x-3)(x-2)=0
  3. Use the zero-product property.
    x−3=0orx−2=0x-3=0 \quad \text{or} \quad x-2=0
  4. Solve each resulting equation.
    x=3orx=2x=3 \quad \text{or} \quad x=2
Answer: The equation implies x=3x=3 or x=2x=2.

Mathematical Induction

Worked example

Prove by induction that An=[cos⁡nθsin⁡nθ−sin⁡nθcos⁡nθ]A^n=\begin{bmatrix}\cos n\theta&\sin n\theta\\-\sin n\theta&\cos n\theta\end{bmatrix} for A=[cos⁡θsin⁡θ−sin⁡θcos⁡θ]A=\begin{bmatrix}\cos\theta&\sin\theta\\-\sin\theta&\cos\theta\end{bmatrix} and all n≥1n\ge1.

  1. Define the matrix and the proposition to be proved.
    A=[cos⁡θsin⁡θ−sin⁡θcos⁡θ],P(n): An=[cos⁡nθsin⁡nθ−sin⁡nθcos⁡nθ]A=\begin{bmatrix}\cos\theta&\sin\theta\\-\sin\theta&\cos\theta\end{bmatrix},\qquad P(n):\ A^n=\begin{bmatrix}\cos n\theta&\sin n\theta\\-\sin n\theta&\cos n\theta\end{bmatrix}
  2. Check the base case.
    A1=[cos⁡θsin⁡θ−sin⁡θcos⁡θ]A^1=\begin{bmatrix}\cos\theta&\sin\theta\\-\sin\theta&\cos\theta\end{bmatrix}
  3. Assume the proposition is true for an integer k≥1k\ge1.
    Ak=[cos⁡kθsin⁡kθ−sin⁡kθcos⁡kθ]A^k=\begin{bmatrix}\cos k\theta&\sin k\theta\\-\sin k\theta&\cos k\theta\end{bmatrix}
  4. Multiply the assumed expression by AA to obtain the next power.
    Ak+1=AkA=[cos⁡kθcos⁡θ−sin⁡kθsin⁡θcos⁡kθsin⁡θ+sin⁡kθcos⁡θ−sin⁡kθcos⁡θ−cos⁡kθsin⁡θ−sin⁡kθsin⁡θ+cos⁡kθcos⁡θ]A^{k+1}=A^kA=\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}
  5. Apply the angle-addition identities to obtain the required form for k+1k+1.
    Ak+1=[cos⁡((k+1)θ)sin⁡((k+1)θ)−sin⁡((k+1)θ)cos⁡((k+1)θ)]A^{k+1}=\begin{bmatrix}\cos((k+1)\theta)&\sin((k+1)\theta)\\-\sin((k+1)\theta)&\cos((k+1)\theta)\end{bmatrix}
  6. The base case and inductive step establish the result for every integer n≥1n\ge1.
    ∀n≥1,An=[cos⁡nθsin⁡nθ−sin⁡nθcos⁡nθ]\forall n\ge1,\quad A^n=\begin{bmatrix}\cos n\theta&\sin n\theta\\-\sin n\theta&\cos n\theta\end{bmatrix}
Answer: The formula holds at n=1n=1. Assuming it holds at kk, multiplication by AA gives the stated matrix with n=k+1n=k+1, by the angle-addition identities. Hence it holds for all n≥1n\ge1 by induction.
Practice

Prove directly that if x2−7x+12=0x^2-7x+12=0, then x=3x=3 or x=4x=4.

Hint: Factor the quadratic and use the zero-product property.
Key step: x2−7x+12=(x−3)(x−4)x^2-7x+12=(x-3)(x-4).
Solution: From (x−3)(x−4)=0(x-3)(x-4)=0, either x−3=0x-3=0 or x−4=0x-4=0. Thus x=3x=3 or x=4x=4.
Practice

Prove by induction that 1+2+⋯+n=n(n+1)21+2+\cdots+n=\frac{n(n+1)}{2} for every integer n≥1n\ge1.

Hint: Check n=1n=1, then add k+1k+1 to the assumed sum for kk.
Key step: From the induction hypothesis, add k+1k+1 and simplify to (k+1)(k+2)2\frac{(k+1)(k+2)}{2}.
Solution: At n=1n=1, both sides equal 11. Assume 1+2+⋯+k=k(k+1)21+2+\cdots+k=\frac{k(k+1)}{2}. Then 1+2+⋯+k+(k+1)=k(k+1)2+k+1=(k+1)(k+2)21+2+\cdots+k+(k+1)=\frac{k(k+1)}{2}+k+1=\frac{(k+1)(k+2)}{2}. Therefore the formula holds for all n≥1n\ge1.

Quick recap

  • A proof is a chain of deductions justified by logic, definitions, axioms, or established results.
  • A direct proof begins with the given information and proceeds to the conclusion.
  • Equivalent expressions may replace one another in a proof.
  • Induction requires a true base case and a valid step from P(k)P(k) to P(k+1)P(k+1).
  • Once both induction conditions hold, P(n)P(n) is true for every integer nn in the stated range.
Lecture 2

Proof By Cases Or By Exhaustion

Reference video · Lecture 2Proof By Cases Or By Exhaustion

Proof by Cases or by Exhaustion

Proof by cases

If pp is equivalent to the disjunction of exhaustive cases r1,r2,ldots,rnr_1,r_2, ldots,r_n, and each case implies qq, then pp implies qq.

p≡r1∨r2∨⋯∨rn,ri⇒q (1≤i≤n)⟹p⇒qp\equiv r_1\lor r_2\lor\cdots\lor r_n,\qquad r_i\Rightarrow q\ (1\le i\le n)\quad\Longrightarrow\quad p\Rightarrow q

How to prove by cases

  1. List cases that together cover every possibility in the hypothesis.
    p≡r1∨r2∨⋯∨rnp\equiv r_1\lor r_2\lor\cdots\lor r_n
  2. Prove the conclusion separately under each case.
    ri⇒q(1≤i≤n)r_i\Rightarrow q\quad (1\le i\le n)
  3. Conclude that the original hypothesis implies the conclusion.
    p⇒qp\Rightarrow q
Projection identity in a triangle
a=bcos⁡C+ccos⁡Ba=b\cos C+c\cos B

For triangle ABCABC, let a=BCa=BC, b=CAb=CA, and c=ABc=AB.

Worked example

Show that for any triangle ABCABC, a=bcos⁡C+ccos⁡Ba=b\cos C+c\cos B.

  1. Drop a perpendicular from AA to the line BCBC, meeting it at DD. Treat distances along BCBC as directed, so distances opposite the direction from BB to CC are negative.
    BD=ccos⁡B,DC=bcos⁡CBD=c\cos B,\qquad DC=b\cos C
  2. If CC is acute, DCDC is positive; BDBD may be negative if BB is obtuse. The directed lengths still add to BCBC.
    a=BD+DC=ccos⁡B+bcos⁡Ca=BD+DC=c\cos B+b\cos C
  3. If CC is obtuse, the foot lies beyond CC, so DCDC is negative; adding the directed lengths gives the same identity.
    a=BD+DC=ccos⁡B+bcos⁡Ca=BD+DC=c\cos B+b\cos C
  4. If CC is right, D=CD=C, so DC=0DC=0 and the identity follows.
    a=BD=ccos⁡B,bcos⁡C=0a=BD=c\cos B,\qquad b\cos C=0
  5. These cases cover all possible values of angle CC, proving the result for every triangle.
    a=bcos⁡C+ccos⁡Ba=b\cos C+c\cos B
Answer: a=bcos⁡C+ccos⁡Ba=b\cos C+c\cos B.
⚠ Common mistake

Do not assume the perpendicular foot lies on segment BCBC, or use only positive lengths in every case. Directed projections account for a foot outside the segment.

Indirect Proof

  • Indirect proof: Establishes a proposition by proving an equivalent statement rather than starting directly from the given hypothesis.
  • Methods: Indirect proofs include several approaches for showing that the required conclusion follows logically.

Proof by Contradiction

Worked example

Prove that the set of all prime numbers is infinite.

  1. Assume, for contradiction, that there are only finitely many primes, listed as p1,p2,…,pkp_1,p_2,\ldots,p_k.
    P={p1,p2,…,pk}P=\{p_1,p_2,\ldots,p_k\}
  2. Multiply the listed primes and add one to form NN.
    N=p1p2⋯pk+1N=p_1p_2\cdots p_k+1
  3. Every listed prime leaves remainder one when dividing NN, so none divides NN.
    N≡1(modpi)(1≤i≤k)N\equiv 1\pmod{p_i}\quad (1\le i\le k)
  4. If NN is prime, it is absent from the list. If NN is composite, it has a prime divisor absent from the list.
    N is prime or compositeN\text{ is prime or composite}
  5. Both possibilities contradict the claim that the list contains all primes; therefore there are infinitely many primes.
    ∣P∣ is infinite|P|\text{ is infinite}
Answer: The assumption that there are finitely many primes leads to a contradiction. Hence, there are infinitely many primes.

Contradiction can use cases

  • Two cases: In the prime proof, NN is either prime or composite.
  • Conclusion: Each possibility contradicts the assumption that all primes were listed.

Proof by Contrapositive

Conditional and contrapositive

A conditional statement is logically equivalent to its contrapositive.

p⇒q⟺¬q⇒¬pp\Rightarrow q\quad\Longleftrightarrow\quad \neg q\Rightarrow\neg p

When to use the contrapositive

  • Strategy: Prove the contrapositive when it is easier than proving the original conditional.
  • One-one test: A function is one-one if equal outputs imply equal inputs.
One-one condition
f(x1)=f(x2)⇒x1=x2f(x_1)=f(x_2)\Rightarrow x_1=x_2

Equal outputs of a one-one function must come from equal inputs.

Worked example

Prove that f(x)=2x+5f(x)=2x+5 is one-one on R\mathbb{R} using the contrapositive.

  1. For f:R→Rf:\mathbb{R}\to\mathbb{R} defined by f(x)=2x+5f(x)=2x+5, prove one-one by proving the contrapositive.
    x1≠x2⇒f(x1)≠f(x2)x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2)
  2. Multiplication by the nonzero number 22 preserves inequality.
    x1≠x2⇒2x1≠2x2x_1\ne x_2\Rightarrow 2x_1\ne 2x_2
  3. Adding 55 preserves inequality, so the function values differ.
    2x1+5≠2x2+52x_1+5\ne 2x_2+5
  4. This proves the contrapositive of equal outputs implying equal inputs; hence ff is one-one.
    x1≠x2⇒f(x1)≠f(x2)x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2)
Answer: ff is one-one on R\mathbb{R}.

Matrix application

  • Claim: If a matrix AA is invertible, then it is non-singular.
  • Contrapositive: If AA is singular, then it is not invertible.
  • Reason: Singularity means ∣A∣=0|A|=0; thus the inverse formula A−1=adj⁡A∣A∣A^{-1}=\dfrac{\operatorname{adj}A}{|A|} cannot define an inverse.

Disproof by Counterexample

Worked example

Disprove the statement “Every continuous function is differentiable.”

  1. Consider the claim that every continuous function is differentiable.
    ∀f  (f continuous⇒f differentiable)\forall f\; (f\text{ continuous}\Rightarrow f\text{ differentiable})
  2. The function ϕ(x)=∣x∣\phi(x)=|x| is continuous everywhere.
    ϕ(x)=∣x∣\phi(x)=|x|
  3. At x=0x=0, its left and right derivatives differ, so it is not differentiable there.
    ϕ−′(0)=−1,ϕ+′(0)=1\phi'_-(0)=-1,\qquad \phi'_+(0)=1
  4. Thus ∣x∣|x| is a counterexample and the universal claim is false.
    ϕ−′(0)≠ϕ+′(0)\phi'_-(0)\ne\phi'_+(0)
Answer: The statement is false: ϕ(x)=∣x∣\phi(x)=|x| is continuous but not differentiable at x=0x=0.

Another counterexample

  • Claim: 22n+12^{2^n}+1 is prime for every natural number nn.
  • Small cases: For n=1,2,3n=1,2,3, the values are 5,17,2575,17,257, all prime; these examples do not prove the general claim.
  • Counterexample: For n=5n=5, 225+1=232+1=4294967297=641×67004172^{2^5}+1=2^{32}+1=4294967297=641\times6700417, which is composite.
Practice

Prove by contrapositive: if n2n^2 is even for an integer nn, then nn is even.

Hint: Assume nn is odd and show that n2n^2 is odd.
Key step: Write an odd integer as n=2k+1n=2k+1 for some integer kk.
Solution: If n=2k+1n=2k+1, then n2=4k2+4k+1=2(2k2+2k)+1n^2=4k^2+4k+1=2(2k^2+2k)+1, which is odd. Thus the contrapositive holds, so if n2n^2 is even, nn is even.
Practice

Disprove the claim that n2+n+41n^2+n+41 is prime for every integer nn.

Hint: Test n=41n=41.
Key step: Substitute n=41n=41 and factor the result.
Solution: For n=41n=41, n2+n+41=412+41+41=41×43n^2+n+41=41^2+41+41=41\times43, which is composite. Thus n=41n=41 is a counterexample.

Quick recap

  • Proof by cases requires exhaustive possibilities, with the conclusion proved in every case.
  • Directed projections prove the triangle identity even when the perpendicular foot lies outside the side segment.
  • Proof by contradiction assumes the claim is false and derives an impossibility.
  • A conditional p⇒qp\Rightarrow q is equivalent to its contrapositive ¬q⇒¬p\neg q\Rightarrow\neg p.
  • For a one-one function, equal outputs imply equal inputs.
  • One valid counterexample disproves a universal statement.
  • Examples supporting a general claim do not establish that it is always true.

Formula sheet

Projection identity in a triangle
a=bcos⁡C+ccos⁡Ba=b\cos C+c\cos B
One-one condition
f(x1)=f(x2)⇒x1=x2f(x_1)=f(x_2)\Rightarrow x_1=x_2

Mathematics — ALL CHAPTERS

1

Relations And Functions

View

2

Inverse Trigonometric Functions

View

3

Matrices

View

4

DETERMINANTS 

View

5

Continuity And Differentiability

View

6

Application Of Derivatives

View

7

Integrals

View

8

APPLICATION OF INTEGRALS

View

9

DIFFERENTIAL EQUATIONS

View

10

VECTOR ALGEBRA

View

11

Three Dimensional Geometry

View

12

Linear Programming

View

13

Probability

View

14

Proofs In Mathematics

View

15

Mathematical Modelling

View