Skip to content
NumeriveMATH
Make learning comfortable
Changing style, motion, or reading speed keeps your current question, answers, homework, and saved progress. The school band still chooses your task layout. Saved to your learner profile across devices. All lessons and help stay available.
← Introduction to Mathematical Proof levels

Introduction to Mathematical Proof / LEVEL 1 · DIFFICULTY 4/5

Introduction to Mathematical Proof

Read the prerequisite, study a worked example and justify each step in these selected university topics.

2 stages · 16 practice problems · two 4-question assessment forms

STAGE UPRF 1.1 · 8 PRACTICE PROBLEMS · 4 NEW-CONTEXT APPLICATIONS

Direct, Contrapositive & Contradiction Proofs

Useful preparation: Logic, Sets & Relations

Open this topic in the university library →

For a long equation, swipe sideways inside its formula box to see every term.

Meaning & notation

A proof handles every allowed object. Track which facts are given, which assumptions are temporary, and why each step follows.

Direct proof
To prove P⇒Q\displaystyle P \Rightarrow Q directly, start with an arbitrary object satisfying P and derive Q through justified implications.
Contrapositive proof
Instead prove ¬Q⇒¬P. This is logically equivalent to P⇒Q\displaystyle P \Rightarrow Q, whereas the converse Q⇒P\displaystyle Q \Rightarrow P is generally not.
Contradiction and counterexample
Contradiction assumes the negation of the target alongside the hypotheses and derives incompatible statements. A counterexample is one allowed object satisfying the hypotheses but violating the conclusion.

Conditions before calculation

  • Declare the domain before using facts such as “not even means odd,” which is a dichotomy for integers, not arbitrary real numbers.
  • Division requires a nonzero divisor; taking square roots or reversing inequalities also needs its own stated conditions.
  • In an indirect proof, identify the temporary assumption and the precise contradiction. Do not assume the desired conclusion without a valid logical framework.

Why the method works

1. Unpack definitions

Replace descriptive words with usable equations. If an integer is divisible by a nonzero integer d, introduce an integer multiplier. The multiplier’s domain is part of the justification.

d∣n  ⟺  ∃k∈Z such that n=dkd\mid n\iff \exists k\in\mathbb Z\text{ such that }n=dk

2. Choose a helpful direction

A parity goal may be easier backwards. To establish that an even square has an even integer root, assume the root is odd and compute its square.

n=2k+1 ⟹ n2=2(2k2+2k)+1n=2k+1\ \Longrightarrow\ n^2=2(2k^2+2k)+1

3. Close the logical loop

Say which arbitrary choices were handled and how the last statement proves the target. For an equivalence, prove both directions separately; one implication alone is insufficient.

Worked examples

EXAMPLE 1

Prove that if a nonzero integer d divides both integers a and b, then it divides 3 a−2 b\displaystyle 3\, a - 2\, b.

  1. Because d divides a and b, choose integers r and s with a=dr\displaystyle a = dr and b=ds\displaystyle b = ds.

  2. Substitute these representations and distribute. This uses the hypotheses rather than the desired conclusion.

    3a−2b=3dr−2ds=d(3r−2s)3a-2b=3dr-2ds=d(3r-2s)

  3. The number 3 r−2 s\displaystyle 3\, r - 2\, s is an integer because integers are closed under multiplication and subtraction.

Conclusion: The displayed integer multiplier proves d divides 3 a−2 b\displaystyle 3\, a - 2\, b.

EXAMPLE 2

Prove that there is no smallest positive rational number.

  1. Assume a smallest positive rational r exists. “Smallest” means r is no larger than every positive rational.

  2. The number r2\displaystyle \frac{r}{2} is rational because rational numbers are closed under division by the nonzero integer 2.

  3. Since r is positive, 0<r2<r\displaystyle 0 < \frac{r}{2} < r. This is a positive rational smaller than the supposed smallest one.

Conclusion: The assumed minimum contradicts its defining property, so it cannot exist.

Pitfalls & counterexamples

Tempting claim: A true conclusion means the argument proving it is valid.

Correction: Every implication must follow from available assumptions, even when the final statement happens to be correct.

Test the claim: “All multiples of 4 are even because 12 is even” gives one successful case but does not handle arbitrary multiples.

Check your understanding

What must be assumed first in a contrapositive proof of “if n2\displaystyle n^{2} is odd, then n is odd” for integer n?

Write a reason before opening the explanation. This reflection is not graded or saved.

Compare your reasoning

Assume n is even.

Negate the conclusion, then show n2\displaystyle n^{2} is even, which negates the premise.

Connect this idea

