Proofs Examples: 46 Problems with Answers

Worked examples of Proofs to try before you open each solution, then practice problems with answers.

Worked Examples

Example 1

easy
Prove directly: The sum of two even integers is even.
Show solution

Answer

a+b=2(m+n) is even.

First step

1.
Let a and b be even integers. By definition, a=2m and b=2n for some integers m,n.

Full solution

  1. 2.
    Then a+b=2m+2n=2(m+n).
  2. 3.
    Since m+n is an integer, a+b=2(m+n) is even by definition.
A direct proof starts from the hypothesis, applies definitions and algebra, and arrives at the conclusion. Translating 'even' into 2k is a standard first step.

Example 2

medium
Prove directly: For any integer n, if n is odd then n2 is odd.

Example 3

medium
Prove by contradiction: there is no largest integer.

Example 4

medium
Prove by contrapositive: if n2 is even, then n is even.

Example 5

medium
Prove: if m and n are both perfect squares, then mn is a perfect square.

Example 6

hard
Prove by contradiction that 2 is irrational.

Example 7

medium
Prove by induction: 1+2+⋯+n=n(n+1)2.

Example 8

medium
Prove: if a∣b, then a∣bc for every integer c.

Example 9

hard
Prove by cases: for any integer n, n2 has remainder 0 or 1 when divided by 4.

Example 10

medium
Prove: the sum of three consecutive integers is divisible by 3.

Example 11

hard
Prove by induction: 2n>n for all n≥1.

Example 12

medium
Prove: if a,b are rational, then a+b is rational.

Example 13

hard
Prove: there are infinitely many primes (Euclid's argument).

Example 14

challenge
Prove: for any natural number n, n3−n is divisible by 6.

Practice Problems

Try each one, then open the solution to compare your method.

Example 1

medium
Prove: The product of two odd integers is odd.

Example 2

medium
Prove directly: if n is even, then n+1 is odd.

Example 3

easy
In a proof, what are the two things you must clearly identify before reasoning?

Example 4

easy
Prove directly: if n is even, then n+2 is even.

Example 5

easy
What is wrong with proving 'x=2' by writing 'assume x=2, then x=2'?

Example 6

easy
Prove: the sum of two odd numbers is even.

Example 7

easy
Which is a valid proof of '∀n, 2n is even': (A) test n=1,2,3; (B) write 2n=2⋅n?

Example 8

easy
In a proof, what role does an axiom play?

Example 9

easy
Prove: if a∣b and a∣c, then a∣(b+c).

Example 10

easy
What does 'it is obvious' hide in a proof?

Example 11

medium
Prove: if n2 is even, then n is even (use contrapositive).

Example 12

medium
Prove: for all integers n, n2+n is even.

Example 13

medium
Prove: if x is rational and y is irrational, then x+y is irrational.

Example 14

medium
What is the converse of 'if it rains, the ground is wet', and is it always true?

Example 15

medium
Prove: the sum of the first n odd numbers equals n2 — outline the method that fits best.

Example 16

medium
Identify the flaw: 'Let a=b. Then a2=ab, a2−b2=ab−b2, (a+b)(a−b)=b(a−b), so a+b=b, thus 2b=b.'

Example 17

medium
Prove: if a<b then a<a+b2<b.

Example 18

medium
State what makes a proof 'valid' versus merely 'persuasive'.

Example 19

medium
Prove: if a and b are both odd, then ab is odd.

Example 20

challenge
Prove: there are infinitely many primes (outline Euclid's argument).

Example 21

challenge
Prove by strong induction: every integer n≥2 has a prime factor.

Example 22

challenge
Prove: for any sets, A⊆B if and only if A∩B=A.

Example 23

easy
In a direct proof of 'if P then Q', what do you assume at the start?

Example 24

easy
What is one counterexample sufficient to disprove?

Example 25

medium
Disprove by counterexample: 'For all integers n, n2>n.'

Example 26

easy
True or false: a proof by example (showing the statement holds for n=1,2,3) proves the universal statement ∀n.

Example 27

medium
Prove: if n is an integer, then n2+n is even.

Example 28

medium
Prove: an integer n is even if and only if n+2 is even.

Example 29

easy
What name do we give a statement that has been proven from axioms?

Example 30

medium
Identify the flaw: 'Proof that all horses are the same color: by induction on the size of a group of horses.'

Example 31

easy
True or false: a single example proves a universal claim.

Example 32

medium
Disprove: 'For all primes p, 2p−1 is prime.'

What to focus on

Core idea: A proof is a rigorous chain of valid inferences from accepted axioms to a guaranteed conclusion.

Common stuck point: The procedure for proofs is the easy part; the trap is treating confirming examples as a proof. Asking "Does my argument guarantee the claim for EVERY case via valid inference, not just confirm examples?" first is what keeps a correct-looking calculation from being attached to the wrong concept.

Ask yourself: Does my argument guarantee the claim for EVERY case via valid inference, not just confirm examples?

Concept recap

A mathematical proof is a rigorous logical argument that demonstrates the truth of a statement beyond doubt, proceeding from accepted axioms and previously proven results through valid inference rules.

A proof is like a contract with no loopholes: every clause follows from agreed definitions, so no future case can wriggle out of it. Testing examples is like asking a few people whether they found a loophole yet. Unlike contracts, a correct proof is never overturned by a later case; only a flawed step can break it.

Read the full lesson on Proofs

Background knowledge

These ideas may be useful before you work through the harder examples.

logical statementconditionalproof intuition