Math
Discrete math calculator
Three counting and sequence tools from a first discrete mathematics course: solve a linear recurrence and get its closed form, count a union with inclusion–exclusion, and find the bound the pigeonhole principle guarantees.
Whole number from 0 to 1000. The default is the Fibonacci sequence.
Gives the number in none of the sets.
| n | aₙ (iteration) | closed form |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 1 | 1 |
| 3 | 2 | 2 |
| 4 | 3 | 3 |
| 5 | 5 | 5 |
| 6 | 8 | 8 |
| 7 | 13 | 13 |
| 8 | 21 | 21 |
| 9 | 34 | 34 |
| 10 | 55 | 55 |
Show the working, step by step
Guess aₙ = rⁿ. Substituting and dividing by rⁿ⁻² gives the characteristic equation.
r² = r + 1 ⇔ r² − r − 1 = 0
Solve it. The discriminant is c₁² + 4c₂ = 1² + 4 × 1 = 5.
r = (1 + √5)/2 ≈ 1.61803, (1 − √5)/2 ≈ -0.618034
Fit the constants to the initial terms a₀ and a₁.
n = 0: A + B = 0 n = 1: A·r₁ + B·r₂ = 1 A = 1/√5 ≈ 0.447214, B = −1/√5 ≈ -0.447214
The closed form:
aₙ = (1/√5)·((1 + √5)/2)ⁿ + (−1/√5)·((1 − √5)/2)ⁿ
Check against direct iteration at n = 10.
iteration: a₁₀ = 55 closed form: a₁₀ ≈ 55
Terms are computed exactly with whole-number arithmetic; the closed form uses decimals, so large n can show rounding in its last digits.
Linear recurrence relations
A second-order linear homogeneous recurrence with constant coefficients defines each term from the two before it. Guessing a solution of the form rⁿ turns it into a quadratic:
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ characteristic equation: r² − c₁r − c₂ = 0, discriminant D = c₁² + 4c₂ D > 0 (roots r₁ ≠ r₂): aₙ = A·r₁ⁿ + B·r₂ⁿ D = 0 (root r twice): aₙ = (A + Bn)·rⁿ D < 0 (roots ρe^(±iθ)): aₙ = ρⁿ(A cos nθ + B sin nθ)
The two constants come from the starting values: set n = 0 and n = 1 and solve the pair of equations for A and B. Set c₂ = 0 for a first-order recurrence aₙ = c₁aₙ₋₁, whose solution is a geometric sequence.
Worked example: Fibonacci
The calculator opens with c₁ = 1, c₂ = 1, a₀ = 0 and a₁ = 1, which is the Fibonacci sequence.
- Characteristic equation: r² − r − 1 = 0, with D = 1² + 4 × 1 = 5.
- Roots: r = (1 + √5)/2 ≈ 1.61803 and (1 − √5)/2 ≈ −0.618034.
- Fit: A + B = 0 and A·r₁ + B·r₂ = 1 give A = 1/√5 ≈ 0.447214 and B = −1/√5.
- Closed form: aₙ = (1/√5)·((1 + √5)/2)ⁿ − (1/√5)·((1 − √5)/2)ⁿ, which is Binet’s formula.
- At n = 10 both iteration and the formula give 55.
The terms are computed exactly with whole-number arithmetic when the inputs are whole numbers, so a₁₀₀ = 354,224,848,179,261,915,075 comes out in full. The closed form is evaluated in decimals and is shown alongside as a check.
Inclusion–exclusion
|A ∪ B| = |A| + |B| − |A ∩ B| |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Choose “Inclusion–exclusion, 3 sets”. Its default counts describe 100 students: 45 take maths, 40 physics and 30 chemistry; 15 take maths and physics, 10 maths and chemistry, 12 physics and chemistry, and 5 take all three. Then 45 + 40 + 30 = 115; subtracting the overlaps gives 115 − 15 − 10 − 12 = 78; adding back the 5 gives 83 students taking at least one of the subjects, so 100 − 83 = 17 take none. The Venn diagram fills in all eight regions: 25 maths only, 18 physics only, 13 chemistry only, 10, 5 and 7 in exactly two, and 5 in all three.
The calculator refuses counts that cannot happen, for example a triple overlap larger than a pairwise one, or figures that would leave a negative number in some region.
The pigeonhole principle
n items in k boxes ⇒ some box holds at least ⌈n / k⌉ to force a box with m items, you need k(m − 1) + 1 items
With the defaults, 30 people and 12 birth months: ⌈30/12⌉ = ⌈2.5⌉ = 3, so at least three people share a birth month. The bound is tight, because 6 months with 3 birthdays and 6 with 2 is possible. To guarantee four people with the same birth month you need 12 × 3 + 1 = 37 people: 36 could be spread three to a month.
Which tool for which question
| The question asks… | Use |
|---|---|
| a formula for the nth term of a sequence defined by earlier terms | Linear recurrence |
| how many are in at least one (or none) of several overlapping groups | Inclusion–exclusion |
| to show that two things must share a property, or the least number that forces it | Pigeonhole |
| how many ways to choose or arrange items | Permutations and combinations |
Common mistakes
- Sign errors in the characteristic equation. aₙ = 5aₙ₋₁ − 6aₙ₋₂ gives r² − 5r + 6 = 0, not r² + 5r − 6 = 0. Move every term to one side.
- Using (A + B)rⁿ for a repeated root. That has only one free constant and cannot fit both a₀ and a₁. The second solution is n·rⁿ.
- Forgetting to add back the triple overlap. Subtracting all three pairwise overlaps removes the centre region three times after adding it three times.
- Rounding ⌈n/k⌉ down. 30/12 = 2.5 means at least 3, not 2.
Common questions
How do you solve a recurrence relation like aₙ = c₁aₙ₋₁ + c₂aₙ₋₂?
Try aₙ = rⁿ. Substituting and dividing by rⁿ⁻² gives the characteristic equation r² − c₁r − c₂ = 0. If its roots r₁ and r₂ are different, every solution is aₙ = A·r₁ⁿ + B·r₂ⁿ; if there is one repeated root r, it is aₙ = (A + Bn)·rⁿ. Then use a₀ and a₁ to find A and B. For aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1 and a₁ = 4, the roots are 3 and 2, and the solution is aₙ = 2·3ⁿ − 2ⁿ.
What is the closed form of the Fibonacci sequence?
Binet’s formula: Fₙ = (φⁿ − ψⁿ)/√5, where φ = (1 + √5)/2 ≈ 1.618 and ψ = (1 − √5)/2 ≈ −0.618 are the roots of r² − r − 1 = 0. Because |ψ| < 1, the ψⁿ term shrinks fast, and Fₙ is simply φⁿ/√5 rounded to the nearest whole number. F₁₀ = 55.
What is the inclusion–exclusion principle?
A way to count a union without double counting. For two sets, |A ∪ B| = |A| + |B| − |A ∩ B|. For three, add the three sizes, subtract the three pairwise overlaps, and add back the triple overlap. The signs alternate because each correction over- or under-counts the elements in more sets.
What does the pigeonhole principle say?
If n items go into k boxes, some box gets at least ⌈n/k⌉ items (n ÷ k rounded up). With 13 people and 12 months, two people share a birth month. With 30 people, at least ⌈30/12⌉ = 3 share a month. The principle proves something must exist without saying which box it is in.
What if the characteristic equation has complex roots?
The terms are still real. Write the roots as ρ(cos θ ± i sin θ) and the solution is aₙ = ρⁿ(A cos nθ + B sin nθ). The sequence oscillates with period 2π/θ, and grows or dies away depending on whether ρ is above or below 1. For aₙ = 2aₙ₋₁ − 2aₙ₋₂, ρ = √2 and θ = 45°, so the pattern of signs repeats every 8 terms while the size doubles every 2.
Related calculators
-
Set calculator
Venn diagrams and set operations on actual elements.
-
Permutations and combinations
nPr, nCr and arrangements, counted exactly.
-
Sequences and series
Arithmetic and geometric sequences and their sums.
-
Graph theory calculator
Shortest paths, spanning trees and Euler paths.