Proof methods support induction, limit arguments, and algebraic structure tests. Checking quantifiers and legal operations prevents the same logical errors across these subjects.

Practise this topic →Review concept flashcards

Reference reading

Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.

Preview the eight practice prompts
  1. Problem 1

    Complete a direct proof 2 a+2 b=2 c\displaystyle 2\, a + 2\, b = 2\, c. With a=2\displaystyle a = 2, b=5\displaystyle b = 5, what integer is c?

    Practise this exact problem →
  2. Problem 2

    An odd integer n=2 a+1\displaystyle n = 2\, a + 1 with a=1\displaystyle a = 1. In n2=2 b+1\displaystyle n^{2} = 2\, b + 1, find b.

    Practise this exact problem →
  3. Problem 3

    A claim says “all positive integers n satisfy n<5\displaystyle n < 5.” Find the smallest positive counterexample.

    Practise this exact problem →
  4. Problem 4

    To prove “if n2\displaystyle n^{2} is even then n is even,” an argument assumes n=2 a+1\displaystyle n = 2\, a + 1 with a=2\displaystyle a = 2 and shows n2\displaystyle n^{2} odd. Which method is this? Enter 1 for contrapositive, 2 for testing examples only.

    Practise this exact problem →
  5. Problem 5New context

    A divisibility argument writes 2 a+2 b=2 c\displaystyle 2\, a + 2\, b = 2\, c. With a=3\displaystyle a = 3, b=6\displaystyle b = 6, what integer is c?

    Practise this exact problem →
  6. Problem 6New context

    A parity proof writes an odd integer n=2 a+1\displaystyle n = 2\, a + 1 with a=2\displaystyle a = 2. In n2=2 b+1\displaystyle n^{2} = 2\, b + 1, find b.

    Practise this exact problem →
  7. Problem 7New context

    A proposed rule says “all positive integers n satisfy n<6\displaystyle n < 6.” Find the smallest positive counterexample.

    Practise this exact problem →
  8. Problem 8New context

    A proof goal is “if n2\displaystyle n^{2} is even then n is even,” an argument assumes n=2 a+1\displaystyle n = 2\, a + 1 with a=3\displaystyle a = 3 and shows n2\displaystyle n^{2} odd. Which method is this? Enter 1 for contrapositive, 2 for testing examples only.

    Practise this exact problem →
Open stage UPRF 1.1 in the student workspace →

STAGE UPRF 1.2 · 8 PRACTICE PROBLEMS · 4 NEW-CONTEXT APPLICATIONS

Induction, Bijections & Countability

Useful preparation: Direct, Contrapositive & Contradiction Proofs

Open this topic in the university library →

For a long equation, swipe sideways inside its formula box to see every term.

Meaning & notation

Induction turns one verified starting point and a reusable transition into infinitely many conclusions. Bijections compare sets by pairing their elements without omission or duplication. Both methods replace an impossible infinite checklist with a finite rule whose correctness can be proved for arbitrary inputs.

Induction
For integers n≥n0\displaystyle n \ge n_{0}, prove P (n0)\displaystyle P\, \left(n_{0}\right), then prove P (k)⇒P (k+1)\displaystyle P\, \left(k\right) \Rightarrow P\, \left(k + 1\right) for every k≥n0\displaystyle k \ge n_{0}. Strong induction may assume all cases from n0\displaystyle n_{0} through k.
Injection, surjection, and bijection
An injection never identifies different inputs. A surjection reaches every element of its specified codomain. A bijection has both properties and therefore has an inverse function.
Countability
Use N={1,2,3,…}. A set is countably infinite if it admits a bijection with N; here “countable” includes finite sets as well.

Conditions before calculation

  • The base cases must cover the range actually needed by the transition. A recurrence using two preceding terms normally needs two starting values.
  • The inductive assumption concerns earlier cases only. The next case must be derived, not introduced as an additional assumption.
  • Every map needs a domain, codomain, and well-defined rule. Changing the codomain can change surjectivity without changing the formula.

Why the method works

1. Expose the next contribution

For a sum, separate the new term before using the induction hypothesis. This identifies the exact connection between successive cases rather than merely recognizing a pattern.

2. Prove both mapping properties

For injectivity, equate two outputs and derive equal inputs. For surjectivity, begin with an arbitrary target and construct an allowed preimage.

f(a)=f(b)⇒a=b,∀y∈B ∃x∈A: f(x)=yf(a)=f(b)\Rightarrow a=b,\qquad\forall y\in B\ \exists x\in A:\ f(x)=y

3. Compare infinite sets by a rule

An infinite proper subset can pair perfectly with its parent set. Listing initial values suggests the pairing, but an inverse formula proves that every target is reached exactly once.

