← All notesMaths AA · Proof, counting and partial fractions⬇ Download PDF
IB DP Maths AA · Topic 1 Number and algebra · SL 1.6 · AHL 1.10, 1.11, 1.15, 1.16 · ~8 min read

Proof, counting and partial fractions

Deductive proof and identities, and for HL: proof by induction and by contradiction, counting principles with permutations and combinations, partial fractions, and solving systems of linear equations.

Deductive proofLHS = RHSProof by induction (HL)Proof by contradiction (HL)Permutations & combinations (HL)Partial fractions (HL)Systems of equations (HL)
RSby Riyaz Sir
mentorriyaz.in
No tag = SL and HLHL ONLY HL students onlyFORMULA BOOKLET given in the examM1A1 how marks are awardedhighlight = comes up again and againTest yourself at the end

In 30 seconds

  • A proof is a chain of steps where each one follows from the last. Deductive proof starts from known facts; an identity proof works one side until it equals the other.
  • HL proof by induction: show the base case, assume case k, prove case k + 1, then write the conclusion.
  • HL proof by contradiction: assume the opposite and reach something impossible.
  • HL counting: multiply choices; permutations count orders, combinations ignore order.
  • HL partial fractions split a fraction with factorised denominator into simpler fractions. Systems of up to three linear equations may have one, none or infinitely many solutions.
  • 2029 syllabus: proof by counterexample is removed at HL; everything else here stays.

By the end you can

  • Write a clear deductive proof and prove identities (LHS ≡ RHS).
  • Prove statements by mathematical induction. HL
  • Use proof by contradiction. HL
  • Count arrangements and selections with the multiplication principle, permutations and combinations. HL
  • Split rational expressions into partial fractions. HL
  • Solve systems of linear equations and interpret their solutions. HL

1Deductive proof

  • Good proof habits: define your variables (let n ∈ ℤ, so an odd number is 2n + 1); show every step; end with a concluding sentence.
Worked example

Prove that the sum of two consecutive odd numbers is a multiple of 4.

  1. let the numbers be 2n + 1 and 2n + 3, n ∈ ℤ M1
  2. sum = 4n + 4 = 4(n + 1) A1
  3. n + 1 ∈ ℤ, so the sum is a multiple of 4 R1
Worked example

Prove that (x + 1)3 − (x − 1)3 ≡ 6x2 + 2.

  1. LHS = (x3 + 3x2 + 3x + 1) − (x3 − 3x2 + 3x − 1) M1
  2. = 6x2 + 2 = RHS A1
  3. so the identity holds for all x R1
Common mistakeStarting from the result and working "both sides" to 1 = 1. Start from ONE side (usually the more complicated one) and transform it into the other.
Syllabus noteProof by counterexample is removed from AA HL for the 2029 syllabus. It remains in the current syllabus (exams to November 2028): one example that breaks a statement disproves it.

2Proof by induction HL

base casen = 1 trueinductive step: if case k falls,case k + 1 fallsBoth together: every domino falls, so the statement is true for all n ∈ ℤ⁺.
Knock the first domino over, and show each one knocks the next: then all of them fall.
  • The four parts: (1) basis: show it is true for n = 1; (2) assumption: assume it is true for n = k; (3) inductive step: use the assumption to show it is true for n = k + 1; (4) conclusion: "since true for n = 1, and true for k ⇒ true for k + 1, it is true for all n ∈ ℤ+".
Worked example

Prove by induction that Σr=1n r = n(n + 1)2.

  1. n = 1: LHS = 1, RHS = 1 × 2/2 = 1 ✓ A1
  2. assume Σr=1k r = k(k + 1)/2 M1
  3. Σr=1k+1 r = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2 M1A1
  4. this is the formula with n = k + 1, so true for all n ∈ ℤ+ by induction R1
Worked example

Prove that 32n − 1 is divisible by 8 for all n ∈ ℤ+.

  1. n = 1: 9 − 1 = 8 ✓ A1
  2. assume 32k − 1 = 8m, m ∈ ℤ M1
  3. 32k+2 − 1 = 9 × 32k − 1 = 9(8m + 1) − 1 = 72m + 8 = 8(9m + 1) M1A1
  4. divisible by 8, so true for all n by induction R1
Common mistakeLeaving out the conclusion sentence or the words "assume true for n = k". These are worth marks (R1) on their own.

3Proof by contradiction HL

Worked example

