Skip to main content

Contradiction and induction

Two more ways to settle a claim about infinitely many cases: suppose it false and reach the impossible, or climb from each case to the next. Prove that the square root of 2 is not a fraction and that the first n odd numbers add up to n squared, and see how induction shows a loop is correct.
M01.6.4L0 Foundation25 minIn review

Before this lesson

M01.6.3 Direct proof and counterexample

After this lesson you can

  • Set out a proof by contradiction, and prove in full that the square root of 2 is not a fraction.
  • State the two parts of a proof by induction, the base case and the step, and explain why each is needed.
  • Prove by induction that the first n odd numbers add up to n squared, and read the same fact off a picture of L-shaped layers.
  • Gather numerical evidence for both results in Python, and use induction to show that a loop computes what it should.

In review. The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

The question

Every fraction you try for \({\sqrt{2}}\) misses. \({7/5}\) squares to 1.96, \({141/100}\) to 1.9881, and \({99/70}\) to about 2.0002. Could a cleverer fraction land on 2 exactly? Trying fractions forever can never settle it. How can a few lines of reasoning settle a question about infinitely many cases?

From the last lesson

1. State the definition of an odd integer.

Show answer

An integer \({n}\) is odd if \({n = 2k + 1}\) for some integer \({k}\).

2. What does one counterexample do to a for-all claim?

Show answer

It disproves it. A claim about every case is false as soon as one case fails.

Intuition

The last lesson’s direct proof walked from what is given to what is wanted. This lesson adds two new shapes of proof, each for a job that a direct proof finds hard.

Two flowcharts side by side. On the left, titled proof by contradiction: a dashed box, suppose the claim is false; an arrow to justified steps; an arrow to a reddish-purple box, something impossible; and an arrow labelled the supposition fails to a vermillion box, so the claim is true. On the right, titled proof by induction: a blue box, base case, true for n equals 1; an arrow to a box, step, if true for k, then true for k plus 1, with a green loop arrow on its right side labelled k to k plus 1, again; and an arrow to a vermillion box, true for every n.
M01.6.4-F1

The two new shapes of proof. Contradiction follows a supposition until it breaks; induction uses one step over and over.

Contradiction. To show that a claim is true, suppose it is false and follow the supposition with justified steps. If you reach something impossible, such as a number that is both even and odd, the supposition must have been wrong, so the claim is true. A small example: there is no largest natural number. Suppose there were one, \({m}\). Then \({m + 1}\) is also a natural number, and it is larger than \({m}\), which is impossible. So no largest natural number exists.

Induction. To show that a statement holds for \({n = 1, 2, 3, \ldots}\), show two things: it holds for \({n = 1}\), and whenever it holds for one number it also holds for the next. Then it holds for 1, so for 2, so for 3, and on without end, like a row of dominoes.

Build it up

Step 1. The tool for \({\sqrt{2}}\). Lesson M01.6.3 proved: if \({n}\) is odd, then \({n^2}\) is odd. Its contrapositive says the same thing: if \({n^2}\) is not odd, then \({n}\) is not odd. Every integer is either even or odd, so “not odd” means “even”, and the contrapositive reads:

Lemma. If \({n^2}\) is even, then \({n}\) is even.

No new proof is needed: a contrapositive is equivalent to the statement it came from.

Step 2. Lowest terms. Any fraction can be reduced by dividing the top and the bottom by a common factor, again and again, until none is left: \({6/4 = 3/2}\). A fraction in lowest terms has a top and a bottom with no common factor bigger than 1. In particular they are not both even.

Step 3. The dominoes. Write \({S_n}\) for the statement about the number \({n}\). Proving \({S_1}\) knocks over the first domino. Proving “if \({S_k}\), then \({S_{k+1}}\)” for every \({k}\) places the dominoes so that each one, as it falls, knocks over the next.

A row of nine dominoes standing on a line, named S1 to S9 underneath, with dots after the last. A green arrow labelled base case, push the first, points at the first domino. The first four dominoes are green and tilted to the right, falling; the other five are grey and still standing. A curved green arrow from the fourth domino to the fifth carries the label step, each one that falls knocks over the next.
M01.6.4-F2

Induction as dominoes. The base case starts the fall; the step guarantees that it never stops.

Step 4. A claim worth proving. Add up the odd numbers, one at a time:

