Mathematical Proof Techniques — Direct, Contradiction, Induction

A proof is not just a formality — it is how mathematicians (and top students) know something is true, not just believe it. Learning proof techniques transforms you from someone who memorizes formulas to someone who understands why they work.

This matters directly in exams: CBSE Class 11’s “Mathematical Reasoning” chapter, JEE’s number theory questions, and any problem where you’re asked to “prove” or “show” a result. Beyond exams, proof thinking sharpens logical reasoning in every subject.

We’ll cover three core techniques: direct proof, proof by contradiction, and mathematical induction. Each has its place, and knowing which to use is itself a skill.

Key Terms and Definitions

Proposition: A statement that is either true or false. Example: “The sum of two odd numbers is even.”

Theorem: A proposition that has been proved using logic from axioms or other theorems.

Axiom (postulate): A statement assumed to be true without proof (the starting point). Example: Euclid’s parallel postulate.

Conjecture: A statement believed to be true but not yet proved. (Goldbach’s conjecture is famous: every even number greater than 2 is the sum of two primes — unproved since 1742.)

Corollary: A result that follows immediately from a theorem with little additional proof needed.

Lemma: A helper result proved specifically to be used in proving a bigger theorem.

Counterexample: A single specific case that shows a statement is false. One counterexample kills a claim instantly.

Method 1: Direct Proof

How it works

Start with what you know (hypotheses, definitions), apply logical steps, and arrive at what you want to prove. This is the most natural approach.

Structure

Assume the hypothesis (the “if” part) is true
Apply definitions, theorems, or algebra
Arrive at the conclusion (the “then” part)

Worked Example (Easy — CBSE Level)

Prove: The sum of two even integers is even.

Proof: Let $a$ and $b$ be even integers. By definition of even, there exist integers $m$ and $n$ such that $a = 2m$ and $b = 2n$ .

Then $a + b = 2m + 2n = 2(m + n)$ .

Since $m + n$ is an integer (integers are closed under addition), $a + b = 2(m+n)$ has 2 as a factor. By definition, $a + b$ is even. $\square$

Worked Example (Medium — JEE Level)

Prove: If $n$ is odd, then $n^2$ is odd.

Proof: Let $n$ be odd. Then $n = 2k + 1$ for some integer $k$ .

$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

Since $2k^2 + 2k$ is an integer, $n^2 = 2(\text{integer}) + 1$ has the form $2m + 1$ — by definition, $n^2$ is odd. $\square$

In direct proofs of statements about integers (even, odd, divisibility), the first step is almost always: “Let [variable] = $2k$ ” (if even) or " $2k+1$ " (if odd) or " $2k$ " or " $3k$ " (if divisible by 2 or 3). This algebraic representation is the key to making abstract properties concrete.

Method 2: Proof by Contradiction

How it works

Assume the opposite of what you want to prove. Then show that this assumption leads to a logical contradiction (something known to be false, or two statements that can’t both be true). Since the assumption led to a contradiction, the assumption must be false — so the original statement must be true.

Structure

Assume the negation of the conclusion
Derive logical consequences
Reach a contradiction
Conclude the original statement is true

Worked Example (Classic — All Levels)

Prove: $\sqrt{2}$ is irrational.

Proof (by contradiction):

Assume $\sqrt{2}$ is rational. Then $\sqrt{2} = \frac{p}{q}$ where $p, q$ are integers with $\gcd(p,q) = 1$ (the fraction is in lowest terms).

Squaring: $2 = \frac{p^2}{q^2}$ , so $p^2 = 2q^2$ .

This means $p^2$ is even. Since the square of an odd number is odd (proved above), $p$ must be even. Write $p = 2m$ .

Then $(2m)^2 = 2q^2 \Rightarrow 4m^2 = 2q^2 \Rightarrow q^2 = 2m^2$ .

So $q^2$ is even, meaning $q$ is even.

But now both $p$ and $q$ are even — this contradicts our assumption that $\gcd(p,q) = 1$ .

This contradiction shows our assumption was wrong. Therefore $\sqrt{2}$ is irrational. $\square$

Worked Example (JEE Style)

Prove: There are infinitely many prime numbers.

Proof (by contradiction — Euclid’s classic proof):

Assume there are finitely many primes: $p_1, p_2, \ldots, p_n$ .

Consider $N = p_1 \cdot p_2 \cdots p_n + 1$ .

$N$ is either prime or composite. If prime, it’s a new prime not in our list — contradiction.

If composite, it must be divisible by some prime $p_i$ in our list. But $N = p_1 p_2 \cdots p_n + 1$ , so when divided by any $p_i$ , the remainder is 1. So $p_i$ does not divide $N$ — contradiction.

Either way, we reach a contradiction. So there are infinitely many primes. $\square$

Contradiction proofs are ideal when the direct approach isn’t obvious, and especially when you’re proving something doesn’t exist or can’t happen. If a statement says “prove $X$ is irrational” or “prove no solution exists,” think contradiction first.

