r² = r + 1 → r² − r − 1 = 0
module 11 · companion
proofs, primes,
& the patterns hiding in numbers
a visual reference for induction, divisibility, recursion, and linear recurrence relations. every concept shows its shape. every symbol earns its keep.
01 / PROOF TECHNIQUE
mathematical induction
a two-step proof machine. prove it works for the first case. prove each case implies the next. logic does the rest. this is the domino effect written in math.
the mental model
every induction proof is a line of dominos
to prove infinitely many statements, you only need to prove two things:
- base case — push the first domino (prove P(1) directly)
- inductive step — show each domino knocks the next (if P(k) is true, then P(k+1) is true)
if both hold, every domino falls. that's the whole trick.
← first domino is the base case · rest fall by the inductive step →
worked example
prove: 1 + 2 + 3 + ... + n = n(n+1)/2
click through each step of the proof. watch how the inductive hypothesis becomes the bridge from k to k+1.
claim: P(n): 1 + 2 + ... + n = n(n+1)/2 for all n ≥ 1
base case. show P(1) holds.
LHS = 1
RHS = 1(1+1)/2 = 2/2 = 1 ✓
inductive step. assume P(k) holds for some k ≥ 1.
inductive hypothesis (IH):
1 + 2 + ... + k = k(k+1)/2
show P(k+1) holds. target:
1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2
start with LHS:
1 + 2 + ... + k + (k+1)
= k(k+1)/2 + (k+1) ← substitute using IH
= (k+1)[k/2 + 1] ← factor out (k+1)
= (k+1)(k + 2)/2
= (k+1)(k+2)/2 ✓ ← matches target
by induction, P(n) holds for all n ≥ 1. ∎
step 0 / 16
template to memorize
every induction proof has the same skeleton
claim: P(n) is true for all n ≥ n₀
proof (by induction on n).
base case. show P(n₀) is true.
[plug in n₀, verify directly]
inductive step. assume P(k) for some k ≥ n₀. ← inductive hypothesis (IH)
we want to show P(k+1) is true.
[use IH to transform P(k) into P(k+1)]
therefore, by induction, P(n) holds for all n ≥ n₀. ∎
master the skeleton. the only part that changes problem-to-problem is the algebra in the inductive step.
02 / KEY TERM
the inductive hypothesis (IH)
the load-bearing assumption. when you write "assume P(k) is true," that assumption IS the inductive hypothesis. it's the tool you use to reach P(k+1).
what it is
a temporary assumption
you assume P(k) is true for some arbitrary k. you don't prove it — you just borrow it. then you use that assumption to prove P(k+1).
it's NOT circular reasoning. the base case is the real starting point. the IH just says: "if the chain hasn't broken by step k, it won't break at step k+1 either."
common mistake
forgetting to use it
if your proof of P(k+1) never references P(k), you're not doing induction — you're just proving each case directly. the IH is the hinge. if you don't use it, the proof isn't valid induction.
every time you substitute or simplify in the inductive step, ask: "did i just use the IH?" if not, you probably need to.
03 / NUMBER THEORY
prime numbers
a prime is a natural number greater than 1 whose only positive divisors are 1 and itself. primes are the atomic elements of the integers — every other integer is built from them.
sieve of eratosthenes
watch primes emerge from the natural numbers
start with 2. circle it (prime). cross out every multiple of 2. move to the next uncircled number (3). circle it. cross out its multiples. repeat. survivors are primes.
key facts
- 1 is NOT prime — primes must be greater than 1
- 2 is the only even prime — every other even number is divisible by 2
- fundamental theorem of arithmetic — every integer > 1 has a unique prime factorization (up to order)
- there are infinitely many primes — proved by euclid around 300 BC
04 / DIVISIBILITY
greatest common divisor
the gcd of two integers is the largest number that divides both of them. written gcd(a, b). the euclidean algorithm finds it in logarithmic time using just repeated remainders.
euclidean algorithm
gcd(a, b) = gcd(b, a mod b)
keep replacing the larger number with the remainder until one side becomes 0. the other side is your gcd.
why it works (intuition)
if d divides both a and b, then d also divides (a - b), and more generally (a mod b). so the set of common divisors doesn't change when we swap (a, b) for (b, a mod b). the numbers shrink, but the gcd is invariant. eventually we hit 0, and whatever's left is the answer.
05 / DIVISIBILITY
least common multiple
the lcm of two integers is the smallest positive number that BOTH divide into. it's the gcd's dual — and they're connected by one of the cleanest formulas in number theory.
the identity
lcm(a, b) · gcd(a, b) = a · b
lcm(a, b) = |a · b| / gcd(a, b)
once you know the gcd, the lcm is free. example with a=12 and b=18:
gcd(12, 18) = 6
lcm(12, 18) = (12 · 18) / 6 = 216 / 6 = 36
prime-factorization way (visual)
| number | factorization |
|---|---|
| 12 | 2² · 3 |
| 18 | 2 · 3² |
| gcd | 2¹ · 3¹ = 6 (take the MIN exponent for each prime) |
| lcm | 2² · 3² = 36 (take the MAX exponent for each prime) |
06 / SELF-REFERENCE
recursion
recursion is defining something in terms of smaller versions of itself. every recursion has two parts: base case (where it stops) and recursive case (where it calls itself).
the shape of a recursive call
factorial: n! = n · (n-1)!
base case: 0! = 1
recursive case: n! = n · (n-1)! for n ≥ 1
to compute 5!, we compute 5 · 4!, which needs 4!, which needs 3!, ... all the way down to the base case. then the answers unwind back up.
descend first the call stack grows as we hit the recursive case over and over. ascend then the base case triggers and answers climb back up.
important
recursion always needs a base case
without a base case, recursion never stops. in code this is a stack overflow. in math it's a definition that doesn't actually define anything. base case = the terminator.
07 / DEFINITION
recursive definitions
a recursive definition builds an object by saying (1) what the smallest cases look like, and (2) how to build larger cases from smaller ones. it's induction's twin — both work on the same domino logic, just pointed in different directions.
sequence: powers of 2
2ⁿ defined recursively
base: a₀ = 1
recursive: aₙ = 2 · aₙ₋₁ for n ≥ 1
first few terms: 1, 2, 4, 8, 16, 32, ...
fibonacci sequence
each term is the sum of the two before it
base: F₀ = 0, F₁ = 1
recursive: Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 2
first few terms: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
recursively defined SETS
definitions aren't just for sequences
you can define an entire set of objects recursively. example: the set S of all even non-negative integers.
base: 0 ∈ S
recursive: if x ∈ S, then (x + 2) ∈ S
exclusion: nothing else is in S
the exclusion clause matters — without it, you could argue anything is in S. standard practice in formal definitions.
08 / RECURRENCES
linear recurrence relations
a recurrence relation expresses aₙ in terms of earlier terms. LINEAR means the earlier terms appear to the first power — no squaring, no multiplying terms together, no weird functions of them.
the general form
a linear recurrence looks like this:
aₙ = c₁·aₙ₋₁ + c₂·aₙ₋₂ + ... + c_k·aₙ₋ₖ + f(n)
each aₙ₋ᵢ shows up exactly once, to the first power, multiplied by some coefficient. f(n) is an optional "forcing" term (if it's 0, the recurrence is homogeneous — see next sections).
linear vs NOT linear
linear ✓
aₙ = 3aₙ₋₁ + 2aₙ₋₂
earlier terms appear to the first power with constant coefficients
linear ✓ (with forcing)
aₙ = 2aₙ₋₁ + n
still linear — the forcing term doesn't touch earlier aₙ values
not linear ✗
aₙ = aₙ₋₁²
earlier term is squared — nonlinear
not linear ✗
aₙ = aₙ₋₁ · aₙ₋₂
two earlier terms multiplied together — nonlinear
09 / PROPERTY
the order of a recurrence
order = how far back you need to look. if aₙ depends on aₙ₋₁, it's order 1. if it depends on aₙ₋₁ and aₙ₋₂, it's order 2. simple as that.
| recurrence | depends on | order |
|---|---|---|
| aₙ = 3aₙ₋₁ | aₙ₋₁ | 1 |
| Fₙ = Fₙ₋₁ + Fₙ₋₂ | previous two | 2 |
| aₙ = aₙ₋₁ + 2aₙ₋₃ | aₙ₋₁ and aₙ₋₃ | 3 |
| aₙ = 5aₙ₋₁ − 6aₙ₋₂ + aₙ₋₄ | aₙ₋₁, aₙ₋₂, aₙ₋₄ | 4 |
rule: order = largest index gap between aₙ and the earliest term on the right-hand side. an order-k recurrence needs k initial conditions (a₀ through aₖ₋₁, or similar) to be fully determined.
10 / PROPERTY
homogeneous
a recurrence is homogeneous when there's no "extra" term. every piece of the equation involves aₙ or earlier aₙ values. nothing else.
the test
if everything can be moved to one side and equals 0 — it's homogeneous
homogeneous ✓
aₙ = 3aₙ₋₁ − 2aₙ₋₂
rewrite as: aₙ − 3aₙ₋₁ + 2aₙ₋₂ = 0 — every term has an aₙ subscript
NOT homogeneous ✗
aₙ = 3aₙ₋₁ + 5
the "+ 5" has nothing to do with aₙ values. that extra term makes it non-homogeneous (or "inhomogeneous")
NOT homogeneous ✗
aₙ = 2aₙ₋₁ + n²
n² is a function of n, not of earlier aₙ values. non-homogeneous
NOT homogeneous ✗
aₙ = aₙ₋₁ + 3ⁿ
same deal — 3ⁿ is a forcing term unrelated to earlier aₙ values
11 / PROPERTY
constant coefficients (CC)
the numbers multiplying aₙ₋₁, aₙ₋₂, etc. are actual numbers — not functions of n.
constant coefficients ✓
aₙ = 3aₙ₋₁ + 5aₙ₋₂
coefficients are 3 and 5 — plain numbers, don't change with n
constant coefficients ✓
aₙ = −7aₙ₋₁ + 12aₙ₋₃
negative and positive constants are both fine
NOT constant coefficients ✗
aₙ = n·aₙ₋₁
the coefficient is n itself — changes with every step. variable coefficient
NOT constant coefficients ✗
aₙ = (n+1)aₙ₋₁ + n²aₙ₋₂
both coefficients depend on n — variable coefficients
12 / COMPOUND
LHCC — linear, homogeneous, constant coefficients
combine all three properties and you get an LHCC recurrence. this is the sweet spot — LHCCs are the recurrences we know how to solve in closed form using the characteristic equation.
the checklist
a recurrence is LHCC if ALL three hold:
- LINEAR each aₙ₋ᵢ appears to the first power, not multiplied by each other
- HOMOGENEOUS no extra forcing term — only aₙ-subscripted pieces
- CONSTANT COEFFICIENTS the multipliers are numbers, not functions of n
canonical form of an order-k LHCC
aₙ = c₁·aₙ₋₁ + c₂·aₙ₋₂ + ... + c_k·aₙ₋ₖ
where c₁, c₂, ..., c_k are constants and c_k ≠ 0
examples
| recurrence | LHCC? | why |
|---|---|---|
| aₙ = 3aₙ₋₁ − 2aₙ₋₂ | yes | linear, homogeneous, CC — order 2 |
| Fₙ = Fₙ₋₁ + Fₙ₋₂ | yes | fibonacci is LHCC, order 2 |
| aₙ = 5aₙ₋₁ + 2 | no | the "+ 2" breaks homogeneity |
| aₙ = n·aₙ₋₁ | no | coefficient n is not constant |
| aₙ = aₙ₋₁² | no | not linear |
13 / SOLUTION METHOD
the characteristic equation
the big payoff. for any LHCC, you can turn the recurrence into a polynomial equation, solve it, and write down an exact closed-form formula for aₙ. no more computing term-by-term.
the core trick
guess aₙ = rⁿ. see what r has to be.
start with an LHCC like aₙ = c₁·aₙ₋₁ + c₂·aₙ₋₂. substitute aₙ = rⁿ:
rⁿ = c₁·rⁿ⁻¹ + c₂·rⁿ⁻²
divide both sides by rⁿ⁻²:
r² = c₁·r + c₂
→ r² − c₁·r − c₂ = 0 ← characteristic equation
solve this quadratic. the roots tell you the building blocks of the closed form.
worked example
solve fibonacci: Fₙ = Fₙ₋₁ + Fₙ₋₂, F₀ = 0, F₁ = 1
1
write the characteristic equation.
substitute Fₙ = rⁿ: rⁿ = rⁿ⁻¹ + rⁿ⁻². divide by rⁿ⁻²:
2
solve for r using the quadratic formula.
r = (1 ± √5) / 2
r₁ = (1 + √5) / 2 ≈ 1.618 ← the golden ratio φ
r₂ = (1 − √5) / 2 ≈ −0.618 ← ψ (its conjugate)
3
write the general solution.
when the roots are distinct, every solution is a linear combination of r₁ⁿ and r₂ⁿ:
Fₙ = A · r₁ⁿ + B · r₂ⁿ
A and B are constants we'll determine from initial conditions.
4
plug in initial conditions to find A and B.
F₀ = 0: A + B = 0 → B = −A
F₁ = 1: A·r₁ + B·r₂ = 1 → A(r₁ − r₂) = 1
r₁ − r₂ = √5 → A = 1/√5, B = −1/√5
5
write the closed form (Binet's formula).
Fₙ = (1/√5) · [ ((1+√5)/2)ⁿ − ((1−√5)/2)ⁿ ]
now you can compute F₁₀₀ without computing all 99 previous terms. check: F₁₀ = 55, formula gives 55 ✓.
the roots ↔ solutions cheat sheet
what the characteristic equation's roots mean
| roots of char. equation | general solution |
|---|---|
| distinct real roots r₁, r₂ | aₙ = A·r₁ⁿ + B·r₂ⁿ |
| repeated root r (mult. 2) | aₙ = (A + Bn)·rⁿ |
| three distinct roots r₁, r₂, r₃ | aₙ = A·r₁ⁿ + B·r₂ⁿ + C·r₃ⁿ |
| root r repeated m times | (A + Bn + Cn² + ... + constants·n^(m-1))·rⁿ |
the constants A, B, C, ... always come from plugging in the initial conditions (you'll need as many conditions as the order of the recurrence).
big picture
why the characteristic equation is a big deal
it turns an infinite recursive process into a finite algebraic one. instead of computing aₙ by grinding through every earlier term, you solve a polynomial once and get a formula that works for all n. for LHCCs this is guaranteed to work. for non-LHCCs (inhomogeneous, nonlinear, or variable coefficients) you need other techniques — generating functions, substitution, the "method of undetermined coefficients," or just computing term-by-term.