\[ \begin{aligned} 1 &= 1, \\ 1 + 3 &= 4, \\ 1 + 3 + 5 &= 9, \\ 1 + 3 + 5 + 7 &= 16. \end{aligned} \]

The totals are the squares \({1^2, 2^2, 3^2, 4^2}\). The \({n}\)-th odd number is \({2n - 1}\) (for \({n = 4}\) it is 7), so the pattern says that the sum of the first \({n}\) odd numbers is \({n^2}\). Four rows are only evidence. Induction will prove it for every \({n}\).

The formal statement

NoteTwo methods of proof

Proof by contradiction. To prove a statement, suppose it is false and deduce something impossible, such as a statement together with its negation. Then the statement is true.

Proof by induction. To prove statements \({S_1, S_2, S_3, \ldots}\), prove the base case \({S_1}\), and the step: for every natural number \({k}\), if \({S_k}\) is true then \({S_{k+1}}\) is true. Then every \({S_n}\) is true.

Theorem 1. \({\sqrt{2}}\) is not a fraction: there are no natural numbers \({p}\) and \({q}\) with \({\sqrt{2} = p/q}\). (Natural numbers are enough. \({\sqrt{2}}\) is positive, so a fraction of integers equal to it has a top and a bottom of the same sign, and dropping both signs keeps its value.)

Proof. Suppose, to reach a contradiction, that \({\sqrt{2} = p/q}\) for natural numbers \({p}\) and \({q}\), and reduce the fraction to lowest terms, so that \({p}\) and \({q}\) are not both even. Square both sides: \({2 = p^2/q^2}\). Multiply both sides by \({q^2}\):

\[ p^2 = 2q^2. \]

The right side is 2 times a natural number, so \({p^2}\) is even, and by the Lemma \({p}\) is even: \({p = 2k}\) for some natural number \({k}\). Put \({2k}\) in place of \({p}\):

\[ \begin{aligned} (2k)^2 &= 2q^2 \\ 4k^2 &= 2q^2 \\ 2k^2 &= q^2. \end{aligned} \]

The last line divides both sides by 2. So \({q^2}\) is 2 times a natural number, hence even, and by the Lemma again \({q}\) is even. Now \({p}\) and \({q}\) are both even, which contradicts lowest terms. The supposition was false, so \({\sqrt{2}}\) is not a fraction. \({\blacksquare}\)

A vertical flowchart of seven boxes. The top box, dashed and marked supposed, reads suppose the square root of 2 equals p over q, in lowest terms. Then: p squared equals 2 q squared; p squared is even, so p is even, p equals 2k; 4 k squared equals 2 q squared, so q squared equals 2 k squared; q squared is even, so q is even; a reddish-purple box, p and q are both even, marked impossible, not lowest terms; and a vermillion box, so the square root of 2 is not a fraction. The green arrows carry the reasons: square, then multiply by q squared; lemma, if n squared is even, so is n; put p equals 2k in, divide by 2; the lemma again; both share the factor 2; the supposition was false.
M01.6.4-F3

Theorem 1 as a flowchart. The supposition leads, step by justified step, to two numbers that are both even and share no factor 2.

Theorem 2. For every natural number \({n}\),

\[ 1 + 3 + 5 + \cdots + (2n - 1) = n^2. \]

The worked example proves it by induction.

Go deeper: why induction works: the smallest counterexample

Suppose the base case and the step are both proved, yet some \({S_n}\) is false. Among the false ones there is a smallest, say \({S_m}\), because every non-empty set of natural numbers has a smallest element. \({S_m}\) is not \({S_1}\), which the base case proved, so \({m \ge 2}\) and \({S_{m-1}}\) is true, being smaller than the smallest false one. But then the step, with \({k = m - 1}\), makes \({S_m}\) true: a contradiction. So every \({S_n}\) is true. Hammack calls this argument, turned into a method of its own, proof by smallest counterexample: “a hybrid of induction and proof by contradiction”.

Worked example

Prove Theorem 2 by induction, and check the step with numbers at \({k = 4}\).

Write \({S_n}\) for the statement that the first \({n}\) odd numbers add up to \({n^2}\):

\[ \begin{aligned} S_n: \quad &1 + 3 + 5 + \cdots + (2n - 1) \\ &\quad = n^2. \end{aligned} \]