Method 3: Mathematical Induction

How it works

Used to prove statements of the form “P(n) is true for all positive integers $n$ ” (or for $n \geq$ some starting value). Think of it like toppling dominoes: if the first one falls, and each falling domino knocks over the next, all dominoes will eventually fall.

Structure (Two Steps)

Base case: Prove P(1) is true (or P(0), P(2), etc., depending on where the statement starts).

Inductive step: Assume P(k) is true for some arbitrary $k \geq 1$ (this is the induction hypothesis). Then prove P(k+1) is true.

Conclusion: P(n) is true for all $n \geq 1$ .

Worked Example (CBSE/JEE Classic)

Prove: $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ for all positive integers $n$ .

Base case: For $n = 1$ : LHS = 1, RHS = $\frac{1 \times 2}{2} = 1$ . LHS = RHS. ✓

Inductive step: Assume $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$ (induction hypothesis).

We need to prove: $1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}$

LHS = $[1 + 2 + \cdots + k] + (k+1)$

$= \frac{k(k+1)}{2} + (k+1)$ [using induction hypothesis]

$= (k+1)\left[\frac{k}{2} + 1\right]$

$= (k+1) \cdot \frac{k+2}{2}$

$= \frac{(k+1)(k+2)}{2}$ = RHS ✓

By the principle of mathematical induction, the formula holds for all positive integers $n$ . $\square$

Worked Example (Harder — JEE)

Prove: $2^n > n$ for all positive integers $n$ .

Base case: $n=1$ : $2^1 = 2 > 1$ . ✓

Inductive step: Assume $2^k > k$ .

We want to show $2^{k+1} > k+1$ .

$2^{k+1} = 2 \cdot 2^k > 2k$ (using induction hypothesis, since $2^k > k$ implies $2 \cdot 2^k > 2k$ )

We need $2k \geq k+1$ , i.e., $k \geq 1$ . This is true for all $k \geq 1$ .

So $2^{k+1} > 2k \geq k+1$ . ✓

By induction, $2^n > n$ for all $n \geq 1$ . $\square$

In JEE Main, induction problems appear with sum formulas (like the one above), inequalities ( $2^n > n^2$ for large $n$ ), and divisibility (prove $n^3 - n$ is divisible by 6 for all $n$ ). The inductive step is where most marks are given — clearly state the induction hypothesis, then explicitly use it. Writing “By induction hypothesis” is mandatory in board exams.

Solved Examples

Example 1 (Easy — CBSE)

Prove: The product of two consecutive integers is always even.

Proof: Let the consecutive integers be $n$ and $n+1$ . Either $n$ is even or $n+1$ is even (consecutive integers alternate parity). So their product $n(n+1)$ includes an even factor, hence is even. $\square$

Example 2 (Medium — CBSE 12)

Prove by induction: $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$

Proof: Base case $n=1$ : LHS = 1, RHS = $\frac{1 \cdot 2 \cdot 3}{6} = 1$ . ✓

Assume true for $n = k$ : $\sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}$

For $n = k+1$ : $\sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$

