MathematicsChapter 7: Mathematical Induction and Binomial Theorem

Induction On Divisibility and Inequalities

Divisibility: show 3 divides 4^n - 1, or 7 divides 3^{2n}-1, school-style.

Learning objectives

State the main ideas and notation used in induction on divisibility and inequalities.
Apply the rules of induction on divisibility and inequalities in a clear, step-by-step solution.
Check signs, conditions, and the final answer for mathematical accuracy.

Definition

Divisibility: show 3 divides 4^n - 1, or 7 divides 3^{2n}-1, school-style. Write 4^{k+1}-1 = 4(4^k-1) + 3, so the extra is clearly a multiple of 3. Inequalities: (1+x)^{n} >= 1+n x for x>=-1, n>=1 (Bernoulli named if the book has it). Meaning: factor or add a clearly positive/divisible leftover.

Where / symbols

INDUCTION ON DIVISIBILITY AND INEQUALITIES: Divisibility: show 3 divides 4^n - 1, or 7 divides 3^{2n}-1, school-style. Write 4^{k+1}-1 = 4(4^k-1) + 3, so the extra is clearly a multiple of 3. Inequalities: (1+x)^{n} >= 1+n x for x>=-1, n>=1 (Bernoulli named if the book has it). Meaning: factor or add a clearly positive/divisible leftover.
1. DIVIDES: P(n): m divides f(n). IH: f(k)=m t. Aim: f(k+1)=m s. Algebra: f(k+1) = (something)*f(k) + (multiple of m).
2. INEQUALITIES: Assume P(k), multiply both sides by a positive number, or add a positive term. Track the direction of >= . Base often n=1 or n=2 as stated.

Overview

Divisible leftover, then inequalities:

Divides

P(n): m divides f(n). IH: f(k)=m t. Aim: f(k+1)=m s. Algebra: f(k+1) = (something)*f(k) + (multiple of m).

Examples 4^{k+1}-1 = 4(4^k-1)+3 · 3 | 3 and 3 | IH piece · State m divides both

Inequalities

Assume P(k), multiply both sides by a positive number, or add a positive term. Track the direction of >= . Base often n=1 or n=2 as stated.

Examples Multiply by (1+x) if x>-1 · Show extra >= 0 · End at P(k+1)

WHAT — INDUCTION ON DIVISIBILITY AND INEQUALITIES

RULE — 1. DIVIDES

P(n): m divides f(n). IH: f(k)=m t. Aim: f(k+1)=m s. Algebra: f(k+1) = (something)*f(k) + (multiple of m).

METHOD — 2. INEQUALITIES

Assume P(k), multiply both sides by a positive number, or add a positive term. Track the direction of >= . Base often n=1 or n=2 as stated.

WORKED EXAMPLE

Worked: 3 divides 4ⁿ-1, the step. 4^k+1-1 = 4*4^k - 1 = 4(4^k-1) + 3 3 divides (4^k-1) by IH 3 divides 3 so 3 divides the sum

How to answer a induction on divisibility and inequalities question

Identify the given quantities, notation, and required result.
Choose the matching rule and write it before substitution.
Work one algebraic step at a time, keeping brackets and signs clear.
Check restrictions, simplify the result, and verify it where possible.

Worked example

3 divides 4^n-1, the step.
4^k+1-1 = 4*4^k - 1 = 4(4^k-1) + 3
3 divides (4^k-1) by IH
3 divides 3
so 3 divides the sum

In simple words

Write 4^k+1-1 as 4(4^k-1)+3 so both pieces are visibly multiples of 3.

Key points

write the k+1 expression in terms of the k piece
leftover must be divisible / positive
extract f(k)
keep the inequality direction

Exam preparation

Exam Focus

Quick revision

Revision Zone

Review the key facts, formulas and checks before you move on.