University discrete maths: what first-year modules cover and how to practise

What first-year discrete maths modules cover

Courses differ in how much they emphasise proof and how much they lean on applications such as cryptography. Your module handbook gives the exact syllabus and exam format.

The core topics

• Logic and proof: propositional logic, quantifiers, direct proof, contradiction, and mathematical induction.
• Sets, functions and relations: operations on sets, injections, surjections and bijections, equivalence relations and partial orders.
• Number theory: divisibility, gcd and Euclid's algorithm, modular arithmetic and inverses.
• Counting: permutations, combinations, the binomial theorem, and the pigeonhole principle.
• Graphs and trees: degrees, paths, connectivity, trees and spanning trees.
• Recurrence relations: setting up and solving recurrences.

Worked examples

Euclid's algorithm

Find gcd(252, 198): 252 = 1 × 198 + 54, then 198 = 3 × 54 + 36, then 54 = 1 × 36 + 18, then 36 = 2 × 18 + 0. The last non-zero remainder is the answer: 18.

Modular arithmetic

Find 3¹⁰⁰ mod 7. By Fermat's little theorem, 3⁶ ≡ 1 (mod 7). Since 100 = 6 × 16 + 4, 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7).

Counting

The number of 5-card hands from a 52-card deck, where order doesn't matter, is:

Proof by induction

Claim: 1 + 3 + 5 + ... + (2n − 1) = n². For n = 1 both sides are 1. If it holds for n = k, adding the next odd number gives k² + (2k + 1) = (k + 1)², so it holds for k + 1, and by induction for every positive integer n.

A recurrence

If a₀ = 0 and aₙ = 2aₙ₋₁ + 1, the first terms are 0, 1, 3, 7, 15, which suggests aₙ = 2ⁿ − 1. Check: 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1, and a₀ = 2⁰ − 1 = 0.

Practise sums and inverses in modular arithmetic in our Group Theory course, then press Mark to check your answer in the course:

Use the daily paper as practice

Uni-Sine publishes a free daily University Discrete Maths paper. It is a short timed practice paper: 8 questions worth 25 to 35 marks, with a suggested 40 to 55 minutes, marked when you finish. It is not your university's exam, so use it alongside your module's problem sheets and past papers.

• What it covers well: propositional logic, proof techniques and induction, sets and functions, modular arithmetic, counting and combinatorics, graph theory, trees and recurrence relations.
• What it does not cover: discrete probability, which some courses include, and the longer written proofs that courses like Cambridge's expect.

Common mistakes in discrete maths

• Skipping the base case. An induction proof is incomplete without its starting case as well as the step from k to k + 1.
• Mixing up permutations and combinations. Ask whether order matters.
• Assuming the converse. "If p then q" does not mean "if q then p".
• Reducing mod n inconsistently. Reduce at every step to keep numbers small, and always into the range 0 to n − 1.

Read next

University · MathsUniversity Calculus: First-Year Topics and PracticeWhat first-year university calculus covers: series, integration techniques, partial derivatives, multiple integrals and ODEs, plus examples and practice.