Worked examples

EXAMPLE 1

Prove that the sum of the first n terms 2,5,8,… equals n (3 n+1)2\displaystyle \frac{n\, \left(3\, n + 1\right)}{2} for n≥1\displaystyle n \ge 1.

  1. At n=1\displaystyle n = 1, the formula gives 2, matching the first term.

  2. Assume the formula at arbitrary k≥1\displaystyle k \ge 1. The next term is 3 (k+1)−1=3 k+2\displaystyle 3\, \left(k + 1\right) - 1 = 3\, k + 2.

  3. Add that term and factor; this is the formula with k replaced by k+1\displaystyle k + 1.

    k(3k+1)2+3k+2=3k2+7k+42=(k+1)(3k+4)2\frac{k(3k+1)}2+3k+2=\frac{3k^2+7k+4}2=\frac{(k+1)(3k+4)}2

Conclusion: The base and transition prove the identity for every positive integer n.

EXAMPLE 2

Construct a bijection from N onto the integers Z.

  1. Send odd input 2 k−1\displaystyle 2\, k - 1 to k−1\displaystyle k - 1 and even input 2k to −k, for positive integer k.

    f(2k−1)=k−1,f(2k)=−kf(2k-1)=k-1,\qquad f(2k)=-k

  2. Odd inputs give distinct nonnegative integers; even inputs give distinct negative integers. The two output ranges cannot overlap.

  3. For target t≥0\displaystyle t \ge 0, choose input 2 t+1\displaystyle 2\, t + 1. For target t<0\displaystyle t < 0, choose input −2t. These are positive integers with the required outputs.

Conclusion: The rule is injective and surjective, so Z is countably infinite.

Pitfalls & counterexamples

Tempting claim: Checking several initial cases completes an induction proof.

Correction: Initial cases do not provide a transition for arbitrary k.

Test the claim: The claim n2≤100\displaystyle n^{2} \le 100 holds for n=1\displaystyle n = 1 through 10 but fails at n=11\displaystyle n = 11.

Check your understanding

Is f (x)=x2\displaystyle f\, \left(x\right) = x^{2} from R to [0,∞\displaystyle \infty) a bijection?

Write a reason before opening the explanation. This reflection is not graded or saved.

Compare your reasoning

It is surjective but not injective.

Every nonnegative y has preimage y\displaystyle \sqrt{y}, but 2 and −2 both map to 4.

Connect this idea

Induction formalizes recursive constructions. Bijections justify equal-size cosets and provide a precise foundation for comparing finite and infinite collections.

Practise this topic →Review concept flashcards

Reference reading

Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.

Preview the eight practice prompts
  1. Problem 1

    In the odd-sum induction at n=3\displaystyle n = 3, what next odd term must be added?

    Practise this exact problem →
  2. Problem 2

    After the induction hypothesis ∑\displaystyle \sum from j=1\displaystyle j = 1 to n of (2 j−1)=n2\displaystyle \left(2\, j - 1\right) = n^{2}. For n=2\displaystyle n = 2, what is the new total after adding 2 n+1\displaystyle 2\, n + 1?

    Practise this exact problem →
  3. Problem 3

    The bijection f (n)=2 n\displaystyle f\, \left(n\right) = 2\, n from positive integers to positive even integers. Which input maps to 8?

    Practise this exact problem →
  4. Problem 4

    A function f:R→R\displaystyle f : R \to R is f (x)=x2+1\displaystyle f\, \left(x\right) = x^{2} + 1. Is it surjective onto R? Enter 1 for yes, 0 for no.

    Practise this exact problem →
  5. Problem 5New context

    A staircase proof assumes the odd-sum formula at n=4\displaystyle n = 4, what next odd term must be added?

    Practise this exact problem →
  6. Problem 6New context

    A proof step starts with ∑\displaystyle \sum from j=1\displaystyle j = 1 to n of (2 j−1)=n2\displaystyle \left(2\, j - 1\right) = n^{2}. For n=3\displaystyle n = 3, what is the new total after adding 2 n+1\displaystyle 2\, n + 1?

    Practise this exact problem →
  7. Problem 7New context

    A numbering scheme is the bijection f (n)=2 n\displaystyle f\, \left(n\right) = 2\, n from positive integers to positive even integers. Which input maps to 10?

    Practise this exact problem →
  8. Problem 8New context

    A set map f:R→R\displaystyle f : R \to R is f (x)=x2+2\displaystyle f\, \left(x\right) = x^{2} + 2. Is it surjective onto R? Enter 1 for yes, 0 for no.

    Practise this exact problem →
Open stage UPRF 1.2 in the student workspace →
Browse another level →
Numerive