Prove that √2 is irrational.

  1. assume √2 = p/q with p, q integers with no common factor M1
  2. 2q2 = p2, so p2 is even, so p is even: p = 2m A1
  3. 2q2 = 4m2 ⇒ q2 = 2m2, so q is even too A1
  4. p and q share the factor 2: contradiction, so √2 is irrational R1

4Counting principles HL

  • Multiplication principle: if one choice can be made in m ways and a second in n ways, together in m × n ways.
ⁿPr = n!(n − r)! FORMULA BOOKLET
arrangements of r items chosen from n (order matters)
ⁿCr = n!r!(n − r)! FORMULA BOOKLET
selections of r items from n (order does not matter)
Worked example

How many ways can 6 people sit in a row if two particular friends must sit together?

  1. treat the pair as one unit: 5 units in 5! = 120 orders M1
  2. the pair can swap: × 2 M1
  3. 240 A1
Worked example

A committee of 4 is chosen from 6 men and 5 women. How many committees have at least one woman?

  1. total ¹¹C4 = 330 A1
  2. no women: ⁶C4 = 15 A1
  3. at least one woman: 330 − 15 = 315 A1
Exam tip"At least one" is almost always quickest as total − none.

5Partial fractions HL

Worked example

Express 5x + 1(x + 1)(x − 1) in partial fractions.

  1. 5x + 1(x + 1)(x − 1) ≡ Ax + 1 + Bx − 1 M1
  2. 5x + 1 ≡ A(x − 1) + B(x + 1)
  3. x = 1: 6 = 2B ⇒ B = 3; x = −1: −4 = −2A ⇒ A = 2 A1
  4. = 2x + 1 + 3x − 1 A1
  • Rules: only for proper fractions (degree of top < degree of bottom) with distinct linear factors in the AA course. If the top's degree is too high, divide first.
  • Why bother: partial fractions turn hard integrals into ln terms, and some series into sums that telescope.

6Systems of linear equations HL

Worked example

Solve x + y + z = 6, 2x − y + z = 3, x + 2y − z = 2.

  1. (1) + (3): 2x + 3y = 8; (1) − (2): −x + 2y = 3 M1
  2. so x = 2y − 3 and 2(2y − 3) + 3y = 8 ⇒ y = 2 A1
  3. x = 1, y = 2, z = 3 A1
  • Three possibilities: a unique solution (three planes meet at a point), no solution (inconsistent), or infinitely many (planes meet in a line): give the solution in terms of a parameter λ.
GDC (calculator) methodPaper 2: use the simultaneous equation solver or row-reduce the matrix (rref). If the GDC reports "no solution" or "infinite solutions", say which and interpret it.
Linking questionInduction proves the sigma formulae used in Sequences and the derivative patterns in Differentiation; partial fractions are the key step in several Integration questions.
Idea for your IA / explorationExplore a counting problem with a real context (lottery odds, passwords, seating plans), or investigate a sequence conjectured from patterns and prove it by induction.

Test yourself — cover the answers first

Quick check

  1. How many ways can 5 different books be arranged on a shelf?
  2. Evaluate ¹⁰P3 and ¹⁰C3.
  3. What are the four parts of an induction proof?
  4. Write an odd integer and an even integer in general form.
  5. HL How many ways can 3 boys and 3 girls stand in a line if boys and girls alternate?

Exam-style

  1. HL Prove by induction that n3 − n is divisible by 6 for n ∈ ℤ+.
  2. HL Express x + 7x2 + x − 2 in partial fractions.
Show answers
  1. 120
  2. 720 and 120
  3. basis, assumption, inductive step, conclusion
  4. 2n + 1 and 2n (n ∈ ℤ)
  5. 2 × 3! × 3! = 72
  6. n = 1: 0 = 6 × 0 ✓
    (k + 1)3 − (k + 1) = (k3 − k) + 3k(k + 1)
    k3 − k = 6m, and k(k + 1) is even, so 3k(k + 1) is a multiple of 6
    so true for all n by induction
  7. x2 + x − 2 = (x + 2)(x − 1)
    x + 7 ≡ A(x − 1) + B(x + 2)
    x = 1: B = 8/3; x = −2: A = −5/3
    83(x − 1) − 53(x + 2)
Practise this chapter
IB Maths AA practice papers
Next chapterComplex numbers →
Stuck on a question?

Send it to me on WhatsApp. I read every message.

Want regular help? Send this to your parent →
Share with a friendAsk Riyaz Sir

Independent notes written by Riyaz Sir. Not produced, endorsed or approved by the International Baccalaureate Organization. Syllabus codes refer to the IB DP subject guides.