$= \frac{(k+1)[k(2k+1) + 6(k+1)]}{6} = \frac{(k+1)(2k^2 + 7k + 6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$

This matches the formula with $n = k+1$ . $\square$

Example 3 (Hard — JEE Main)

Prove: $\sqrt{3}$ is irrational.

Proof (by contradiction): Assume $\sqrt{3} = p/q$ in lowest terms. Then $p^2 = 3q^2$ , so 3 divides $p^2$ . Since 3 is prime, 3 divides $p$ . Write $p = 3m$ . Then $9m^2 = 3q^2$ , so $q^2 = 3m^2$ , meaning 3 divides $q$ . But then $\gcd(p,q) \geq 3$ , contradicting lowest terms. $\square$

Exam-Specific Tips

CBSE Class 11: The Principle of Mathematical Induction is an entire chapter (Chapter 4). Typically 2-4 questions appear in exams: one sum formula, one divisibility, and sometimes an inequality. Practice the write-up structure — “Base case: … Inductive step: Assume P(k)… We prove P(k+1)…” — because marks are given for correct structure, not just the final algebraic manipulation.

JEE Main: Proofs appear indirectly — induction in Number Theory, contradiction in problems about irrationals or limits of sequences. A solid understanding of why these techniques work helps you construct answers rather than guess.

For all exams: When asked to “prove,” never just verify with examples. Checking that a statement works for $n = 1, 2, 3$ is NOT a proof. You must use a valid proof technique.

Common Mistakes to Avoid

Mistake 1 (Induction): Proving the base case but writing a circular inductive step — assuming what you want to prove. The induction hypothesis (P(k) is true) is your tool; you must use it explicitly to prove P(k+1). If you never mention or use the induction hypothesis in the inductive step, your proof is invalid.

Mistake 2 (Contradiction): Not clearly identifying what is being contradicted. At the end of a contradiction proof, explicitly state: “This contradicts [X]. Therefore our assumption was false.” Don’t leave the reader (examiner) guessing what the contradiction is.

Mistake 3 (Direct Proof): Using specific numbers instead of general variables. If you prove “the sum of two even numbers is even” by checking $2 + 4 = 6$ , that’s not a proof. You need to show it works for any even numbers using variables $a = 2m$ and $b = 2n$ .

Mistake 4 (All types): Confusing “or” with “and” in logic. “A or B” means at least one is true. “A and B” means both are true. Many proof errors stem from this logical imprecision.

Mistake 5: Assuming the converse. If “P implies Q” is true, it does NOT follow that “Q implies P.” This is a fundamental logical error. “If $n$ is even, then $n^2$ is even” (true) does not immediately give you “If $n^2$ is even, then $n$ is even” (which also happens to be true, but requires a separate proof — specifically by contradiction).

Practice Questions

Q1: Prove that the sum of two odd integers is always even.

Let $a = 2m+1$ and $b = 2n+1$ be odd integers. Then $a + b = 2m + 1 + 2n + 1 = 2m + 2n + 2 = 2(m+n+1)$ . Since $m+n+1$ is an integer, $a+b$ is divisible by 2, hence even. $\square$

Q2: Prove by induction: $1 + 3 + 5 + \cdots + (2n-1) = n^2$ .

Base case: $n=1$ : LHS = 1, RHS = $1^2 = 1$ . ✓

Inductive step: Assume $1 + 3 + \cdots + (2k-1) = k^2$ . Then:

$1 + 3 + \cdots + (2k-1) + (2k+1) = k^2 + (2k+1) = k^2 + 2k + 1 = (k+1)^2$

This is the formula for $n = k+1$ . By induction, the result holds for all $n \geq 1$ . $\square$

Q3: Prove that $\sqrt{5}$ is irrational.

Assume $\sqrt{5} = p/q$ (in lowest terms). Then $p^2 = 5q^2$ . So 5 divides $p^2$ . Since 5 is prime, 5 divides $p$ . Let $p = 5m$ . Then $25m^2 = 5q^2 \Rightarrow q^2 = 5m^2$ . So 5 divides $q$ . But then both $p$ and $q$ are divisible by 5, contradicting $\gcd(p,q) = 1$ . Hence $\sqrt{5}$ is irrational. $\square$

Q4: Prove by induction: $n^3 + 2n$ is divisible by 3 for all positive integers $n$ .

Base case: $n=1$ : $1 + 2 = 3$ , divisible by 3. ✓

Inductive step: Assume $k^3 + 2k = 3m$ for some integer $m$ .

$(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2$

$= (k^3 + 2k) + 3k^2 + 3k + 3 = 3m + 3(k^2 + k + 1)$

$= 3(m + k^2 + k + 1)$

This is divisible by 3. By induction, $n^3 + 2n$ is divisible by 3 for all $n \geq 1$ . $\square$

Q5: Give a counterexample to disprove: “All prime numbers are odd.”

Counterexample: $p = 2$ . The number 2 is prime (divisible only by 1 and itself), but $2$ is even, not odd. One counterexample is sufficient to disprove a universal claim.

FAQs

Q: When should I use direct proof vs contradiction?

Use direct proof when the statement is of the form “If P, then Q” and you can naturally chain from P to Q using algebra or known facts. Use contradiction when direct proof isn’t obvious, when proving something doesn’t exist, or when you’re proving something is irrational/impossible. A useful heuristic: if you struggle with direct proof for more than 2 minutes, try contradiction.

Q: What does $\square$ mean at the end of a proof?

The symbol $\square$ (sometimes written QED, from Latin “quod erat demonstrandum” — “which was to be demonstrated”) marks the end of a proof. It tells the reader you’ve finished the argument. Always include it in your written proofs — in board exams, it signals completion.

Q: Why can’t I just verify with examples?

Verification checks finitely many cases; mathematics requires certainty for all cases (often infinitely many). The statement “2n + 1 is prime for all n” might seem true for $n = 1$ (3), $n = 2$ (5), $n = 3$ (7), $n = 4$ (9)… wait, $9 = 3 \times 3$ is not prime. One failed example destroys the claim. Conversely, no number of successful examples proves a general statement.

Q: Is strong induction different from regular induction?

Strong induction assumes P(1), P(2), …, P(k) are all true and uses this to prove P(k+1). Regular induction only assumes P(k). Strong induction is needed when proving P(k+1) requires information from cases before just k. For example, proving every integer greater than 1 can be factored into primes requires strong induction.

Q: Does mathematical induction work for all types of mathematical statements?

No — induction works specifically for statements indexed by natural numbers ( $n = 1, 2, 3, \ldots$ ). For statements about all real numbers, or all continuous functions, or geometric claims, other methods (direct proof, contradiction, analysis) are needed.