Base case. For \({n = 1}\) the sum has a single term, \({2 \times 1 - 1 = 1}\), and \({1^2 = 1}\). So \({S_1}\) is true.

Step. Suppose that \({S_k}\) is true for some natural number \({k}\):

\[ 1 + 3 + 5 + \cdots + (2k - 1) = k^2. \]

The next odd number is number \({k + 1}\) in the list, \({2(k + 1) - 1}\), which is \({2k + 1}\). Add it to both sides, then use the expansion \({(a + b)^2}\) of M01.1.2 with \({a = k}\) and \({b = 1}\):

\[ \begin{aligned} &1 + 3 + \cdots + (2k - 1) + (2k + 1) \\ &\quad = k^2 + (2k + 1) \\ &\quad = (k + 1)^2. \end{aligned} \]

The left side is the sum of the first \({k + 1}\) odd numbers, so this is \({S_{k+1}}\). The step holds for every \({k}\), the base case holds, and so by induction \({S_n}\) is true for every natural number \({n}\). \({\blacksquare}\)

Check with numbers. At \({k = 4}\), \({S_4}\) says that the first four odd numbers add up to 16. The next odd number is \({2 \times 4 + 1 = 9}\), and 16 + 9 = 25, which is \({5^2}\): that is \({S_5}\).

Two square arrays of dots, five by five. On the left, titled each odd number adds one L, the 25 dots are grouped into five nested L-shapes, drawn alternately in dark blue and sky blue and labelled at the top of each arm with its count: 1, 3, 5, 7 and 9; below, 1 plus 3 plus 5 plus 7 plus 9 equals 25 equals 5 squared. On the right, titled the step from k equals 4 to k plus 1 equals 5, a four by four block of blue dots labelled k squared equals 16 is completed by a vermillion L of nine dots along the right side and the bottom, labelled 2k plus 1 equals 9 new; below, 16 plus 9 equals 25 equals 5 squared.
M01.6.4-F4

The worked-example trace. Each odd number is one more L around the square; the step adds the L of \({2k + 1}\) dots to a \({k}\) by \({k}\) square.

The picture is the same proof without symbols. A \({k}\) by \({k}\) square grows into a \({k + 1}\) by \({k + 1}\) square by adding one dot at the end of each of its \({k}\) rows, one more under each of its \({k}\) columns, and one in the corner. That is \({k + k + 1}\) dots, which is \({2k + 1}\), the next odd number.

Code

First, evidence about \({\sqrt{2}}\). If \({p/q}\) were \({\sqrt{2}}\), then \({p \times p}\) would equal \({2 \times q \times q}\). For each \({q}\) up to 1,000, math.isqrt gives the largest whole number whose square is at most \({2q^2}\); if any fraction worked, that number would be its \({p}\).

import math

found = []
near = []
# every bottom q from 1 to 1000
for q in range(1, 1001):
    target = 2 * q * q
    # root, rounded down
    p = math.isqrt(target)
    if p * p == target:
        found.append((p, q))
    # the whole numbers just
    # below and above the root
    for top in [p, p + 1]:
        miss = top * top - target
        if abs(miss) == 1:
            near.append((top, q))

print("p*p == 2*q*q:", found)
print("off by one:", near)
p*p == 2*q*q: []
off by one: [(1, 1), (3, 2), (7, 5), (17, 12), (41, 29), (99, 70), (239, 169), (577, 408), (1393, 985)]

No fraction with a bottom up to 1,000 works, and the best ones, such as \({99/70}\), miss by exactly 1 (\({9801}\) against \({9800}\)). Theorem 1 says why no search, however long, will ever find one.

Now the odd numbers, added by a loop. Each pass adds the next odd number and records whether the total is the square of the number of terms so far.

total = 0
holds = []
# k = 1, 2, ..., 100
for k in range(1, 101):
    # add the k-th odd number
    total = total + (2 * k - 1)
    # is S_k true?
    holds.append(total == k * k)
print("S_1 to S_100 hold:", all(holds))
print("first 100 add to:", total)

# 1 + 3 + ... + 199 by sum()
print(sum(range(1, 200, 2)))
S_1 to S_100 hold: True
first 100 add to: 10000
10000

A hundred checks are evidence. The loop itself, though, can be proved correct for every number of passes, and the proof is the induction of the worked example. The claim “after pass \({k}\), total is \({k^2}\)” holds after pass 1, since \({0 + 1 = 1}\). If it holds after pass \({k}\), pass \({k + 1}\) adds \({2k + 1}\) and leaves \({(k + 1)^2}\). So it holds after every pass. A claim like this, true before and after each pass of a loop, is called a loop invariant. Proving one by induction is how programmers show that a loop does what it should, and induction shows in the same way that a function that calls itself is correct.

Explore

The module’s Venn and truth-table explorer holds the picture of a contradiction. Clear every region: the set is empty, and its statement is true in no row. That is \({P \wedge \neg P}\), a statement together with its negation, which no element satisfies. Reaching it is what makes a supposition impossible.

Pitfalls

Two rows of nine dominoes named S1 to S9. The top row, marked with a cross and titled step, no base: 1 plus 3 plus and so on plus 2n minus 1 equals n squared plus 1, has every domino grey and standing; text on the left reads no push, S1 says 1 equals 2, and text above reads the step holds, yet nothing ever falls. The bottom row, marked with a tick and titled base and step: 1 plus 3 plus and so on plus 2n minus 1 equals n squared, has every domino green and tilted, with a green push arrow at the first one labelled S1, 1 equals 1.
M01.6.4-F5

Wrong beside right. The false formula \({n^2 + 1}\) passes the step but fails the base case, so none of its dominoes ever falls.

“The step works, so the formula is proved.”

Try the false formula

\[ \begin{aligned} &1 + 3 + \cdots + (2n - 1) \\ &\quad = n^2 + 1. \end{aligned} \]

Its step works: if the first \({k}\) odd numbers added to \({k^2 + 1}\), adding \({2k + 1}\) would give \({(k + 1)^2 + 1}\). But its base case says \({1 = 2}\). The step only passes truth along; the base case has to supply it.

“The decimals of \({\sqrt{2}}\) never repeat, so it is not a fraction.”

That is true, but nobody can see all the decimals, so it cannot be the reason. The order runs the other way: Theorem 1, proved by reasoning about \({p}\) and \({q}\), shows that \({\sqrt{2}}\) is not a fraction, and lesson M01.1.1 then tells us that its decimal neither stops nor repeats.

“The computer checked a million cases, so it is proved.”

A search up to 1,000, or a loop up to 100, covers finitely many cases. The claims are about all of them. The code is evidence that the proofs are worth trying, and a check on the algebra.

“Assuming \({S_k}\) in the step is circular.”

The step does not assume what it wants to prove. It assumes \({S_k}\) for one \({k}\) and derives \({S_{k+1}}\), the next statement. Only together with the base case does that cover every \({n}\).

Check yourself

Recall

1. What is the first line of a proof by contradiction?

Show answer

“Suppose the claim is false.” The rest of the proof follows that supposition to something impossible.

2. In the proof that \({\sqrt{2}}\) is not a fraction, why may we take \({p/q}\) in lowest terms?

Show answer

Any fraction can be reduced, by dividing top and bottom by common factors until none is left, without changing its value.

3. Which result of M01.6.3 does that proof use, and in what form?

Show answer

“If \({n}\) is odd, then \({n^2}\) is odd”, used as its contrapositive: if \({n^2}\) is even, then \({n}\) is even.

4. What two things does a proof by induction prove?

Show answer

The base case \({S_1}\), and the step: for every \({k}\), if \({S_k}\) is true then \({S_{k+1}}\) is true.

5. Why is checking Theorem 2 for every \({n}\) up to 100 not a proof of it?

Show answer

It covers only a hundred values of \({n}\), and the claim is about every natural number.

Exercises

1. ★ Use Theorem 2 to find the sum of the first 10 odd numbers, and say which odd number is the last one in that sum. Then check the step from \({k = 6}\) to \({k = 7}\) with numbers.

Show solution

The sum is \({10^2 = 100}\), and the last term is \({2 \times 10 - 1 = 19}\). For the step: the first six odd numbers add up to \({6^2 = 36}\), the next odd number is \({2 \times 6 + 1 = 13}\), and \({36 + 13 = 49}\), which is \({7^2}\).

2. ★★ Prove by induction that \({4^n - 1}\) is a multiple of 3 for every natural number \({n}\).

Show solution

Base case. For \({n = 1}\), \({4^1 - 1 = 3}\), which is a multiple of 3.

Step. Suppose \({4^k - 1 = 3m}\) for some whole number \({m}\). Then

\[ \begin{aligned} 4^{k+1} - 1 &= 4 \times 4^k - 1 \\ &= 4(4^k - 1) + 4 - 1 \\ &= 4 \times 3m + 3 \\ &= 3(4m + 1). \end{aligned} \]

The second line adds and takes away 4. Since \({4m + 1}\) is a whole number, \({4^{k+1} - 1}\) is a multiple of 3. By induction the claim holds for every \({n}\). (Check: \({4^2 - 1 = 15}\) and \({4^3 - 1 = 63}\), which are \({3 \times 5}\) and \({3 \times 21}\).) \({\blacksquare}\)

3. ★★★ Prove that \({\sqrt{3}}\) is not a fraction. First prove the lemma “if \({n^2}\) is a multiple of 3, then \({n}\) is a multiple of 3” through its contrapositive, using the fact that every integer that is not a multiple of 3 is \({3k + 1}\) or \({3k + 2}\) for some integer \({k}\).

Show solution

Lemma. The contrapositive is: if \({n}\) is not a multiple of 3, then neither is \({n^2}\). If \({n = 3k + 1}\), then

\[ \begin{aligned} n^2 &= 9k^2 + 6k + 1 \\ &= 3(3k^2 + 2k) + 1. \end{aligned} \]

If \({n = 3k + 2}\), then

\[ \begin{aligned} n^2 &= 9k^2 + 12k + 4 \\ &= 3(3k^2 + 4k + 1) + 1. \end{aligned} \]

Either way \({n^2}\) leaves remainder 1 on division by 3, so it is not a multiple of 3.

Theorem. Suppose \({\sqrt{3} = p/q}\) in lowest terms. Then \({p^2 = 3q^2}\), so \({p^2}\) is a multiple of 3, and by the lemma \({p = 3k}\). Then \({9k^2 = 3q^2}\), so \({q^2 = 3k^2}\), and by the lemma \({q}\) is a multiple of 3. Now \({p}\) and \({q}\) share the factor 3, which contradicts lowest terms. So \({\sqrt{3}}\) is not a fraction. \({\blacksquare}\)

Summary card

Contradiction follows a supposition until it breaks; induction proves a first case and a step.

The anchor figure again: on the left, the chain suppose the claim is false, justified steps, something impossible, so the claim is true; on the right, base case true for n equals 1, then the step if true for k then true for k plus 1 with a loop arrow, then true for every n.
M01.6.4-F1

Two new shapes of proof.

  • Contradiction: suppose the claim false, reach the impossible. \({\sqrt{2}}\) is not a fraction.
  • Induction: base case \({S_1}\), plus the step from \({S_k}\) to \({S_{k+1}}\) for every \({k}\).
  • Theorem 2: the first \({n}\) odd numbers add up to \({n^2}\), one L-shaped layer at a time.
  • Code: searches and loops give evidence; an invariant proved by induction shows a loop is correct.

Sources and next steps

Sources. Each was opened and checked against this lesson on 12 November 2026.

  • Richard Hammack, Book of Proof, third edition (free PDF). Section 5.1: the contrapositive as a way of proving an if-then, and Chapter 5, Exercise 1 (solved at the back): if \({n^2}\) is even, then \({n}\) is even. Section 6.1: the outline of a proof by contradiction, the definition of a rational number (Definition 6.1), and the proof that \({\sqrt{2}}\) is irrational from a fully reduced fraction. Chapter 10: the dominoes, and in Section 10.1 the outline of induction (basis step and inductive step) with the proof that the first \({n}\) odd numbers add up to \({n^2}\). Section 10.3: proof by smallest counterexample, “a hybrid of induction and proof by contradiction”.
  • Python Software Foundation, math.isqrt: the integer square root of a non-negative integer, the largest \({a}\) with \({a^2 \le n}\); added in Python 3.8.

Next. M01.7 meets these proofs again: lesson M01.7.3 confirms by induction its formula for the sum of the first \({n}\) natural numbers. M01.8 counts the elements of sets, among them the union of two overlapping sets.

This lesson unlocks

M01.7 Sums, products and sequences M01.8 Counting and combinatorics

Your progress is saved in this browser only. No account, no tracking.
Back to top