2. So why do I need to learn all this nasty mathematics?

Why you should know about mathematics, if you are interested in ComputerScience: or, more specifically, why you should take CS202 or a comparable course:

• Computation is something that you can't see and can't touch, and yet (thanks to the efforts of generations of hardware engineers) it obeys strict, well-defined rules with astonishing accuracy over long periods of time.
• Computations are too big for you to comprehend all at once. Imagine printing out an execution trace that showed every operation a typical $500 desktop computer executed in one (1) second. If you could read one operation per second, for eight hours every day, you would die of old age before you got halfway through. Now imagine letting the computer run overnight.

So in order to understand computations, we need a language that allows us to reason about things we can't see and can't touch, that are too big for us to understand, but that nonetheless follow strict, simple, well-defined rules. We'd like our reasoning to be consistent: any two people using the language should (barring errors) obtain the same conclusions from the same information. Computer scientists are good at inventing languages, so we could invent a new one for this particular purpose, but we don't have to: the exact same problem has been vexing philosophers, theologians, and mathematicians for much longer than computers have been around, and they've had a lot of time to think about how to make such a language work. Philosophers and theologians are still working on the consistency part, but mathematicians (mostly) got it in the early 20th-century. Because the first virtue of a computer scientist is laziness, we are going to steal their code.

3. But isn't math hard?

Yes and no. The human brain is not really designed to do formal mathematical reasoning, which is why most mathematics was invented in the last few centuries and why even apparently simple things like learning how to count or add require years of training, usually done at an early age so the pain will be forgotten later. But mathematical reasoning is very close to legal reasoning, which we do seem to be unusually good at. There is very little structural difference between the sentences

• "If x is in S, then x+1 is in S." (1)

and

• "If x is of royal blood, then x's child is of royal blood." (2)

but because the first is about boring numbers and the second is about fascinating social relationships and rules, most people have a much easier time deducing that to show somebody is royal we need to start with some known royal and follow a chain of descendants than they have deducing that to show that some number is in the set S. we need to start with some known element of S and show that repeatedly adding 1 gets us to the number we want. And yet to a logician these are the same processes of reasoning.

So why is statement (1) trickier to think about than statement (2)? Part of the difference is familiarity—we are all taught from an early age what it means to be somebody's child, to take on a particular social role, etc. For mathematical concepts, this familiarity comes with exposure and practice, just as with learning any other language. But part of the difference is that we humans are wired to understand and appreciate social and legal rules: we are very good at figuring out the implications of a (hypothetical) rule that says that any contract to sell a good to a consumer for $100 or more can be cancelled by the consumer within 72 hours of signing it provided the good has not yet been delivered, but we are not so good at figuring out the implications of a rule that says that a number is composite if and only if it is the product of two integer factors neither of which is 1. It's a lot easier to imagine having to cancel a contract to buy swampland in Florida that you signed last night while drunk than having to prove that 82 is composite. But again: there is nothing more natural about contracts than about numbers, and if anything the conditions for our contract to be breakable are more complicated than the conditions for a number to be composite.

4. Thinking about math with your heart

There are two things you need to be able to do to get good at mathematics (the creative kind that involves writing proofs, not the mechanical kind that involves grinding out answers according to formulas). One of them is to learn the language: to attain what mathematicians call mathematical maturity. You'll do that in CS202, if you pay attention. But the other is to learn how to activate the parts of your brain that are good at mathematical-style reasoning when you do math—the parts evolved to detect when the other primates in your primitive band of hunter-gatherers are cheating.

To do this it helps to get a little angry, and imagine that finishing a proof or unraveling a definition is the only thing that will stop your worst enemy from taking some valuable prize that you deserve. (If you don't have a worst enemy, there is always the UniversalQuantifier.) But whatever motivation you choose, you need to be fully engaged in what you are doing. Your brain is smart enough to know when you don't care about something, and if you don't believe that thinking about math is important, it will think about something else.

CategoryMathNotes

List of things you should know about if you want to do ComputerScience.

6. Foundations and logic

Why: This is the assembly language of mathematics—the stuff at the bottom that everything else complies to.

• Propositional logic.
• Predicate logic.
• Axioms, theories, and models.
• Proofs.
• Induction and recursion.

7. Fundamental mathematical objects

Why: These are the mathematical equivalent of data structures, the way that more complex objects are represented.

• Naive set theory.
  • Predicates vs sets.
  • Set operations.
  • Set comprehension.
  • Russell's paradox and axiomatic set theory.
• Functions.
  • Functions as sets.
  • Injections, surjections, and bijections.
  • Cardinality.
  • Finite vs infinite sets.
  • Sequences.
• Relations.
  • Equivalence relations, equivalence classes, and quotients.
  • Orders.
• The basic number tower.
  • Countable universes: ℕ, ℤ, ℚ. (Can be represented in a computer.)
  • Uncountable universes: ℝ, ℂ. (Can only be approximated in a computer.)
• Other algebras.
  • The string monoid.
  • ℤ/m and ℤ/p.
  • Polynomials over various rings and fields.

8. Modular arithmetic and polynomials

Why: Basis of modern cryptography.

• Arithmetic in ℤ/m.
• Primes and divisibility.
• Euclid's algorithm and inverses.
• The Chinese Remainder Theorem.
• Fermat's Little Theorem and Euler's Theorem.
• RSA encryption.
• Galois fields and applications.

9. Linear algebra

Why: Shows up everywhere.

• Vectors and matrices.
• Matrix operations and matrix algebra.
• Geometric interpretations.
• Inverse matrices and Gaussian elimination.

10. Graphs

Why: Good for modeling interactions. Basic tool for algorithm design.

• Definitions: graphs, digraphs, multigraphs, etc.
• Paths, connected components, and strongly-connected components.
• Special kinds of graphs: paths, cycles, trees, cliques, bipartite graphs.
• Subgraphs, induced subgraphs, minors.

11. Counting

Why: Basic tool for knowing how much resources your program is going to consume.

• Basic combinatorial counting: sums, products, exponents, differences, and quotients.
• Combinatorial functions.
  • Factorials.
  • Binomial coefficients.
  • The 12-fold way.
• Advanced counting techniques.
  • Inclusion-exclusion.
  • Recurrences.
  • Generating functions.

12. Probability

Why: Can't understand randomized algorithms or average-case analysis without it. Handy if you go to Vegas.

• Discrete probability spaces.
• Events.
• Independence.
• Random variables.
• Expectation and variance.
• Probabilistic inequalities.
  • Markov's inequality.
  • Chebyshev's inequality.
  • Chernoff bounds.
• Stochastic processes.
  • Markov chains.
  • Martingales.
  • Branching processes.

13. Tools

Why: Basic computational stuff that comes up, but doesn't fit in any of the broad categories above. These topics will probably end up being mixed in with the topics above.

These you will have seen before:

• How to differentiate and integrate simple functions.
• Things you may have forgotten about exponents and logarithms.

These may be somewhat new:

• Inequalities and approximations.
• ∑ and ∏ notation.
• Computing or approximating the value of a sum.
• Asymptotics.

CategoryMathNotes

Set theory is the dominant foundation for mathematics. The idea is that everything else in mathematics—numbers, functions, etc.—can be written in terms of sets, so that if you have a consistent description of how sets behave, then you have a consistent description of how everything built on top of them behaves. If predicate logic is the machine code of mathematics, set theory would be assembly language.

19. Naive set theory

Naive set theory is the informal version of set theory that corresponds to our intuitions about sets as unordered collections of objects (called elements) with no duplicates. A set can be written explicitly by listing its elements using curly braces:

• { } = the empty set ∅, which has no elements.

• { Moe, Curly, Larry } = the Three Stooges.

• { 0, 1, 2, ... } = ℕ, the natural numbers. Note that we are relying on the reader guessing correctly how to continue the sequence here.
• { { }, { 0 }, { 1 }, { 0, 1 }, { 0, 1, 2 }, 7 } = a set of sets of natural numbers, plus a stray natural number that is directly an element of the outer set.

Membership in a set is written using the ∈ symbol (pronounced "is an element of" or "is in"). So we can write Moe ∈ The Three Stooges or 4 ∈ ℕ. We can also write ∉ for "is not an element of", as in Moe ∉ ℕ.

A fundamental axiom in set theory is that the only distinguishing property of a set is its list of members: if two sets have the same members, they are the same set.

For nested sets like { { 1 } }, ∈ represents only direct membership: the set { { 1 } } only has one element, { 1 }, so 1 ∉ { { 1 } }. This can be confusing if you think of ∈ as representing the English "is in," because if I put my lunch in my lunchbox and put my lunchbox in my backpack, then my lunch is in my backpack. But my lunch is not an element of { { my lunch }, my textbook, my slingshot }. In general, ∈ is not transitive (see Relations)—it doesn't behave like < unless there is something very unusual about the set you are applying it to—and there is no particular notation for being a deeply-buried element of an element of an element (etc.) of some set.

In addition to listing the elements of a set explicitly, we can also define a set by set comprehension, where we give a rule for how to generate all of its elements. This is pretty much the only way to define an infinite set without relying on guessing, but can be used for sets of any size. Set comprehension is usually written using set-builder notation, as in the following examples:

• { x | x∈ℕ ∧ x > 1 ∧ ∀y∈ℕ∀z∈ℕ yz = x ⇒ y = 1 ∨ z = 1 } = the prime numbers.

• { 2x | x∈ℕ } = the even numbers.

• { x | x∈ℕ ∧ x < 12 } = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }.

Sometimes the original set that an element has to be drawn from is put on the left-hand side of the pipe:

• { n∈ℕ | ∃x,y,z∈ℕ x > 0 ∧ y > 0 ∧ xⁿ + yⁿ = zⁿ }. (This is a fancy name for the two-element set { 1, 2 }; see Fermat's Last Theorem.)

Using set comprehension, we can see that every set in naive set theory is equivalent to some predicate. Given a set S, the corresponding predicate is x∈S, and given a predicate P, the corresponding set is { x | Px }. But beware of Russell's paradox: what is { S | S∉S }?

20. Operations on sets

If we think of sets as representing predicates, each logical connective gives rise to a corresponding operation on sets:

• A∪B = { x | x∈A ∨ x∈B }. The union of A and B.

• A∩B = { x | x∈A ∧ x∈B }. The intersection of A and B.

• A∖B = { x | x∈A ∧ x∉B }. The set difference of A and B.

• A∆B = { x | x∈A ⊕ x∈B }. The symmetric difference of A and B.

(Of these, union and intersection are the most important in practice.)

Corresponding to implication is the notion of a subset:

• A⊆B ("A is a subset of B") if and only if ∀x x∈A ⇒ x∈B.

Sometimes one says A is contained in B if A⊆B. This is one of two senses in which A can be "in" B—it is also possible that A is in fact an element of B (A∈B). For example, the set A = { 12 } is an element of the set B = { Moe, Larry, Curly, { 12 } } but A is not a subset of B, because A's element 12 is not an element of B. Usually we will try to reserve "is in" for ∈ and "is contained in" for ⊆, but it's safest to use the symbols to avoid any possibility of ambiguity.

Finally we have the set-theoretic equivalent of negation:

• Ā = { x | x∉A }. The set Ā is known as the complement of A.

If we allow complements, we are necessarily working inside some fixed universe: the complement of the empty set contains all possible objects. This raises the issue of where the universe comes from. One approach is to assume that we've already fixed some universe that we understand (e.g. ℕ), but then we run into trouble if we want to work with different classes of objects at the same time. Modern set theory is defined in terms of a collection of axioms that allow us to construct, essentially from scratch, a universe big enough to hold all of mathematics without apparent contradictions while avoiding the paradoxes that may arise in naive set theory.

21. Axiomatic set theory

The problem with naive set theory is that unrestricted set comprehension is too strong, leading to contradictions. Axiomatic set theory fixes this problem by being more restrictive about what sets one can form. The axioms most commonly used are known as Zermelo-Fraenkel set theory with choice or ZFC. The page AxiomaticSetTheory covers these axioms in painful detail, but in practice you mostly just need to know what constructions you can get away with.

The short version is that you can construct sets by (a) listing their members, (b) taking the union of other sets, or (c) using some predicate to pick out elements or subsets of some set. The starting points for this process are the empty set ∅ and the set ℕ of all natural numbers (suitably encoded as sets). If you can't construct a set in this way (like the Russell's Paradox set), odds are that it isn't a set.

These properties follow from the more useful axioms of ZFC:

Extensionality

Any two sets with the same members are equal.

Existence

∅ is a set.

Pairing

For any given list of sets x, y, z, ..., { x, y, z, ... } is a set. (Strictly speaking, pairing only gives the existence of { x, y }, and the more general result requires the next axiom as well.)

Union

For any given set of sets { x, y, z, ... }, the set x ∪ y ∪ z ∪ ... exists.

Power set

For any set S, the power set ℘(S) = { A | A ⊆ S } exists.

Specification

For any set S and any predicate P, the set { x∈S | P(x) } exists. This is called restricted comprehension. Limiting ourselves to constructing subsets of existing sets avoids Russell's Paradox, because we can't construct S = { x | x ∉ x }. Instead, we can try to construct S = { x∈T | x∉x }, but we'll find that S isn't an element of T, so it doesn't contain itself without creating a contradiction.

Infinity

ℕ exists, where ℕ is defined as the set containing ∅ and containing x∪{x} whenever it contains x. Here ∅ represents 0 and x∪{x} represents the successor operation. This effectively defines each number as the set of all smaller numbers, e.g. 3 = { 0, 1, 2 } = { ∅, { ∅ }, { ∅, { ∅ } } }. Without this axiom, we only get finite sets.

There are three other axioms that don't come up much in computer science:

Foundation

Every nonempty set A contains a set B with A∩B=∅. This rather technical axiom prevents various weird sets, such as sets that contain themselves or infinite descending chains A₀ ∋ A₁ ∋ A₂ ∋ ... .

Replacement

If S is a set, and R(x,y) is a predicate with the property that ∀x ∃!y R(x,y), then { y | ∃x∈S R(x,y) } is a set. Mostly used to construct astonishingly huge infinite sets.

Choice

For any set of nonempty sets S there is a function f that assigns to each x in S some f(x) ∈ x.

22. Cartesian products, relations, and functions

Sets are unordered: the set { a, b } is the same as the set { b, a }. Sometimes it is useful to consider ordered pairs (a, b), where we can tell which element comes first and which comes second. These can be encoded as sets using the rule (a, b) = { {a}, {a, b} }.

Given sets a and b, their Cartesian product a × b is the set { (x,y) | x ∈ a ∧ y ∈ b }, or in other words the set of all ordered pairs that can be constructed by taking the first element from a and the second from b. If a has n elements and b has m, then a × b has nm elements. For example, { 1, 2 } × { 3, 4 } = { (1,3), (1,4), (2,3), (2,4) }.

Because of the ordering, Cartesian product is not commutative in general. We usually have A×B ≠ B×A (exercise: when are they equal?).

The existence of the Cartesian product of any two sets can be proved using the axioms we already have: if (x,y) is defined as { {x}, {x,y} }, then ℘(a ∪ b) contains all the necessary sets {x} and {x,y}, and ℘℘(a ∪ b) contains all the pairs { {x}, {x,y} }. It also contains a lot of other sets we don't want, but we can get rid of them using Specification.

A subset of the Cartesian product of two sets is called a relation. An example would be the < relation on the natural numbers: { (0, 1), (0, 2), ...; (1, 2), (1, 3), ...; (2, 3), ... }. Just as sets can act like predicates of one argument (where Px corresponds to x ∈ P), relations act like predicates of two arguments. Relations are often written between their arguments, so xRy is shorthand for (x,y) ∈ R.

A special class of relations are functions. A function from a domain A to a codomain (or range) B is a relation on A and B (i.e., a subset of A × B) such that every element of A appears on the left-hand side of exactly one ordered pair. We write f: A⇒B as a short way of saying that f is a function from A to B, and for each x ∈ A write f(x) for the unique y ∈ B with (x,y) ∈ f. (Technically, knowing f alone does not tell you what the codomain is, since some elements of B may not show up at all; this can be fixed by representing a function as a pair (f,B), but it's generally not useful unless you are doing CategoryTheory.) Most of the time a function is specified by giving a rule for computing f(x), e.g. f(x) = x².

Functions let us define sequences of arbitrary length: for example, the infinite sequence x₀, x₁, x₂, ... of elements of some set A is represented by a function x:ℕ→A, while a shorter sequence (a₀, a₁, a₂) would be represented by a function a:{0,1,2}→A. In both cases the subscript takes the place of a function argument: we treat x_n as syntactic sugar for x(n). Finite sequences are often called tuples, and we think of the result of taking the Cartesian product of a finite number of sets A×B×C as a set of tuples (a,b,c) (even though the actual structure may be ((a,b),c) or (a,(b,c)) depending on which product operation we do first).

A function f:A→B that covers every element of B is called onto, surjective, or a surjection. If it maps distinct elements of A to distinct elements of B (i.e., if x≠y implies f(x)≠f(y)), it is called one-to-one, injective, or an injection. A function that is both surjective and injective is called a one-to-one correspondence, bijective, or a bijection. (The terms onto, one-to-one, and bijection are probably the most common, although injective and surjective are often used as well, as they avoid the confusion between one-to-one and one-to-one correspondence.) Any bijection f has an inverse f^-1; this is the function { (y,x) | (x,y) ∈ f }. Two functions f:A→B and g:B→C can be composed to give a composition g∘f; g∘f is a function from A to C defined by (g∘f)(x) = g(f(x)).

Bijections let us define the size of arbitrary sets without having some special means to count elements. We say two sets A and B have the same size or cardinality if there exists a bijection f:A↔B. We can also define |A| formally as the (unique) smallest ordinal B such that there exists a bijection f:A↔B. This is exactly what we do when we do counting: to know that there are 3 stooges, we count them off 0 → Moe, 1 → Larry, 2 → Curly, giving a bijection between the set of stooges and 3 = { 0, 1, 2 }.

More on functions and relations can be found on the pages Functions and Relations.

23. Constructing the universe

With power set, Cartesian product, the notion of a sequence, etc., we can construct all of the standard objects of mathematics. For example:

Integers

The integers are the set ℤ = { ..., -2, -1, 0, -1, 2, ... }. We represent each integer z as an ordered pair (x,y), where x=0 ∨ y=0; formally, ℤ = { (x,y) ∈ ℕ×ℕ | x=0 ∨ y=0 }. The interpretation of (x,y) is x-y; so positive integers z are represented as (z,0) while negative integers are represented as (0,-z). It's not hard to define addition, subtraction, multiplication, etc. using this representation.

Rationals

The rational numbers ℚ are all fractions of the form p/q where p is an integer, q is a natural number not equal to 0, and p and q have no common factors.

Reals

The real numbers ℝ can be defined in a number of ways, all of which turn out to be equivalent. The simplest to describe is that a real number x is represented by the set { y∈ℚ | y≤x }. Formally, we consider any subset of x of ℚ with the property y∈x ∧ z<y ⇒ z∈x to be a distinct real number (this is known as a Dedekind cut). Note that real numbers in this representation may be hard to write down.

We can also represent standard objects of computer science:

Deterministic finite state machines

A deterministic finite state machine is a tuple (Σ,Q,q₀,δ,Q_accept) where Σ is an alphabet (some finite set), Q is a state space (another finite set), q₀∈Q is an initial state, δ:Q×Σ→Q is a transition function specifying which state to move to when processing some symbol in Σ, and Q_accept⊆Q is the set of accepting states. If we represent symbols and states as natural numbers, the set of all deterministic finite state machines is then just a subset of ℘ℕ×℘ℕ×ℕ×(ℕ^ℕ×ℕ)×℘ℕ satisfying some consistency constraints.

24. Sizes and arithmetic

We can compute the size of a set by explicitly counting its elements; for example, |∅| = 0, | { Larry, Moe, Curly } | = 3, and | { x∈ℕ | x < 100 ∧ x is prime } | = 25. But sometimes it is easier to compute sizes by doing arithmetic. We can do this because many operations on sets correspond in a natural way to arithmetic operations on their sizes. (For much more on this, see HowToCount.)

Two sets A and B that have no elements in common are said to be disjoint; in set-theoretic notation, this means A∩B = ∅. In this case we have |A∪B| = |A|+|B|. The operation of disjoint union acts like addition for sets. For example, the disjoint union of 2-element set { 0, 1 } and the 3-element set { Wakko, Jakko, Dot } is the 5-element set { 0, 1, Wakko, Jakko, Dot }.

The size of a Cartesian product is obtained by multiplication: |A×B| = |A|⋅|B|. An example would be the product of the 2-element set { a, b } with the 3-element set { 0, 1, 2 }: this gives the 6-element set { (a,0), (a,1), (a,2), (b,0), (b,1), (b,2) }. Even though Cartesian product is not generally commutative, since ordinary natural number multiplication is, we always have |A×B| = |B×A|.

For power set, it is not hard to show that |℘(S)| = 2^|S|. This is a special case of the size of A^B, the set of all functions from B to A, which is |A|^|B|; for the power set we can encode P(S) using 2^S, where 2 is the special set {0,1}.

24.1. Infinite sets

For infinite sets, we take the above properties as definitions of addition, multiplication, and exponentiation of their sizes. The resulting system is known as cardinal arithmetic, and the sizes that sets (finite or infinite) might have are known as cardinal numbers.

The finite cardinal numbers are just the natural numbers: 0, 1, 2, 3, ... . The first infinite cardinal number is the size of the set of natural numbers, and is written as ℵ₀ ("aleph-zero," "aleph-null," or "aleph-nought"). The next infinite cardinal number is ℵ₁ ("aleph-one"): it might or might not be the size of the set of real numbers, depending on whether you include the Generalized Continuum Hypothesis in your axiom system or not.

Infinite cardinals can behave very strangely. For example:

• ℵ₀+ℵ₀=ℵ₀. In other words, it is possible to have two sets A and B that both have the same size as ℕ, take their disjoint union, and get another set A+B that has the same size as ℕ. To give a specific example, let A = { 2x | x∈ℕ } and B = { 2x+1 | x∈ℕ }. These have |A|=|B|=|ℕ| because there is a bijection between each of them and ℕ built directly into their definitions. It's also not hard to see that A and B are disjoint, and A∪B = ℕ. So |A|=|B|=|A|+|B| in this case.

• ℵ₀⋅ℵ₀=ℵ₀. Example: A bijection between ℕ×ℕ and ℕ using the Cantor pairing function <x,y> = (x+y+1)(x+y)/2 + y. The first few values of this are <0,0> = 0, <1,0> = 2⋅1/2+0 = 1, <0,1> = 2⋅1/2+1 = 1, <2,0> = 3⋅2/2 + 0 = 3, <1,1> = 3⋅2/2 + 1 = 4, <0,2> = 3⋅2/2 + 2 = 5, etc. The basic idea is to order all the pairs by increasing x+y, and then order pairs with the same value of x+y by increasing y; eventually every pair is reached.

• ℕ^* = { all finite sequences of elements of ℕ } has size ℵ₀. One way to do this to define a function recursively by setting f([]) = 0 and f([first, rest]) = 1+<first,f(rest)>, where first is the first element of the sequence and rest is all the other elements. In class, we did the example f(0,1,2) = 1+<0,f(1,2)> = 1+<0,1+<1,f(2)>> = 1+<0,1+<1,1+<2,0>>> = 1+<0,1+<1,1+3>> = 1+<0,1+<1,4>> = 1+<0,1+19> = 1+<0,20> = 1+230 = 231. This assigns a unique element of ℕ to each finite sequence, which is enough to show |ℕ^*| ≤ |ℕ|; in fact, with some effort one can show that f is a bijection.

24.2. Countable sets

All of these sets have the property of being countable, which means that they can be put into a bijection with ℕ or one of its subsets. The general principle is that any sum or product of infinite cardinal numbers turns into taking the maximum of its arguments. The last case implies that anything you can write down using finitely many symbols (even if they are drawn from an infinite but countable alphabet) is countable. This has a lot of applications in computer science: one of them is that the set of all computer programs in any particular programming language is countable.

24.3. Uncountable sets

Exponentiation is different. We can easily show that 2^ℵ₀ ≠ ℵ₀, or equivalently that there is no bijection between ℘ℕ and ℕ. This is done using Cantor's diagonalization argument.

Theorem

Let S be any set. Then there is no surjection f:S→℘S.

Proof

Let f:S→℘S be some function from S to subsets of S. We'll construct a subset of S that f misses. Let A = { x∈S | x∉f(x) }. Suppose A = f(y). Then y∈A ↔ y∉A, a contradiction. (Exercise: Why does A exist even though the Russell's Paradox set doesn't?)

Since any bijection is also a surjection, this means that there's no bijection between S and ℘S either, implying, for example, that |ℕ| is strictly less than |℘ℕ|.

(On the other hand, it is the case that |ℕ^ℕ| = |2^ℕ|, so things are still weird up here.)

Sets that are larger than ℕ are called uncountable. A quick way to show that there is no surjection from A to B is to show that A is countable but B is uncountable. For example:

Corollary

There are functions f:ℕ→{0,1} that are not computed by any computer program.

Proof

Let P be the set of all computer programs that take a natural number as input and always produce 0 or 1 as output (assume some fixed language), and for each program p ∈ P, let f_p be the function that p computes. We've already argued that P is countable (each program is a finite sequence drawn from a countable alphabet), and since the set of all functions f:ℕ→{0,1} = 2^ℕ has the same size as ℘ℕ, it's uncountable. So some f gets missed: there is at least one function from ℕ to {0,1} that is not equal to f_p for any program p.

The fact that there are more functions from ℕ to ℕ than there are elements of ℕ is one of the reasons why set theory (slogan: "everything is a set") beat out lambda calculus (slogan: "everything is a function from functions to functions") in the battle over the foundations of mathematics. And this is why we do set theory in CS202 and lambda calculus gets put in CS201.

25. Further reading

See RosenBook §§2.1–2.2, BiggsBook Chapter 2, or Naive set theory.

CategoryMathNotes

The natural numbers are the set ℕ = { 0, 1, 2, 3, .... }. These correspond to all possible sizes of finite sets; in a sense, the natural numbers are precisely those numbers that occur in nature: one can have a field with 0, 1, 2, 3, etc. sheep in it, but it's hard to have a field with -12 or 22/7 sheep in it.

Warning: While this is definition of ℕ is almost universally used in computer science, and is used in RosenBook, some mathematicians—including the author of BiggsBook—leave zero out of the natural numbers. There are several possible reasons why you might do this:

• You were born well before the invention of zero approximately two millenia back by the ancient Indians, Babylonians, and/or Mayans.
• You were taught by extremely conservative schoolmasters who still hadn't got a handle on this newfangled zero thing.
• You live in a country that is so rich in sheep that the thought of a field with no sheep in it seems unnatural.
• You are a number theorist, and you don't want to have follow "Let n be a natural number..." with "(except zero)" in every theorem you write.

My suspicion is that Biggs falls into the last category (and might fall into some of the earlier ones). For the purposes of CS202 we will adopt the usual convention in ComputerScience and start the naturals at zero. However, you should keep an eye out for assumptions that the natural numbers don't include zero. The terms positive integers (for {1, 2, 3, ...}) and non-negative integers (for {0, 1, 2, 3, ...}) can also be helpful for avoiding confusion.

27. Axioms

There are several different ways to define the naturals. That these definitions all yield the same object is one of the reasons why they are so natural.

27.1. Peano axioms

The PeanoAxioms define the natural numbers directly from logic. It is not hard to show that the usual natural numbers satisfy these axioms (whether or not you throw out zero). Unfortunately, the Peano axioms by themselves don't give us many of the usual operations (like addition and multiplication) that we expect to be able to do to numbers.

27.2. Set-theoretic definition

In SetTheory, a natural number is defined as a finite¹ set x such that (a) every element y of x is also a subset of x, and (b) every element y of x is also a natural number. The existence of the set of natural numbers is asserted by the Axiom of Infinity. The smallest natural number is the empty set, which we take as representing 0. Next is 1 = { 0 }, 2 = { 0, 1 }, 3 = { 0, 1, 2 }, etc. It can easily be verified that each natural number defined in this way is indeed a subset of the next. It's not hard to show that these set-theoretic natural numbers satisfy the Peano axioms, and it's possible to define addition and multiplication operations on them that satisfy the arithmetic and order axioms below (we'll see more of this in HowToCount). Ordering is by inclusion: for the set-theoretic definition, n < m just in case n is an element of m.

27.3. Arithmetic and order axioms

Axioms for arithmetic in ℕ-{0} are given in Section 4.1 of BiggsBook. RosenBook doesn't spend much time on axiomatizing the naturals, relying instead on the deep intuition about natural numbers that most of us had trained into us from early childhood.

You've probably already seen all of the usual axioms early in your mathematical education, with the possible exception of mz = nz implies m = n. Note that unlike the other axioms, this one does not extend to ℕ, since m⋅0 = n⋅0 = 0 for any m and n. An extended list of axioms for ℕ including zero might look like

1. a+b is in ℕ. [Closure under addition]
2. a⋅b is in ℕ. [Closure under multiplication]
3. a+b = b+a. [Commutativity of addition]
4. (a+b)+c = a+(b+c). [Associativity of addition]
5. ab = ba. [Commutativity of multiplication]
6. (ab)c = a(bc). [Associativity of multiplication]
7. There is an element 1 of ℕ such that n1 = n for all n. [Multiplicative identity]
8. mz = nz implies m = n when z ≠ 0 (see below for 0). [Multiplicative cancellation]
9. a(b+c) = ab+ac. [Distributivity of multiplication over addition]

10. For any m and n, exactly one of n < m, n = m, or n > m is true. [Trichotomy]

11. There is an element 0 of ℕ such that n+0 = n for all n. [Additive identity]
12. 0a = 0. [Multiplicative annihilator]

The numbering follows BiggsBook, except for the last two axioms, which don't appear in BiggsBook outside of Exercise 4.1.3.

Note that < is defined in terms of +. In our terms, n < m means that there exists some x such that x is not equal to 0 and n+x = m.

One problem with these axioms (as compared to the Peano axioms) is that they are not very restrictive: they work equally well for e.g. the non-negative reals or the non-negative rationals, and extend to all of the reals or the rationals if we adjust the definition of <. So the arithmetic axioms can't be used as a definition of the naturals, even though they are much more convenient for doing actual arithmetic than the more basic definitions.

Much of the work in logic in the early 20th century involved showing that addition, multiplication, etc. could be defined in terms of much more primitive operations like successor, and that the operations so defined behaved the way we'd expect. This program was not always popular with non-logicians: as Henri_Poincaré put it (quoted in Bell and Machover's A Course in Mathematical Logic, North-Holland, 1977): "On the contrary, I find nothing in logistic for the discoverer but shackles. It does not help us at all in the direction of conciseness, far from it: and if it requires 27 equations to establish that 1 is a number, how many will it requires to demonstrate a real theorem?" Thankfully, we get to build on these efforts, and can treat the arithmetic axioms as our own convenient library of lemmas rather than having to reach down into the raw logical swamps.

27.3.1. Formal definition of arithmetic operations in terms of successor

Here's a formal definition of + in terms of successor:

1. ∀x 0+x = x.
2. ∀x ∀y Sx+y = x+Sy.

This defines the sum of two natural numbers uniquely because we can use the second rule to move all the S's off of the first addend onto the second one, until we get down to zero (recall that under the PeanoAxioms a natural number like 37 is really just a convenient shorthand for SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS0).

Here's multiplication:

1. ∀x 0x = 0.
2. ∀x ∀y (Sx)y = xy + y.

With the above rules for addition, this lets us multiply any two numbers very slowly: SS0⋅SS0 = (S0⋅SS0) + SS0 = ((0⋅SS0) + SS0) + SS0 = (0 + SS0) + SS0 = SS0 + SS0 = S0 + SSS0 = 0 + SSSS0 = SSSS0. Normal people write this as 2⋅2 = 4 and skip all the S's.

Here's <:

1. x < y ⇔ ∃z (z ≠ 0 ∧ x+z = y).

Note that this fails badly if z ranges over a larger set, like the integers.

With enough time on your hands, it is in principle possible to prove all of the arithmetic axioms given earlier hold for these definitions of +, ⋅, and <.

28. Order properties

The < relation is a total order (see Relations). This means that in addition to trichotomy, transitivity holds: a < b and b < c implies a < c. Transitivity can be proved from the definition of < and axioms 1-12; see Exercise 4.2.1 in BiggsBook.

However, < is even stronger than this: it is also a well order. This means that any subset of the natural numbers has a least element, which is the key to carrying out InductionProofs.

CategoryMathNotes

PDF version

31. Simple induction

Most of the ProofTechniques we've talked about so far are only really useful for proving a property of a single object (although we can sometimes use generalization to show that the same property is true of all objects in some set if we weren't too picky about which single object we started with). Mathematical induction (which mathematicians just call induction) is a powerful technique for showing that some property is true for many objects, where you can use the fact that it is true for small objects as part of the proof that it is true for large objects.

The basic framework for induction is as follows: given a sequence of statements P(0), P(1), P(2), we'll prove that P(0) is true (the base case), and then prove that for all k, P(k) ⇒ P(k+1) (the induction step). We then conclude that P(n) is in fact true for all n.

31.1. Why induction works

There are three ways to show that induction works, depending on where you got your natural numbers from.

Peano axioms

If you start with the PeanoAxioms, induction is one of them. Nothing more needs to be said.

Well-ordering of the naturals

A set is well-ordered if every subset has a smallest element. (An example of a set that is not well-ordered is the integers ℤ.) If you build the natural numbers using 0 = { } and x+1 = x ∪ {x}, it is possible to prove that the resulting set is well-ordered. Because it is well-ordered, if P(n) does not hold for all n, there is a smallest n for which P(n) is false. But then either this n = 0, contradicting the base case, or P(n-1) is true (because otherwise n would not be the smallest) and P(n) is false, contradicting the induction step.

Method of infinite descent

The original version, due to Fermat, goes like this: Suppose P(n) is false for some n > 0. Since P(n-1) ⇒ P(n) is logically equivalent to ¬P(n) ⇒ ¬P(n-1), we can conclude (using the induction step) ¬P(n-1). Repeat until you reach 0. The problem with this version is that the "repeat" step is in effect using an induction argument. The modern solution to this problem is to recast the argument to look like the well-ordering argument above, by assuming that n is the smallest n for which P(n) is false and asserting a contradiction once you prove ¬P(n-1). Historical note: Fermat may have used this technique to construct a plausible but invalid proof of his famous "Last Theorem" that aⁿ+bⁿ=cⁿ has no non-trivial integer solutions for n > 2.

31.2. Examples

• The PigeonholePrinciple.

• The number of subsets of an n-element set is 2ⁿ.

• 1+3+5+7+...+(2n+1) = (n+1)².

• 2ⁿ > n² for n ≥ 5.

32. Strong induction

Sometimes when proving that the induction hypothesis holds for n+1, it helps to use the fact that it holds for all n' < n+1, not just for n. This sort of argument is called strong induction. Formally, it's equivalent to simple induction: the only difference is that instead of proving ∀k P(k) ⇒ P(k+1), we prove ∀k (∀m≤k Q(m)) ⇒ Q(k+1). But this is exactly the same thing if we let P(k) ≡ ∀m≤k Q(m), since if ∀m≤k Q(m) implies Q(k+1), it also implies ∀m≤k+1 Q(m), giving us the original induction formula ∀k P(k) ⇒ P(k+1).

32.1. Examples

• Every n > 1 can be factored into a product of one or more prime numbers. Proof: By induction on n. The base case is n = 2, which factors as 2 = 2 (one prime factor). For n > 2, either (a) n is prime itself, in which case n = n is a prime factorization; or (b) n is not prime, in which case n = ab for some a and b, both greater than 1. Since a and b are both less than n, by the induction hypothesis we have a = p₁p₂...p_k for some sequence of one or more primes and similarly b = p'₁p'₂...p'_k'. Then n = p₁p₂...p_kp'₁p'₂...p'_k' is a prime factorization of n.

• Every deterministic bounded two-player perfect-information game that can't end in a draw has a winning strategy for one of the players. A perfect-information game is one in which both players know the entire state of the game at each decision point (like Chess or Go, but unlike Poker or Bridge); it is deterministic if there is no randomness that affects the outcome (this excludes Backgammon and Monopoly, some variants of Poker, and multiple hands of Bridge), and it's bounded if the game is guaranteed to end in at most a fixed number of moves starting from any reachable position (this also excludes Backgammon and Monopoly). Proof: For each position x, let b(x) be the bound on the number of moves made starting from x. Then if y is some position reached from x in one move, we have b(y) < b(x) (because we just used up a move). Let f(x) = 1 if the first player wins starting from position x and f(x) = 0 otherwise. We claim that f is well-defined. Proof: If b(x) = 0, the game is over, and so f(x) is either 0 or 1, depending on who just won. If b(x) > 0, then f(x) = max { f(y) | y is a successor to x } if it's the first player's turn to move and f(x) = min { f(y) | y is a successor to x } if it's the second player's turn to move. In either case each f(y) is well-defined (by the induction hypothesis) and so f(x) is also well-defined.

• The DivisionAlgorithm: for each n,m ∈ ℕ there is a unique q∈ℕ and a unique r∈ℕ such that n = qm+r and0≤r<m. Proof: Fix m then proceed by induction on n. If n < m, then if q > 0 we have n = qm+r ≥ 1⋅m ≥ m, a contradiction. So in this case q = 0 is the only solution, and since n = qm + r = r we have a unique choice of r = n. If n ≥ m, by the induction hypothesis there is a unique q' and r' such that n-m = q'm+r' where 0≤r'<m. But then q = q'+1 and r = r' satisfies qm+r = (q'-1+1)m+r = (q'm+r') + m = (n-m) + m = n. To show that this solution is unique, if there is some other q'' and r'' such that q''m+r'' = n, then (q''-1)m + r'' = n-m = q'm+r', and by the uniqueness of q' and r' (ind. hyp. again), we have q''-1 = q' = q-1 and r'' = r' = r, giving that q'' = q and r'' = r. So q and r are unique.

33. Recursion

A definition with the structure of an inductive proof (give a base case and a rule for building bigger structures from smaller ones) Structures defined in this way are recursively-defined.

Examples of recursively-defined structures:

Finite Von Neumann ordinals

A finite von Neumann ordinal is either (a) the empty set ∅, or (b) x ∪ { x }, where x is a finite von Neumann ordinal.

Complete binary trees

A complete binary tree consists of either (a) a leaf node, or (b) an internal node (the root) with two complete binary trees as children (or subtrees).

Boolean formulas

A boolean formula consists of either (a) a variable, (b) the negation operator applied to a Boolean formula, (c) the AND of two Boolean formulas, or (d) the OR of two Boolean formulas. A monotone Boolean formula is defined similarly, except that negations are forbidden.

Finite sequences, recursive version

Before we defined a finite sequence as a function from some natural number (in its set form: n = { 0, 1, 2, ..., n-1 }) to some range. We could also define a finite sequence over some set S recursively, by the rule: [ ] (the empty sequence) is a finite sequence, and if a is a finite sequence and x∈S, then (x,a) is a finite sequence. (Fans of LISP will recognize this method immediately.)

Key point is that in each case the definition of an object is recursive---the object itself may appear as part of a larger object. Usually we assume that this recursion eventually bottoms out: there are some base cases (e.g. leaves of complete binary trees or variables in Boolean formulas) that do not lead to further recursion. If a definition doesn't bottom out in this way, the class of structures it describes might not be well-defined (i.e., we can't tell if some structure is an element of the class or not).

33.1. Recursively-defined functions

We can also define functions on recursive structures recursively:

The depth of a binary tree

For a leaf, 0. For a tree consisting of a root with two subtrees, 1+max(d₁, d₂), where d₁ and d₂ are the depths of the two subtrees.

The value of a Boolean formula given a particular variable assignment

For a variable, the value (true or false) assigned to that variable. For a negation, the negation of the value of its argument. For an AND or OR, the AND or OR of the values of its arguments. (This definition is not quite as trivial as it looks, but it's still pretty trivial.)

Or we can define ordinary functions recursively:

The Fibonacci series

Let F(0) = F(1) = 1. For n > 1, let F(n) = F(n-1) + F(n-2).

Factorial

Let 0! = 1. For n > 0, let n! = n × (n-1)!.

33.2. Recursive definitions and induction

Recursive definitions have the same form as an induction proof. There are one or more base cases, and one or more recursion steps that correspond to the induction step in an induction proof. The connection is not surprising if you think of a definition of some class of objects as a predicate that identifies members of the class: a recursive definition is just a formula for writing induction proofs that say that certain objects are members.

Recursively-defined objects and functions also lend themselves easily to induction proofs about their properties; on general structures, such induction arguments go by the name of structural induction.

34. Structural induction

For finite structures, we can do induction over the structure. Formally we can think of this as doing induction on the size of the structure or part of the structure we are looking at.

Examples:

Every complete binary tree with n leaves has n-1 internal nodes

Base case is a tree consisting of just a leaf; here n = 1 and there are n - 1 = 0 internal nodes. The induction step considers a tree consisting of a root and two subtrees. Let n₁ and n₂ be the number of leaves in the two subtrees; we have n₁+n₂ = n; and the number of internal nodes, counting the nodes in the two subtrees plus one more for the root, is (n₁-1)+(n₂-1)+1 = n₁+n₂ - 1 = n-1.

Monotone Boolean formulas generate monotone functions

What this means is that changing a variable from false to true can never change the value of the formula from true to false. Proof is by induction on the structure of the formula: for a naked variable, it's immediate. For an AND or OR, observe that changing a variable from false to true can only leave the values of the arguments unchanged, or change one or both from false to true (induction hypothesis); the rest follows by staring carefully at the truth table for AND or OR.

Bounding the size of a binary tree with depth d

We'll show that it has at most 2^d+1-1 nodes. Base case: the tree consists of one leaf, d = 0, and there are 2⁰⁺¹-1 = 2-1 = 1 nodes. Induction step: Given a tree of depth d > 1, it consists of a root (1 node), plus two subtrees of depth at most d-1. The two subtrees each have at most 2^d-1+1-1 = 2^d-1 nodes (induction hypothesis), so the total number of nodes is at most 2(2^d-1)+1 = 2^d+1+2-1 = 2^d+1-1.

CategoryMathNotes

PDF version

36. Summations

Summations are the discrete versions of integrals; given a sequence x_a, x_a+1, ..., x_b, its sum x_a + x_a+1 + ... + x_b is written as

The large jagged symbol is a stretched-out version of a capital Greek letter sigma. The variable i is called the index of summation, a is the lower bound or lower limit, and b is the upper bound or upper limit. Mathematicians invented this notation centuries ago because they didn't have for loops; the intent is that you loop through all values of i from a to b (including both endpoints), summing up the argument of the ∑ for each i.

If b < a, then the sum is zero. For example,

This rule mostly shows up as an extreme case of a more general formula, e.g.

which still works even when n=0 or n=-1 (but not for n=-2).

Summation notation is used both for laziness (it's more compact to write

than 1 + 3 + 5 + 7 + ... + (2n+1)) and precision (it's also more clear exactly what you mean).

36.1. Formal definition

For finite sums, we can formally define the value by either of two recurrences:

In English, we can compute a sum recursively by computing either the sum of the last n-1 values or the first n-1 values, and then adding in the value we left out. (For infinite sums we need a different definition; see below.)

36.2. Choosing and replacing index variables

When writing a summation, you can generally pick any index variable you like, although i, j, k, etc. are popular choices. Usually it's a good idea to pick an index that isn't used outside the sum. Though

has a well-defined meaning, the version on the right-hand side is a lot less confusing.

In addition to renaming indices, you can also shift them, provided you shift the bounds to match. For example, rewriting

as

(by substituting j for i-1) makes the sum more convenient to work with.

36.3. Scope

The scope of a summation extends to the first addition or subtraction symbol that is not enclosed in parentheses or part of some larger term (e.g., in the numerator of a fraction). So

Since this can be confusing, it is generally safest to wrap the sum in parentheses (as in the second form) or move any trailing terms to the beginning. An exception is when adding together two sums, as in

Here the looming bulk of the second Sigma warns the reader that the first sum is ending; it is much harder to miss than the relatively tiny plus symbol in the first example.

36.4. Sums over given index sets

Sometimes we'd like to sum an expression over values that aren't consecutive integers, or may not even be integers at all. This can be done using a sum over all indices that are members of a given index set, or in the most general form satisfy some given predicate (with the usual set-theoretic caveat that the objects that satisfy the predicate must form a set). Such a sum is written by replacing the lower and upper limits with a single subscript that gives the predicate that the indices must obey.

For example, we could sum i² for i in the set {3,5,7}:

Or we could sum the sizes of all subsets of a given set S:

Or we could sum the inverses of all prime numbers less than 1000:

Sometimes when writing a sum in this form it can be confusing exactly which variable or variables are the indices. The usual convention is that a variable is always an index if it doesn't have any meaning outside the sum, and if possible the index variable is put first in the expression under the Sigma if possible. If it is not obvious what a complicated sum means, it is generally best to try to rewrite it to make it more clear; still, you may see sums that look like

or

where the first sum sums over all pairs of values (i,j) that satisfy the predicate, with each pair appearing exactly once, and the second sums over all sets A that are subsets of S and contain x (assuming x and S are defined outside the summation). Hopefully, you will not run into too many sums that look like this, but it's worth being able to decode them if you do.

Sums over a given set are guaranteed to be well-defined only if the set is finite. In this case we can use the fact that there is a bijection between any finite set S and the ordinal |S| to rewrite the sum as a sum over indices in |S|. For example, if |S| = n, then there exists a bijection f:{0..n-1}↔S, so we can define

If S is infinite, this is trickier. For countable S, where there is a bijection f:ℕ↔S, we can sometimes rewrite

and use the definition of an infinite sum (given below). Note that if the x_i have different signs the result we get may depend on which bijection we choose. For this reason such infinite sums are probably best avoided unless you can explicitly use ℕ as the index set.

36.5. Sums without explicit bounds

When the index set is understood from context, it is often dropped, leaving only the index, as in ∑_i i². This will generally happen only if the index spans all possible values in some obvious range, and can be a mark of sloppiness in formal mathematical writing. Theoretical physicists adopt a still more lazy approach, and leave out the ∑_i part entirely in certain special types of sums: this is known as the Einstein summation convention after the notoriously lazy physicist who proposed it.

36.6. Infinite sums

Sometimes you may see an expression where the upper limit is infinite, as in

The meaning of this expression is the limit of the series s obtained by taking the sum of the first term, the sum of the first two terms, the sum of the first three terms, etc. The limit converges to a particular value x if for any ε>0, there exists an N such that for all n > N, the value of s_n is within ε of x (formally, |s_n-x| < ε). We will see some examples of infinite sums when we look at GeneratingFunctions.

36.7. Double sums

Nothing says that the expression inside a summation can't be another summation. This gives double sums, such as in this rather painful definition of multiplication for non-negative integers:

If you think of a sum as a for loop, a double sum is two nested for loops. The effect is to sum the innermost expression over all pairs of values of the two indices.

Here's a more complicated double sum where the limits on the inner sum depend on the index of the outer sum:

When n=1, this will compute (0+1)(0+1) + (1+1)(0+1) + (1+1)(1+1) = 7. For larger n the number of terms grows quickly.

There are also triple sums, quadruple sums, etc.

37. Computing sums

When confronted with some nasty sum, it is nice to be able to convert into a simpler expression that doesn't contain any Sigmas. It is not always possible to do this, and the problem of finding a simpler expression for a sum is very similar to the problem of computing an integral (see HowToIntegrate): in both cases the techniques available are mostly limited to massaging the summation until it turns into something whose simpler expression you remember. To do this, it helps to both (a) have a big toolbox of sums with known values, and (b) have some rules for manipulating summations to get them into a more convenient form. We'll start with the toolbox.

37.1. Some standard sums

Here are the three formula you should either memorize or remember how to derive:

Rigorous proofs of these can be obtained by induction on n.

For not so rigorous proofs, the second identity can be shown (using a trick alleged to have been invented by the legendary 18th-century mathematician Carl_Friedrich_Gauss at a frighteningly early age; see here for more details on this legend) by adding up two copies of the sequence running in opposite directions, one term at a time:

 S =     1    +    2     +     3    +   ....   +   n
 S =     n    +   n-1    +    n-2   +   ....   +   1
------------------------------------------------------
2S =   (n+1)  +  (n+1)   +   (n+1)  +   ....   + (n+1) = n(n+1),

and from 2S=n(n+1) we get S = n(n+1)/2.

For the last identity, start with

which holds when |r| < 1. The proof is that if

then

and so

Solving for S then gives S = 1/(1-r).

We can now get the sum up to n by subtracting off the extra terms starting with rⁿ⁺¹:

Amazingly enough, this formula works even when r is greater than 1. If r is equal to 1, then the formula doesn't work (it requires dividing zero by zero), but there is an easier way to get the solution.

Other useful sums can be found in various places. RosenBook and ConcreteMathematics both provide tables of sums in their chapters on GeneratingFunctions. But it is usually better to be able to reconstruct the solution of a sum rather than trying to memorize such tables.

37.2. Summation identities

The summation operator is linear. This means that constant factors can be pulled out of sums:

and sums inside sums can be split:

With multiple sums, the order of summation is not important, provided the bounds on the inner sum don't depend on the index of the outer sum:

Products of sums can be turned into double sums of products and vice versa:

These identities can often be used to transform a sum you can't solve into something simpler.

37.3. What to do if nothing else works

If nothing else works, you can try using the guess but verify method, which is a variant on the same method for identifying sequences. Here we write out the values of the sum for the first few values of the upper limit (for example), and hope that we recognize the sequence. If we do, we can then try to prove that a formula for the sequence of sums is correct by induction.

Example: Suppose we want to compute

but that it doesn't occur to us to split it up and use the ∑k and ∑1 formulas. Instead, we can write down a table of values:

At this point we might guess that S(n) = n². To verify this, observe that it holds for n=0, and for larger n we have S(n) = S(n-1) + (2n-1) = (n-1)² + 2n - 1 = n² - 2n + 1 - 2n - 1 = n². So we can conclude that our guess was correct.

If this doesn't work, you could always try using GeneratingFunctions.

37.4. Strategies for asymptotic estimates

Mostly in AlgorithmAnalysis we do not need to compute sums exactly, because we are just going to wrap the result up in some asymptotic expression anyway (see AsymptoticNotation). This makes our life much easier, because we only need an approximate solution.

Here's my general strategy for computing sums:

37.4.1. Pull out constant factors

Pull as many constant factors out as you can (where constant in this case means anything that does not involve the summation index). Example:

37.4.2. Bound using a known sum

See if it's bounded above or below by some other sum whose solution you already know. Good sums to try (you should memorize all of these):

37.4.2.1. Geometric series

The way to recognize a geometric series is that the ratio between adjacent terms is constant. If you memorize the second formula, you can rederive the first one. If you're Carl_Friedrich_Gauss, you can skip memorizing the second formula.

A useful trick to remember for geometric series is that if x is a constant that is not exactly 1, the sum is always big-Theta of its largest term. So for example

(the exact value is 2ⁿ⁺¹-2), and

(the exact value is 1-2^-n). This fact is the basis of the Master Theorem, described in SolvingRecurrences. If the ratio between terms equals 1, the formula doesn't work; instead, we have a constant series (see below).

37.4.2.2. Constant series

37.4.2.3. Arithmetic series

The simplest arithmetic series is

The way to remember this formula is that it's just n times the average value (n+1)/2. The way to recognize an arithmetic series is that the difference between adjacent terms is constant. The general arithmetic series is of the form

Because the general series expands so easily to the simplest series, it's usually not worth memorizing the general formula.

37.4.2.4. Harmonic series

Can be rederived using the integral technique given below or by summing the last half of the series, so this is mostly useful to remember in case you run across H_n (the n-th harmonic number).

37.4.3. Bound part of the sum

See if there's some part of the sum that you can bound. For example,

has a (painful) exact solution, or can be approximated by the integral trick described below, but it can very quickly be solved to within a constant factor by observing that

and

37.4.4. Integrate

Integrate. If f(n) is non-decreasing and you know how to integrate it, then

which is enough to get a big-Theta bound for almost all functions you are likely to encounter in algorithm analysis. If you don't remember how to integrate, see HowToIntegrate.

37.4.5. Grouping terms

Try grouping terms together. For example, the standard trick for showing that the harmonic series is unbounded in the limit is to argue that 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + ... ≥ 1 + 1/2 + (1/4 + 1/4) + (1/8 + 1/8 + 1/8 + 1/8) + ... ≥ 1 + 1/2 + 1/2 + 1/2 + ... . I usually try everything else first, but sometimes this works if you get stuck.

37.4.6. Oddities

One oddball sum that shows up occasionally but is hard to solve using any of the above techniques is

If a < 1, this is Θ(1) (the exact formula for

when a < 1 is a/(1-a)², which gives a constant upper bound for the sum stopping at n); if a = 1, it's just an arithmetic series; if a > 1, the largest term dominates and the sum is Θ(aⁿn) (there is an exact formula, but it's ugly—if you just want to show it's O(aⁿn), the simplest approach is to bound the series

by the geometric series

I wouldn't bother memorizing this one provided you bookmark this page.

37.4.7. Final notes

In practice, almost every sum you are likely to encounter in AlgorithmAnalysis will be of the form

where f(n) is exponential (so that it's bounded by a geometric series and the largest term dominates) or polynomial (so that f(n/2) = Θ(f(n)) and the sum is Θ(n f(n)) using the

lower bound).

ConcreteMathematics spends a lot of time on computing sums exactly. The most useful technique for doing this is to use GeneratingFunctions.

38. Products

What if you want to multiple a series of values instead of add them? The notation is the same as for a sum, except that you replace the Sigma with a Pi, as in this definition of the factorial function for non-negative n.

The other difference is that while an empty sum is defined to have the value 0, an empty product is defined to have the value 1. The reason for this rule (in both cases) is that an empty sum or product should return the identity element for the corresponding operation—the value that when added to or multiplied by some other value x doesn't change x. This allows writing general rules like:

which holds as long as A∩B=Ø. Without the rule that the sum of an empty set was 0 and the product 1, we'd have to put in a special case for when one or both of A and B were empty.

Note that a consequence of this definition is that 0! = 1.

39. Other big operators

Some more obscure operators also allow you to compute some aggregate over a series, with the same rules for indices, lower and upper limits, etc., as ∑ and ∏. These include:

• Big AND:

• Big OR:

• Big Intersection:

• Big Union:

These all behave pretty much the way one would expect. One issue that is not obvious from the definition is what happens with an empty index set. Here the rule as with sums and products is to return the identity element for the operation. This will be True for AND, False for OR, and the empty set for union; for intersection, there is no identity element in general, so the intersection over an empty collection of sets is undefined.

CategoryAlgorithmNotes CategoryMathNotes

Notes on solving recurrences. These are originally from CS365, and emphasize asymptotic solutions; for CS202 we recommend also looking at GeneratingFunctions.

43. The problem

A recurrence or recurrence relation defines an infinite sequence by describing how to calculate the n-th element of the sequence given the values of smaller elements, as in:

• T(n) = T(n/2) + n, T(0) = T(1) = 1.

In principle such a relation allows us to calculate T(n) for any n by applying the first equation until we reach the base case. To solve a recurrence, we will find a formula that calculates T(n) directly from n, without this recursive computation.

Not all recurrences are solvable exactly, but in most of the cases that arises in analyzing recursive algorithms, we can usually get at least an asymptotic (i.e. big-Theta) solution (see AsymptoticNotation).

By convention we only define T by a recurrence like this for integer arguments, so the T(n/2) by convention represents either T(floor(n/2)) or T(ceiling(n/2)). If we want an exact solution for values of n that are not powers of 2, then we have to be precise about this, but if we only care about a big-Theta solution we will usually get the same answer no matter how we do the rounding.² From this point on we will assume that we only consider values of n for which the recurrence relation does not produce any non-integer intermediate values.

44. Guess but verify

As when solving any other mathematical problem, we are not required to explain where our solution came from as long as we can prove that it is correct. So the most general method for solving recurrences can be called "guess but verify". Naturally, unless you are very good friends with the existential quantifier you may find it had to come up with good guesses. But sometimes it is possible to make a good guess by iterating the recurrence a few times and seeing what happens.

44.1. Forward substitution

Let's consider the recurrence

• T(n) = T(n-1) + 2n - 1
• T(0) = 0

The method of forward substitution proceeds by generating the first half-dozen or so terms in the sequence described by the recurrence, in the hope that it will turn out to be a sequence we recognize. In this case, we can calculate

• n	T(n)
  0	0
  1	1
  2	4
  3	9
  4	16
  5	25

and at this point we can shout "Aha! This example was carefully rigged to give T(n)=n²!". Unfortunately, there are infinitely many sequences that start with these six numbers, so we can't be fully sure that this is the right answer until we prove it. So let's do so.

We will show that T(n) = n² satisfies the above recurrence for all n, by induction on n. The base case is n = 0; here T(0) = 0 = 0². For n > 0, we have

• T(n) = T(n-1) + 2n - 1 = (n-1)² + 2n - 1 = n² - 2n + 1 + 2n - 1 = n²,

and we are done.

(Here we used the induction hypothesis where we replace T(n-1) by (n-1)². We will usually not be very explicit about this.)

Here's a less rigged example:

• T(n) = T(floor(n/2)) + n, T(0) = 0.

Computing small cases gives

• n	T(n)
  0	0
  1	1
  2	3
  3	4
  4	7
  5	8
  6	10
  7	11
  8	15

which doesn't really tell us much about the behavior for large values. We can easily add a few powers of 2 to get an idea of what happens later:

• 16	31
  32	63
  64	127

From this we might guess that the solution satisfies T(n) <= 2n (or perhaps T(n) <= 2n - 1 for n > 0). So let's see if we can prove it:

Base case

T(0) = 0 <= 2n.

Induction step

For n > 0, T(n) = T(floor(n/2) + n <= 2 floor(n/2) + n <= 2(n/2) + n = 2n.

We might be able to prove a slightly tighter bound with more work, but this is enough to sho T(n) = O(n). Showing that T(n) = Omega(n) is trivial (since T(n) >= n), so we get T(n) = Θ(n) and we are done.

Applying the method of forward substitution requires a talent for recognizing sequences from their first few elements. If you are not born with this talent, you can borrow it from the mathematician Neal J. A. Sloane, or at least from his on-line Encyclopedia of Integer Sequences.

44.2. Backward substitution

Backward substitution, like forward substitution, tries to find a pattern from which we can guess a solution that we then prove using other techniques---but now we start with T(n) and expand it recursively using the recurrence.

For example, if we consider the same T(n) = T(n/2) + n recurrence from above, and assume for simplicity that n is a power of 2, then we get

• T(n) = n + T(n/2) = n + n/2 + T(n/4) = n + n/2 + n/4 + T(n/8) = n + n/2 + n/4 + n/8 + T(n/16) = ...

From this we might reasonably guess that T(n) is bounded by

(See ComputingSums for how to compute this sum.) This is the same guess that we got from the method of forward substitution, so we prove that it works in the same way.

Note that in both methods we can omit how we got the guess from the final proof, though some readers might consider a refusal to explain a particularly good guess a form of teasing.

45. Converting to a sum

Some common recurrences appear often enough in AlgorithmAnalysis that it makes sense solve them once in general form, and then just apply the general solution as needed. You can either memorize these solutions, or, better yet, remember enough of how they are derived to be able to reconstruct them.

45.1. When T(n) = T(n-1) + f(n)

This is the easiest case, which usually appears in DecreaseAndConquer algorithms. Here it is easy to see (and can be proved by induction) that

Example: for T(n) = T(n-1) + n², we immediately have

which we can quickly show is Θ(n³) in any number of ways (see ComputingSums).

45.2. When T(n) = aT(n-1) + f(n)

This is a little trickier, because as the arguments to the f's drop, they are multiplied by more and more a's. After some backward substitution it is not hard to recognize the pattern

Example: T(n) = 2T(n-1) + n. Then from the formula

This turns out to be a rather painful sum to solve exactly, but we can reasonably guess that it's somewhere between 2ⁿ and 2ⁿn, and try guess-but-verify to whittle the range down further.

45.3. When T(n) = aT(n/b) + f(n)

This form of recurrence tends to arise from DivideAndConquer algorithms. For n = b^k, n/b = b^k-1, which makes this recurrence a thinly-disguised version of the last one. We thus have

where log_b x = log x / log b, the base-b logarithm of x.

These sums can get ugly fast. Here's an unusually clean case:

• T(n) = 2T(n/2) + n.

Then

provided, of course, that n is a power of 2. For values of n that are not powers of 2, or for less conveniently constructed recurrences of this form, it is often better to skip directly to the Master Theorem.

46. The Master Theorem

The Master Theorem provides instant asymptotic solutions for many recurrences of the form T(n) = aT(n/b) + f(n), that apply for all values of n (not just powers of b). It is based on applying the analysis of the preceding section to various broad families of functions f, and then extending the results using a monotonicity argument to values of n that are not powers of b. Here we sketch out the proof; see LevitinBook Appendix B for a more detailed argument.

If f(n) = 0, then the recurrence is simply T(n) = aT(n/b). This has solution T(n) = n^{log[b] a} T(1) = Θ(n^{log[b] a}). (Example: T(n) = 4T(n/2) has solution Θ(n^{lg 4}) = Θ(n²).) We classify different cases of the Master Theorem based on how f(n) compares to this default solution.

Recall that the general solution is

• T(n) = Sigma,,i=0 to log[b] n - 1 aⁱ f(n/bⁱ) + n^{log[b] a} T(1).

We assume that T(1) = Θ(1) throughout.

Suppose that f(x) = x^c. Then aⁱ f(n/bⁱ) = aⁱ n^c / b^ic = n^c (a/b^c)ⁱ. The sum is then a geometric series with ratio (a/b^c), and its behavior depends critically on whether (a/b^c) is less than 1, equal to 1, or greater than 1.

If (a/b^c) is less than 1, then Sigma_{i=0 to infinity} n^c (a/b^c)ⁱ = n^c/(1-(a/b^c)) = O(n^c). This case arises when log(a/b^c) = log a - c log b is less than zero, which occurs precisely when c > log a / log b = log_b a. So if f(n) = n^c, the f(n) term in the sum dominates both the rest of the sum and the n^{log[b] a} term, and we get T(n) = Θ(f(n)). If f(n) is Omega(n^c), but satisfies the additional technical requirement that af(n/b) <= (1-delta) f(n) for all n and some fixed delta > 0, then the geometric series argument still works with factor (1-delta), and we still get T(n) = Θ(f(n)). This covers the case where f(n) = Omega(n^{log[b] a + epsilon}).

If (a/b^c) is equal to 1, then every term in the sum is the same, and the total is f(n) log_b n. In this case c = log_b a, so f(n) = n^{log[b] a} and f(n) log_b n dominates (barely) the T(1) term. An extended version of this analysis shows that the solution is T(n) = Θ(f(n) log n) when f(n) = Θ(n^{log[b] a}).

Finally, if (a/b^c) is greater than 1, we have a geometric series whose sum is proportional to its last term, which can be shown to be asymptotically smaller than the T(1) term. This case gives T(n) = Θ(n^{log[b] a}) for any f(n) = O(n^{log[b] a - epsilon}).

Summarizing, we have

1. If f(n) = O(n^{log[b] a - epsilon}), then T(n) = Θ(n^{log[b] a}).

2. If f(n) = Θ(n^{log[b] a}), then T(n) = Θ(f(n) log n).

3. If f(n) = Omega(n^{log[b] a + epsilon}), and there exists c < 1 such that a f(n/b) <= c f(n), then T(n) = Θ(f(n)).

These three cases do not cover all possibilities (consider T(n) = 2T(n/2) + n log n), but they will handle most recurrences of this form you are likely to encounter.

CategoryAlgorithmNotes CategoryMathNotes

PDF version

49. What counting is

Recall that in SetTheory we formally defined each natural number as the set of all smaller natural numbers, so that n = { 0, 1, 2, ..., n-1 }. Call a set finite if it can be put in one-to-one correspondence with some natural number n. For example, the set S = { Larry, Moe, Curly } is finite because we can map Larry to 0, Moe to 1, and Curly to 2, and get a bijection between S and the set 3 = { 0, 1, 2 }. The size or cardinality of a finite set S, written |S| or #S, is just the natural number it can be put in one-to-one correspondence with; that this is well-defined (gives a unique size for each finite set) follows from the Pigeonhole Principle (see below). In general, a cardinal number is a representative of some class of sets that can all put connected to each other by bijections; these include infinite cardinal numbers, discussed below.

Usually we will not provide an explicit bijection to compute the size of a set, but instead will rely on standard counting principles (see below). A proof that a set has a certain size (or that two sets have the same size) that does provide an explicit bijection is called a combinatorial proof. For sets of complicated objects, such proofs often provide additional insight into the structure of the objects.

49.1. Countable and uncountable sets

A set S is infinite if there is a bijection between S and some proper subset of S (proper subset means a subset that isn't equal to S), or equivalently if it can't be put in one-to-one correspondence with any natural number. One of the smallest infinite sets is just the set of all naturals ℕ. Any infinite set also has a cardinality; as for finite sets, the cardinality of an infinite set is defined based on what other sets it can be put into one-to-one correspondence with, and different infinite sets may have different cardinalities.

The smallest cardinality is ℵ₀ (pronounced aleph-nought), the cardinality of ℕ. Any set S for which there exists a bijection f:S↔ℕ has cardinality ℵ₀. Examples include the set of all pairs of natural numbers (which can be mapped to single natural numbers using various encodings), the set of integers ℤ, the set of rationals ℚ, the set of all finite sequences of natural numbers (using more sophisticated encodings), the set of all computer programs (represent them as sequences of natural numbers, e.g., using ASCII encoding), the set of all possible finite-length texts in any language with a countable output, or the set of all mathematical objects that can be explicitly defined (each such definition is a finite text).

Sets with cardinality ℵ₀ or less are called countable; sets with cardinality exactly ℵ₀ are countably infinite.

That there are larger cardinalities is a consequence of a famous proof due to Georg Cantor, the diagonalization argument:

Theorem

Let S be any set. Then there is no surjection f:S→℘S.

Proof

Let f:S→℘S. We will show that f is not surjective, by constructing a subset A of S such that A≠f(x) for any x in S. Let A = { x | x∉f(x) }. Now choose some x and consider f(x). We have x∈A if and only if x∉f(x); so x is in exactly one of A and f(x), and in particular A≠f(x). It follows that A≠f(x) for all x, and thus that A isn't in the range of f.

Since any bijection is also a surjection, this means that |S| ≠ |℘S|. For finite sets, this is pretty easy to show directly: it just says that n<2ⁿ for all natural numbers n. For infinite sets, it means, for example, that |ℕ| ≠ |℘ℕ|, or equivalently that |℘ℕ| > ℵ₀. This means that ℘ℕ is uncountable.

The next largest cardinal after ℵ₀ is called ℵ₁ (aleph-one). The standard axioms of SetTheory provably can't tell us whether |℘ℕ| = ℵ₁ or not, but if we assume the Continuum hypothesis we can assert that |℘ℕ| = ℵ₁. In this case ℵ₁ not only gives the cardinality of the power set of the naturals, but also the cardinality of the set of real numbers ℝ, the set of complex numbers ℂ, the set of finite sequences of reals, etc. It does not give the cardinality of ℘ℝ or the set of functions f:ℝ→ℝ; these live (assuming a strengthened version of the Continuum hypothesis) up at ℵ₂.

Because Cantor's theorem applies even to these bigger sets, there is an infinite sequence of increasingly large cardinalities ℵ₀, ℵ₁, ℵ₂, ℵ₃, ... . Pretty much anything past about ℵ₁ falls into the category of incomprehensibly large (not an actual mathematical term).

50. Basic counting techniques

Our goal here is to compute the size of some set of objects, e.g. the number of subsets of a set of size n, the number of ways to put k cats into n boxes so that no box gets more than one cat, etc.

In rare cases we can use the definition of the size of a set directly, by constructing a bijection between the set we care about and some natural number. For example, the set S_n = { x ∈ ℕ | x < n² /\ ∃y: x = y² } has exactly n members, because we can generate it by applying the one-to-one correspondence f(y) = y² to the set { 0, 1, 2, 3, ..., n-1 } = n. But most of the time constructing an explicit one-to-one correspondence is too time-consuming or too hard, so having a few lemmas around that tell us what the size of a set will be can be handy.

50.1. Reducing to a previously-solved case

If we can produce a bijection between a set A whose size we don't know and a set B whose size we do, then we get |A|=|B|. Pretty much all of our proofs of cardinality will end up looking like this.

50.2. Showing |A| ≤ |B| and |B| ≤ |A|

We write |A| ≤ |B| if there is an injection f:A→B, and similarly |B| ≤ |A| if there is an injection g:B→A. If both conditions hold, then there is a bijection between A and B, showing |A| = |B|. This fact is trivial for finite sets (it is a consequence of the Pigeonhole Principle), but for infinite sets—even though it is still true—the actual construction of the bijection is a little trickier. See Cantor-Bernstein-Schroeder theorem if you really want the gory details.

Similarly, if we write |A| ≥ |B| to indicate that there is a surjection from A to B, then |A| ≥ |B| and |B| ≥ |A| implies |A| = |B|. The easiest way to show this is to observe that if there is a surjection f:A→B, then we can get an injection f':B→A by letting f'(y) be any element of { x | f(x) = y } (this requires the Axiom of Choice, but pretty much everybody assumes the Axiom of Choice).

Examples:

• |ℚ| = |ℕ|. Proof: |ℕ| ≤ |ℚ| because we can map any n in ℕ to the same value in ℚ; this is clearly an injection. To show |ℚ| ≤ |ℕ|, observe that we can encode any element ±p/q of ℚ, where p and q are both natural numbers, as a triple <sign, p, q> where sign ∈ {0,1} indicates + (0) or - (1); this encoding is clearly injective. Then use the bijection from ℕ×ℕ to ℕ twice to crunch this triple down to a single natural number, getting an injection from ℚ to ℕ.

50.3. Sum rule

The sum rule says

• If A∩B=Ø, then |A∪B| = |A| + |B|.

Proof: Let f:A→|A| and g:B→|B| be bijections. Define h:A∪B→(|A|+|B|) by the rule h(x) = f(x) for x∈A, h(x) = |A|+g(x) for x∈B. We need to show that h is a bijection; we will do so by first showing that it is injective, then that it is surjective. Let x and y be distinct elements of A∪B. If x and y are both in A, then h(x) = f(x) ≠ f(y) = h(y); similarly if x and y are both in B, h(x) = |A|+g(x) ≠ |A| + g(y) = h(y). If x is in A and y in B, then h(x) = f(x) < |A|, and h(y) = g(y) + |A| ≥ |A|; it follows that h(x) ≠ h(y). The remaining case is symmetric. To show h is surjective, let m∈(|A|+|B|). If m < |A|, there exists some x∈A such that h(x) = f(x) = m. Otherwise, we have |A| ≤ m < |A|+|B|, so 0 ≤ m - |A| < |B|, and there exists some y∈B such that g(y) = m-|A|. But then h(y) = g(y)+|A| = m-|A|+|A| = m.

Generalizations: If A₁, A₂, A₃ ... A_k are pairwise disjoint (i.e. A_i ∩ A_j = Ø for all i ≠j), then

The proof is by induction on k.

50.3.1. Examples

• As I was going to Saint Ives, I met a man with 7 wives, 28 children, 56 grandchildren, and 122 great-grandchildren. Assuming these sets do not overlap, how many people did I meet? Answer: 1+7+28+56+122=214.

50.3.2. For infinite sets

The sum rule works for infinite sets, too; technically, the sum rule is used to define |A|+|B| as |A∪B| when A and B are disjoint. This makes cardinal arithmetic a bit wonky: if at least one of A and B is infinite, then |A| + |B| = max(|A|,|B|), since we can space out the elements of the larger of A and B and shoehorn the other into the gaps.

50.3.3. The Pigeonhole Principle

A consequence of the sum rule is that if A and B are both finite and |A| > |B|, you can't have an injection from A to B. The proof is by contraposition. Suppose f:A→B is an injection. Write A as the union of f^-1(x) for each x∈B, where f^-1(x) is the set of y in A that map to x. Because each f^-1(x) is disjoint, the sum rule applies; but because f is an injection there is at most one element in each f^-1(x). It follows that . (Question: Why doesn't this work for infinite sets?)

The Pigeonhole Principle generalizes in an obvious way to functions with larger domains; if f:A→B, then there is some x in B such that |f^-1(x)| ≥ |A|/|B|.

50.4. Inclusion-exclusion (with two sets)

What if A and B are not disjoint, i.e., if A∩B is not Ø? In this case adding |A| to |B| will count any element that appears in both sets twice. We can get the size of |A∪B| by subtracting off the overcount, obtaining this formula, which works for all A and B:

• |A∪B| = |A| + |B| - |A∩B|

To prove that the formula works, we use the sum rule. Observe that A = (A∩B) ∪ (B-A) and that the union in this case is disjoint (recall that A-B is the set of all elements that are in A but not in B). A similar decomposition works for B, so we have

• |A| + |B| = |A∩B| + |B-A| + |B∩A| + |A-B| = |A∪B| + |A∩B|.

Here we are again using the sum rule: A∪B is the disjoint union of A-B, B-A, and A∩B. Subtracting the |A∩B| term from both sides gives the formula we originally wanted.

This is a special case of the inclusion-exclusion formula, which can be used to compute the size of the union of many sets using the size of pairwise, triple-wise, etc. intersections of the sets.

50.4.1. For infinite sets

Subtraction doesn't work very well for infinite quantities (while ℵ₀+ℵ₀=ℵ₀, that doesn't mean ℵ₀=0). So the closest we can get to the inclusion-exclusion formula is that |A| + |B| = |A∪B| + |A∩B|. If at least one of A or B is infinite, then |A∪B| is also infinite, and since |A∩B| ≤ |A∪B| we have |A∪B| + |A∩B| = |A∪B| by the usual but bizarre rules of cardinal arithmetic. So for infinite sets we have the rather odd result that |A∪B| = |A| + |B| = max(|A|,|B|) whether the sets overlap or not.

50.4.2. Combinatorial proof

We can prove |A| + |B| = |A∪B| + |A∩B| combinatorially, by turning both sides of the equation into disjoint unions (so the sum rule works) and then providing an explicit bijection between the resulting sets. The trick is that we can always force a union to be disjoint by tagging the elements with extra information; so on the left-hand side we construct L = {1}×A ∪ {2}×B, and on the right-hand side we construct R = {1}×(A∪B) ∪ {2}×(A∩B). It is easy to see that both unions are disjoint, because we are always taking the union of a set of ordered pairs that start with 1 with a set of ordered pairs that start with 2, and no ordered pair can start with both tags; it follows that |L| = |A| + |B| and |R| = |A∪B| + |A∩B|. Now define the function f:L→R by the rule

• f((1,x)) = (1,x).
• f((2,x)) = (2,x) if x∈B∩A
• f((2,x)) = (1,x) if x∈B\A.

Observe that f is surjective, because for any (1,x) in {1}×(A∪B), either x is in A and (1,x) = f((1,x)) where (1,x) ∈ L, or x is in B\A and (1,x) = f((2,x)) where (2,x) ∈ L. It is also true that f is injective; the only way for it not to be is if f((1,x)) = f((2,x)) = (1,x) for some x. Suppose this occurs. Then x ∈ A (because of the 1 tag) and x ∈ B\A (because (2,x) is only mapped to (1,x) if x∈B\A). But x can't be in both A and B\A, so we get a contradiction.

50.5. Product rule

The product rule says that for any sets A and B

• |A×B| = |A|·|B|.

Recall that A×B is the Cartesian product of A and B, the set of all ordered pairs whose first element comes from A and whose second comes from B.

Proof (for finite sets): Let f:A→|A| and g:B→|B| be bijections. Construct a new function h:|A×B|→(|A|·|B|) by the rule h(<a,b>) = a·|B| + b. Showing that h is a bijection is left as an exercise to the reader (hint: use the DivisionAlgorithm).

The general form is

where the product on the left is a Cartesian product and the product on the right is an ordinary integer product.

50.5.1. Examples

• As I was going to Saint Ives, I met a man with seven sacks, and every sack had seven cats. How many cats total? Answer: Label the sacks 0,1,2,...,6, and label the cats in each sack 0,1,2,...,6. Then each cat can be specified uniquely by giving a pair <sack number, cat number>, giving a bijection between the set of cats and the set 7×7. Since the |7×7|=7·7=49, we have 49 cats.

• Dr Frankenstein's trusty assistant Igor has brought him 6 torsos, 4 brains, 8 pairs of matching arms, and 4 pairs of legs. How many different monsters can Dr Frankenstein build? Answer: there is a one-to-one correspondence between possible monsters and 4-tuples of the form <torso, brain, pair of arms, pair of legs>; the set of such 4-tuples has 6·4·8·4=728 members.

• How many different ways can you order n items? Call this quantity n! (i.e., n factorial). With 0 or 1 items, there is only one way; so we have 0!=1!=1. For n > 1, there are n choices for the first item, leaving n-1 items to be ordered. From the product rule we thus have n! = n·(n-1)!, which we could also expand out as

As a generalization of the previous example, we can count the number of ways P(n,k) we can pick an ordered subset of k of n items without replacement, also known as picking a k-permutation. There are n ways to pick the first item, n-1 to pick the second, and so forth, giving a total of

such k-permutations by the product rule.

Among combinatorialists, the notation (n)_k (pronounced "n lower-factorial k") is more common than P(n,k) for n·(n-1)·(n-2)·...·(n-k+1). As an extreme case we have (n)_n = n·(n-1)·(n-2)·...·(n-n+1) = n·(n-1)·(n-2)·...·1 = n!.

50.5.2. For infinite sets

The product rule also works for infinite sets, becasue we again use it as a definition: for any A and B, |A|⋅|B| is defined to be |A×B|. One oddity for infinite sets is that this definition gives |A|⋅|B| = |A|+|B| = max(|A|,|B|), because if at least one of A and B is infinite, it is possible to construct a bijection between A×B and the larger of A and B. (Infinite sets are strange.)

50.6. Exponent rule

Given sets A and B, let A^B be the set of functions f:B→A. Then |A^B| = |A|^|B|.

If |B| is finite, this is just a |B|-fold application of the product rule: we can write any function f:B→A as a sequence of length |B| that gives the value in A for each input in B. Since each element of the sequence contributes |A| possible choices, we get |A|^|B| choices total.

For infinite sets, the exponent rule is a definition of |A|^|B|. The behavior of exponentiation for infinite cardinals is very strange indeed; see here for some properties of cardinal exponentiation if you are really interested.

To give a flavor of how exponentiation works for arbitrary sets, here's a combinatorial proof of the usual arithmetic fact that x^ax^b = x^a+b, for any cardinal numbers x, a, and b. Let x = |X| and let a = |A| and b = |B| where A and B are disjoint (we can always use the tagging trick that we used for inclusion-exclusion to make A and B be disjoint). Then x^ax^b = |X^A×X^B| and x^a+b = |X^A∪B|. We will now construct an explicit bijection f:X^A∪B→X^A×X^B. The input to f is a function g:A∪B→X; the output is a pair of functions (g_A:A→X,g_B:B→X). We define g_A by g_A(x) = g(x) for all x in A (this makes g_A the restriction of g to A, usually written as g|A or g⇂A); similarly g_B = g|B. This is easily seen to be a bijection; if g = h, then f(g) = (g|A,g|B) = f(h) = (h|A,h|B), and if g≠h there is some x for which g(x)≠h(x), implying g|A≠h|A (if x is in A) or g|B≠h|B (if x is in B).

50.7. Counting the same thing in two different ways

An old farm joke:

• Q: How do you count a herd of cattle? A: Count the legs and divide by four.

Sometimes we can compute the size of a set S by using it (as an unknown variable) to compute the size of another set T (as a function of |S|), and then using some other way to count T to find its size, finally solving for |S|. This is known as counting two ways and is surprisingly useful when it works. We will assume that all the sets we are dealing with are finite, so we can expect things like subtraction and division to work properly.

Example: Let S be an n-element set, and consider the set S_k = { A⊆S | |A| = k }. What is |S_k|? Answer: First we'll count the number m of sequences of k elements of S with no repetitions. We can get such a sequence in two ways:

1. By picking a size-k subset A and then choosing one of k! ways to order the elements. This gives m = |S_k|·k!.

2. By choosing the first element in one of n ways, the second in one of n-1, the third in one of n-2 ways, and so on until the k-th element, which can be chosen in one of n-k+1 ways. This gives m = (n)_k = n·(n-1)·(n-2)·...(n-k+1), which can be written as n!/(n-k)!. (Here we are using the factors in (n-k)! to cancel out the factors in n! that we don't want.)

So we have m = |S_k|·k! = n!/(n-k)!, from which we get

This quantity turns out to be so useful that it has a special notation:

where the left-hand side is known as a binomial coefficient and is pronounced "n choose k." We discuss BinomialCoefficients at length on their own page. The secret of why it's called a binomial coefficient will be revealed when we talk about GeneratingFunctions.

Example: Here's a generalization of binomial coefficients: let the multinomial coefficient

be the number of different ways to distribute n items among k bins where the i-th bin gets exactly n_i of the items and we don't care what order the items appear in each bin. (Obviously this only makes sense if n₁+n₂+...+n_k=n.) Can we find a simple formula for the multinomial coefficient?

Here are two ways to count the number of permutations of the n-element set:

1. Pick the first element, then the second, etc. to get n! permuations.
2. Generate a permutation in three steps:

   1. Pick a partition of the n elements into groups of size n₁, n₂, ... n_k.

   2. Order the elements of each group.
   3. Paste the groups together into a single ordered list.

There are

ways to pick the partition and

ways to order the elements of all the groups, so we have

which we can solve to get

This also gives another way to derive the formula for a binomial coefficient, since

51. Applying the rules

If you're given some strange set to count, look at the structure of its description:

• If it's given by a rule of the form x is in S if either P(x) or Q(x) is true, use the sum rule (if P and Q are mutually exclusive) or inclusion-exclusion. This includes sets given by recursive definitions, e.g. x is a tree of depth at most k if it is either (a) a single leaf node (provided k > 0) or (b) a root node with two subtrees of depth at most k-1. The two classes are disjoint so we have T(k) = 1 + T(k-1)² with T(0) = 0.³

• For objects made out of many small components or resulting from many small decisions, try to reduce the description of the object to something previously known, e.g. (a) a word of length k of letters from an alphabet of size n allowing repetition (there are n^k of them, by the product rule); (b) a word of length k not allowing repetition (there are (n)_k of them—or n! if n = k); (c) a subset of k distinct things from a set of size n, where we don't care about the order (there are of them); any subset of a set of n things (there are 2ⁿ of them—this is a special case of (a), where the alphabet encodes non-membership as 0 and membership as 1, and the position in the word specifies the element). Some examples:

  • The number of games of Tic-Tac-Toe assuming both players keep playing until the board is filled is obtained by observing that each such game can be specified by listing which of the 9 squares are filled in order, giving 9! = 362,880 distinct games. Note that we don't have to worry about which of the 9 moves are made by X and which by O, since the rules of the game enforce it. (If we only consider games that end when one player wins, this doesn't work: probably the easiest way to count such games is to send a computer off to generate all of them. This horrible program says there are 255168 possible games and 958 distinct final positions.)

  • The number of completely-filled-in Tic-Tac-Toe boards can be obtained by observing that any such board has 5 X's and 4 O's. So there are = 126 such positions. (Question: Why would this be smaller than the actual number of final positions?)

Sometimes reducing to a previous case requires creativity. For example, suppose you win n identical cars on a game show and want to divide them among your k greedy relatives. Assuming that you don't care about fairness, how many ways are there to do this?

• If it's ok if some people don't get a car at all, then you can imagine putting n cars and k-1 dividers in a line, where relative 1 gets all the cars up to the first divider, relative 2 gets all the cars between the first and second dividers, and so forth up to relative k who gets all the cars after the (k-1)th divider. Assume that each car—and each divider—takes one parking space. Then you have n+k-1 parking spaces with k-1 dividers in them (and cars in the rest). There are exactly ways to do this.

• Alternatively, suppose each relative demands at least 1 car. Then you can just hand out one car to each relative to start with, leaving n-k cars to divide as in the previous case. There are ways to do this.

Finding such correspondences is a central part of enumerative combinatorics, the branch of mathematics that deals with counting things.

52. An elaborate counting problem

Suppose you have the numbers { 1, 2, .., 2n }, and you want to count how many sequences of k of these numbers you can have that are (a) increasing (a[i] < a[i+1] for all i), (b) decreasing (a[i] ≥ a[i+1] for all i), or (c) made up only of even numbers.

This is the union of three sets A, B, and C, corresponding to the three cases. The first step is to count each set individually; then we can start thinking about applying inclusion-exclusion to get the size of the union.

For A, any increasing sequence can be specified by choosing its elements (the order is determined by the assumption it is increasing). So we have .

For B, by symmetry we have .

For C, we are just looking at n^k possible sequences, since there are n even numbers we can put in each position.

Inclusion-exclusion says that |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∪B∪C|. It's not hard to see that A∩B = ∅ when k is at least 2⁴, so we can reduce this to |A| + |B| + |C| - |A∩C| - |B∩C|. To count A∩C, observe that we are now looking at increasing sequences chosen from the n possible even numbers; so there are exactly of them, and similarly for B∩C. Summing up gives a total of

sequences satisfying at least one of the criteria.

Note that we had to assume k = 2 to get A∩B=∅, so this formula might require some adjustment for k<2. In fact we can observe immediately that the unique empty sequence for k=1 fits in all of A, B, and C, so in this case we get 1 winning sequence (which happens to be equal to the value in the formula, because here A∩B=∅ for other reasons), and for k=1 we get 2n winning sequences (which is less than the value 3n given by the formula).

To test that the formula works for at least some larger values, let n=3 and k=2. Then the formula predicts total sequences.⁵ And here they are (generated by seqs.py run as python seqs.py 6 2):

[1, 2]
[1, 3]
[1, 4]
[1, 5]
[1, 6]
[2, 1]
[2, 2]
[2, 3]
[2, 4]
[2, 5]
[2, 6]
[3, 1]
[3, 2]
[3, 4]
[3, 5]
[3, 6]
[4, 1]
[4, 2]
[4, 3]
[4, 4]
[4, 5]
[4, 6]
[5, 1]
[5, 2]
[5, 3]
[5, 4]
[5, 6]
[6, 1]
[6, 2]
[6, 3]
[6, 4]
[6, 5]
[6, 6]

53. Further reading

RosenBook does basic counting in chapter 5 and more advanced counting (including SolvingRecurrences and using GeneratingFunctions) in chapter 7. BiggsBook chapters 6 and 10 give a basic introduction to counting, with more esoteric topics in chapters 11 and 12. ConcreteMathematics has quite a bit on counting various things.

CategoryMathNotes

PDF version

The binomial coefficient "n choose k", written

counts the number of k-element subsets of an n-element set.

The name arises from the binomial theorem, which says that

For integer n, we can limit ourselves to letting k range from 0 to n. The most general version of the theorem lets k range over all of ℕ, and relies on the binomial coefficient to zero out the extra terms. It holds for any integer n ≥ 0 or (with a suitable definition of binomial coefficients) for any n if |x/y| < 1 (which guarantees that the sum converges).

The connection to counting subsets is straightforward: expanding (x+y)ⁿ using the distributive law gives 2ⁿ terms, each of which is a unique sequence of n x's and y's. If we think of the x's in each term as labeling a subset of the n positions in the term, the terms that get added together to get x^ky^n-k correspond one-to-one to subsets of size k. So there are

such terms, accounting for the coefficient on the right-hand side.

55. Recursive definition

If we don't like computing factorials, we can also compute binomial coefficients recursively.

Base cases:

• If k = 0, then there is exactly one zero-element set of our n-element set—it's the empty set—and we have

• If k > n, then there are no k-element subsets, and we have

Recursive step: We'll use Pascal's identity, which says that

The proof of this identity is combinatorial, which means that we will construct an explicit bijection between a set counted by the left-hand side and a set counted by the right-hand side. This is often one of the best ways of understanding simple binomial coefficient identities.

On the left-hand side, we are counting all the k-element subsets of an n-element set S. On the right hand side, we are counting two different collections of sets: the (k-1)-element and k-element subsets of an (n-1)-element set. The trick is to recognize that we get an (n-1)-element set S' from our original set by removing one of the elements x. When we do this, we affect the subsets in one of two ways:

1. If the subset doesn't contain x, it doesn't change. So there is a one-to-one correspondence (the identity function) between k-subsets of S that don't contain x and k-subsets of S'. This bijection accounts for the first term on the right-hand side.
2. If the subset does contain x, then we get a (k-1)-element subset of S' when we remove it. Since we can go back the other way by reinserting x, we get a bijection between k-subsets of S that contain x and (k-1)-subsets of S'. This bijection accounts for the second term on the right-hand side.

Adding the two cases together (using the sum rule), we conclude that the identity holds.

Using the base case and Pascal's identity, we can construct Pascal's triangle, a table of values of binomial coefficients:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...

Each row corresponds to increasing values of n, and each column to increasing values of k, with

in the upper left-hand corner. To compute each entry, we add together the entry directly above it and the entry diagonally to the left.

55.1. Pascal's identity: algebraic proof

Using the binomial theorem plus a little bit of algebra, we can prove Pascal's identity without using a combinatorial argument (this is not necessarily an improvement). The additional fact we need is that if we have two equal series

then a_i = b_i for all i.

Here's the proof:

and now we equate matching coefficients to get

as advertised.

56. Vandermonde's identity

Vandermonde's identity says that, provided r does not exceed m or n,

56.1. Combinatorial proof

To pick r elements of an m+n element set, we have to pick some of them from the first m elements and some from the second n elements. Suppose we choose k elements from the last n; there are

different ways to do this, and

different ways to choose the remaining r-k from the first m. This gives (by the product rule)

ways to choose r elements from the whole set if we limit ourselves to choosing exactly k from the last n. The identity follow by summing over all possible values of k.

56.2. Algebraic proof

Here we use the fact that, for any sequences of coefficients {a_i} and {b_i},

So now consider

and now equate terms with matching exponents.

Is this more enlightening than the combinatorial version? It depends on what kind of enlightnment you are looking for. In this case the combinatorial and algebraic arguments are counting essentially the same things in the same way, so it's not clear what if any advantage either has over the other. But in many cases it's easier to construct an algebraic argument than a combinatorial one, in the same way that it's easier to do arithmetic using standard grade-school algorithms than by constructing explicit bijections. On the other hand, a combinatorial argument may let you carry other things you know about some structure besides just its size across the bijection, giving you more insight into the things you are counting. The best course is probably to have both techniques in your toolbox.

57. Sums of binomial coefficients

What is the sum of all binomial coefficients for a given n? We can show

combinatorially, by observing that adding up all subsets of an n-element set of all sizes is the same as counting all subsets. Alternatively, apply the binomial theorem to (1+1)ⁿ.

Here's another sum, with alternating sign. This is useful if you want to know how the even-k binomial coefficients compare to the odd-k binomial coefficients.

Proof: (1-1)ⁿ = 0ⁿ = 0 when n is nonzero. (When n is zero, the 0ⁿ part still works, since 0⁰ = 1 = (0 choose 0)(-1)⁰.)

By now it should be obvious that

It's not hard to construct more examples of this phenomenon.

58. Application: the inclusion-exclusion formula

We've previously seen that |A∪B| = |A| + |B| - |A∩B|. The generalization of this fact from two to many sets is called the inclusion-exclusion formula and says

This rather horrible expression means that to count the elements in the union of n sets A₁ through A_n, we start by adding up all the individual sets |A₁| + |A₂| + ... |A_n|, then subtract off the overcount from elements that appear in two sets -|A₁ ∩ A₂| - |A₁ ∩ A₃| - ..., then add back the resulting undercount from elements that appear in three sets, and so on.

Why does this work? Consider a single element x that appears in k of the sets. We'll count it as +1 in (k choose 1) individual sets, as -1 in (k choose 2) pairs, +1 in (k choose 3) triples, and so on, adding up to

59. Negative binomial coefficients

Though it doesn't make sense to talk about the number of k-subsets of a (-1)-element set, the binomial coefficient (n choose k) has a meaningful value for negative n, which works in the binomial theorem. We'll use the lower-factorial version of the definition:

Note we still demand that k∈ℕ; we are only allowed to do funny things with the upper index n.

So for example:

This means, for example, that

In computing this sum, we had to be careful which of 1 and -z got the n exponent and which got -1-n. If we do it the other way, we get

This turns out to actually be correct: applying the geometric series formula turns the last line into

but it's a lot less useful.

What happens for a larger upper index? One way to think about (-n)_k is that we are really computing (n+k-1)_k and then negating all the factors (which corresponds to multiplying the whole expression by (-1)^k. So this gives us the identity

So, for example,

These facts are useful when we look at GeneratingFunctions.

60. Fractional binomial coefficients

Yes, we can do fractional binomial coefficients, too. Exercise: Find the value of

61. Further reading

ConcreteMathematics §5.1–5.3 is an excellent source for information about all sorts of facts about binomial coefficients.

CategoryMathNotes

PDF version

63. Basics

The short version: A generating function represents objects of weight n with zⁿ, and adds all the objects you have up to get a sum a₀z⁰ + a₁z¹ + a₂z² + ..., where each a_n counts the number of different objects of weight n. If you are very lucky (or constructed your set of objects by combining simpler sets of objects in certain straightforward ways) there will be some compact expression that is expands to this horrible sum but is easier to right down. Such compact expressions are called generating functions, and manipulating them algebraically gives an alternative to actually knowing HowToCount.

63.1. A simple example

We are given some initial prefixes for words: qu, s, and t; some vowels to put in the middle: a, i, and oi; and some suffixes: d, ff, and ck, and we want to calculate the number of words we can build of each length.

One way is to generate all 27 words⁶ and sort them by length:

sad sid tad tid
quad quid sack saff sick siff soid tack taff tick tiff toid
quack quaff quick quiff quoid soick soiff toick toiff
quoick quoiff

This gives us 4 length-3 words, 12 length-4 words, 9 length-5 words, and 2 length-6 words. This is probably best done using a computer, and becomes expensive if we start looking at much larger lists.

An alternative is to solve the problem by judicious use of algebra. Pretend that each of our letters is actually a variable, and that when we concatenate qu, oi, and ck to make quoick, we are really multiplying the variables using our usual notation. Then we can express all 27 words as the product (qu+s+t)(a+i+oi)(d+ff+ck). But we don't care about the exact set of words, we just want to know how many we get of each length.

So now we do the magic trick: we replace every variable we've got with a single variable z. For example, this turns quoick into zzzzzz = z⁶, so we can still find the length of a word by reading off the exponent on z. But we can also do this before we multiply everything out, getting

We can now read off the number of words of each length directly off the coefficients of this polynomial.

63.2. Why this works

In general, what we do is replace any object of weight 1 with z. If we have an object with weight n, we think of it as n weight-1 objects stuck together, i.e., zⁿ. Disjoint unions are done using addition as in simple counting: z+z² represents the choice between a weight-1 object and a weight-2 object (which may have been built out of 2 weight-1 objects), while 12z⁴ represents a choice between 12 different weight-4 objects. The trick is that when we multiply two expressions like this, whenever two values z^k and z^l collide, the exponents add to give a new value z^k+l representing a new object with total weight k+l, and if we have something more complex like (nz^k)(mz^l), then the coefficient multiply to give (nm)z^k+l different weight (k+l) objects.

For example, suppose we want to count the number of robots we can build given 5 choices of heads, each of weight 2, and 6 choices of bodies, each of weight 5. We represent the heads by 5z² and the bodies by 6z⁵. When we multiply these expressions together, the coefficients multiply (which we want, by the product rule) and the exponents add: we get 5z²⋅6z⁵ = 30z⁷ or 30 robots of weight 7 each.

The real power comes in when we consider objects of different weights. If we add to our 5 weight-2 robot heads two extra-fancy heads of weight 3, and compensate on the body side with three new lightweight weight-4 bodies, our new expression is (5z²+2z³)(3z⁴+6z⁵) = 15z⁶+36z⁷+12z⁸, giving a possible 15 weight-6 robots, 36 weight-7 robots, and 12 weight-8 robots. The rules for multiplying polynomials automatically tally up all the different cases for us.

This trick even works for infinitely-long polynomials that represent infinite series (such "polynomials" are called formal power series). Even though there might be infinitely many ways to pick three natural numbers, there are only finitely many ways to pick three natural numbers whose sum is 37. By computing an appropriate formal power series and extracting the coefficient from the z³⁷ term, we can figure out exactly how many ways there are. This works best, of course, when we don't have to haul around an entire infinite series, but can instead represent it by some more compact function whose expansion gives the desired series. Such a function is called a generating function, and manipulating generating functions can be a powerful alternative to creativity in making combinatorial arguments.

63.3. Formal definition

Given a sequence a₀,a₁,a₂,..., its generating function F(z) is given by the sum

A sum in this form is called a formal power series. It is "formal" in the sense that we don't necessarily plan to actually compute the sum, and are instead using the string of zⁱ terms as a long rack to store coefficients on.

In some cases, the sum has a more compact representation. For example, we have

so 1/(1-z) is the generating function for the sequence 1,1,1,.... This may let us manipulate this sequence conveniently by manipulating the generating function.

Here's a simple case. If F(z) generates some sequence a_i, what does sequence b_i does F(2z) generate? The i-th term in the expansion of F(2z) will be a_i(2z)ⁱ = a_i 2ⁱ zⁱ, so we have b_i = 2ⁱ a_i. This means that the sequence 1,2,4,8,16,... has generating function 1/(1-2z). In general, if F(z) represents a_i, then F(cz) represents cⁱa_i.

What else can we do to F? One useful operation is to take its derivative with respect to z. We then have

This almost gets us the representation for the series i a_i, but the exponents on the z's are off by one. But that's easily fixed:

So the sequence 0,1,2,3,4,... has generating function

and the sequence of squares 0,1,4,9,16,... has generating function

As you can see, some generating functions are prettier than others.

(We can also use integration to divide each term by i, but the details are messier.)

Another way to get the sequence 0,1,2,3,4,... is to observe that it satisfies the recurrence:

• a₀ = 0

• a_n+1 = a_n + 1 (∀n∈ℕ)

A standard trick in this case is to multiply each of the ∀i bits by zⁿ, sum over all n, and see what happens. This gives ∑ a_n+1zⁿ = ∑ a_nzⁿ + ∑ zⁿ = ∑ a_nzⁿ + 1/(1-z). The first term on the right-hand side is the generating function for a_n, which we can call F(z) so we don't have to keep writing it out. The second term is just the generating function for 1,1,1,1,1,... . But what about the left-hand side? This is almost the same as F(z), except the coefficients don't match up with the exponents. We can fix this by dividing F(z) by z, after carefully subtracting off the a₀ term:

So this gives the equation (F(z) - a₀)/z = F(z) + 1/(1-z). Since a₀ = 0, we can rewrite this as F(z)/z = F(z) + 1/(1-z). A little bit of algebra turns this into F(z) - zF(z) = z/(1-z) or F(z) = z/(1-z)².

Yet another way to get this sequence is construct a collection of objects with a simple structure such that there are exactly n objects with weight n. One way to do this is to consider strings of the form a⁺b^* where we have at least one a followed by zero or more b's. This gives n strings of length n, because we get one string for each of 1..n a's we can put in (an example would be abb, aab, and aaa for n=3). We can compute the generating function for this set because to generate each string we must pick in order:

• One initial a. Generating function = z.
• Zero or more a's. Generating function = 1/(1-z).
• Zero or more b's. Generating function = 1/(1-z).

  Taking the product of these gives z/(1-z)², as before.

This trick is useful in general; if you are given a generating function F(z) for a_n, but want a generating function for b_n = ∑_k≤n a_k, allow yourself to pad each weight-k object out to weight n in exactly one way using n-k junk objects, i.e. multiply F(z) by 1/(1-z).

64. Some standard generating functions

Here is a table of some of the most useful generating functions.

Of these, the first is the most useful to remember (it's also handy for remembering how to sum geometric series). All of these equations can be proven using the binomial theorem.

65. More operations on formal power series and generating functions

Let F(z) = ∑_i a_izⁱ and G(z) = ∑_i b_izⁱ. Then their sum F(z)+G(z) = ∑_i (a_i+b_i)zⁱ is the generating function for the sequence (a_i+b_i). What is their product F(z)G(z)?

To compute the i-th term of F(z)G(z), we have to sum over all pairs of terms, one from F and one from G, that produce a zⁱ factor. Such pairs of terms are precisely those that have exponents that sum to i. So we have

As we've seen, this equation has a natural combinatorial interpretation. If we interpret the coefficient a_i on the i-th term of F(z) as counting the number of "a-things" of weight i, and the coefficient b_i as the number of "b-things" of weight i, then the i-th coefficient of F(z)G(z) counts the number of ways to make a combined thing of total weight i by gluing together an a-thing and a b-thing.

As a special case, if F(z)=G(z), then the i-th coefficient of F(z)G(z) = F²(z) counts how many ways to make a thing of total weight i using two "a-things", and Fⁿ(z) counts how many ways (for each i) to make a thing of total weight i using n "a-things". This gives us an easy combinatorial proof of a special case of the binomial theorem:

Think of the left-hand side as the generating function F(x) = 1+x raised to the n-th power. F by itself says that you have a choice between one weight-0 object or one weight-1 object. On the right-hand side the i-th coefficient counts how many ways you can put together a total of i weight-1 objects given n to choose from—so it's n choose i.

66. Counting with generating functions

The product formula above suggests that generating functions can be used to count combinatorial objects that are built up out of other objects, where our goal is to count the number of objects of each possible non-negative integer "weight" (we put "weight" in scare quotes because we can make the "weight" be any property of the object we like, as long as it's a non-negative integer—a typical choice might be the size of a set, as in the binomial theorem example above). There are five basic operations involved in this process; we've seen two of them already, but will restate them here with the others.

Throughout this section, we assume that F(z) is the generating function counting objects in some set A and G(z) the generating function counting objects in some set B.

66.1. Disjoint union

Suppose C = A∪B and A and B are disjoint. Then the generating function for objects in C is F(z)+G(z).

Example: Suppose that A is the set of all strings of zero or more letters x, where the weight of a string is just its length. Then F(z) = 1/(1-z), since there is exactly one string of each length and the coefficient a_i on each zⁱ is always 1. Suppose that B is the set of all strings of zero or more letters y and/or z, so that G(z) = 1/(1-2z) (since there are now 2ⁱ choices of length-i strings). The set C of strings that are either (a) all x's or (b) made up of y's, z's, or both, has generating function F(z)+G(z) = 1/(1-z) + 1/(1-2z).

66.2. Cartesian product

Now let C = A×B, and let the weight of a pair (a,b)∈C be the sum of the weights of a and b. Then the generating function for objects in C is F(z)G(z).

Example: Let A be all-x strings and B be all y or z strings, as in the previous example. Let C be the set of all strings that consist of zero or more x's followed by zero or more y's and/or z's. Then the generating function for C is F(z)G(z) = 1/((1-z)(1-2z)).

66.3. Repetition

Now let C consists of all finite sequences of objects in A, with the weight of each sequence equal to the sum of the weights of its elements (0 for an empty sequence). Let H(z) be the generating function for C. From the preceding rules we have

• H = 1 + F + F² + F³ + ... = 1/(1-F).

This works best when H(0) = 0; otherwise we get infinitely many weight-0 sequences. It's also worth noting that this is just a special case of substitution (see below), where our "outer" generating function is 1/(1-z).

66.3.1. Example: (0|11)*

Let A = { 0, 11 }, and let C be the set of all sequences of zeroes and ones where ones occur only in even-length runs. Then the generating function for A is z+z² and the generating function for C is 1/(1-z-z²). We can extract exact coefficients from this generating function using the techniques below.

66.3.2. Example: sequences of positive integers

Suppose we want to know how many different ways there are to generate a particular integer as a sum of positive integers. For example, we can express 4 as 4, 3+1, 2+2, 2+1+1, 1+1+1+1, 1+1+2, 1+2+1, or 1+3, giving 8 different ways.

We can solve this problem using the repetition rule. Let F = z/(1-z) generate all the positive integers. Then

We can get exact coefficients by observing that

This means that there is 1 way to express 0 (the empty sum), and 2^n-1 ways to express any larger value n (e.g. 2^4-1 = 8 ways to express 4).

Once we know what the right answer is, it's not terribly hard to come up with a combinatorial explanation. The quantity 2^n-1 counts the number of subsets of an (n-1)-element set. So imagine that we have n-1 places and we mark some subset of them, plus add an extra mark at the end; this might give us a pattern like XX-X. Now for each sequence of places ending with a mark we replace it with the number of places (e.g. XX-X = 1,1,2, X--X-X---X = 1,3,2,4). Then the sum of the numbers we get is equal to n, because it's just counting the total length of the sequence by dividing it up at the marks and the adding the pieces back together. The value 0 doesn't fit this pattern (we can't put in the extra mark without getting a sequence of length 1), so we have 0 as a special case again.

If we are very clever, we might come up with this combinatorial explanation from the beginning. But the generating function approach saves us from having to be clever.

66.4. Pointing

This operation is a little tricky to describe. Suppose that we can think of each weight-k object in A as consisting of k items, and that we want to count not only how many weight-k objects there are, but how many ways we can produce a weight-k object where one of its k items has a special mark on it. Since there are k different items to choose for each weight-k object, we are effectively multiplying the count of weight-k objects by k. In generating function terms, we have

• H(z) = z d/dz F(z).

Repeating this operation allows us to mark more items (with some items possibly getting more than one mark). If we want to mark n distinct items in each object (with distinguishable marks), we can compute

• H(z) = zⁿ dⁿ/dzⁿ F(z),

where the repeated derivative turns each term a_i zⁱ into a_ii(i-1)(i-2)...(i-n+1) z^i-n and the zⁿ factor fixes up the exponents. To make the marks indistinguishable (i.e., we don't care what order the values are marked in), divide by n! to turn the extra factor into (i choose n).

(If you are not sure how to take a derivative, look at HowToDifferentiate.)

Example: Count the number of finite sequences of zeroes and ones where exactly two digits are underlined. The generating function for { 0, 1 } is 2z, so the generating function for sequences of zeros and ones is F = 1/(1-2z) by the repetition rule. To mark two digits with indistinguishable marks, we need to compute

66.5. Substitution

Suppose that the way to make a C-thing is to take a weight-k A-thing and attach to each its k items a B-thing, where the weight of the new C-thing is the sum of the weights of the B-things. Then the generating function for C is the composition F(G(z)).

Why this works: suppose we just want to compute the number of C-things of each weight that are made from some single specific weight-k A-thing. Then the generating function for this quantity is just (G(z))^k. If we expand our horizons to include all a_k weight-k A-things, we have to multiply by a_k to get a_k (G(z))^k. If we further expand our horizons to include A-things of all different weights, we have to sum over all k:

But this is just what we get if we start with F(z) and substitute G(z) for each occurrence of z, i.e. if we compute F(G(z)).

66.5.1. Example: bit-strings with primes

Suppose we let A be all sequences of zeroes and ones, with generating function F(z) = 1/(1-2z). Now suppose we can attach a single or double prime to each 0 or 1, giving 0' or 0'' or 1' or 1'', and we want a generating function for the number of distinct primed bit-strings with n attached primes. The set { prime, prime-prime } has generating function G(z)=z+z², so the composite set has generating function F(z) = 1/(1-2(z+z²)) = 1/(1-2z-2z²).

66.5.2. Example: (0|11)* again

The previous example is a bit contrived. Here's one that's a little more practical, although it involves a brief digression into multivariate generating functions. A multivariate generating function F(x,y) generates a series ∑_ij a_ij xⁱy^j, where a_ij counts the number of things that have i x's and j y's. (There is also the obvious generalization to more than two variables). Consider the multivariate generating function for the set { 0, 1 }, where x counts zeroes and y counts ones: this is just x+y. The multivariate generating function for sequences of zeroes and ones is 1/(1-x-y) by the repetition rule. Now suppose that each 0 is left intact but each 1 is replaced by 11, and we want to count the total number of strings by length, using z as our series variable. So we substitute z for x and z² (since each one turns into a string of length 2) for y, giving 1/(1-z-z²). This gives another way to get the generating function for strings built by repeating 0 and 11.

67. Generating functions and recurrences

What makes generating functions particularly useful for algorithm analysis is that they directly solve recurrences of the form T(n) = a T(n-1) + b T(n-2) + f(n) (or similar recurrences with more T terms on the right-hand side), provided we have a generating function F(z) for f(n). The idea is that there exists some generating function G(z) that describes the entire sequence of values T(0),T(1),T(2),..., and we just need to solve for it by restating the recurrence as an equation about G. The left-hand side will just turn into G. For the right-hand side, we need to shift T(n-1) and T(n-2) to line up right, so that the right-hand side will correctly represent the sequence T(0),T(1),aT(0)+aT(1)+F(2), etc. It's not hard to see that the generating function for the sequence 0,T(0),T(1),T(2),... (corresponding to the T(n-1) term) is just zG(z), and similarly the sequence 0,0,T(1),T(2),T(3),... (corresponding to the T(n-2) term) is z²G(z). So we have (being very careful to subtract out extraneous terms at for i=0 and i=1):

• G = az(G - T(0)) + bz²G + (F - f(0) - zf(1)) + T(0) + zT(1),

and after expanding F we can in principle solve this for G as a function of z.

67.1. Example: A Fibonacci-like recurrence

Let's take a concrete example. The Fibonacci-like recurrence

• T(n) = T(n-1) + T(n-2), T(0) = 1, T(1) = 1,

becomes

• G = (zG - z) + z²G + 1 + z.

(here F = 0).

Solving for G gives

• G = 1/(1 - z - z²).

Unfortunately this is not something we recognize from our table, although it has shown up in a couple of examples. (Exercise: Why does the recurrence T(n) = T(n-1) + T(n-2) count the number of strings built from 0 and 11 of length n?) In the next section we show how to recover a closed-form expression for the coefficients of the resulting series.

68. Recovering coefficients from generating functions

There are basically three ways to recover coefficients from generating functions:

1. Recognize the generating function from a table of known generating functions, or as a simple combination of such known generating functions. This doesn't work very often but it is possible to get lucky.

2. To find the k-th coefficient of F(z), compute the k-th derivative d^k/dz^k F(z) and divide by k! to shift a_k to the z⁰ term. Then substitute 0 for z. For example, if F(z) = 1/(1-z) then a₀ = 1 (no differentiating), a₁ = 1/(1-0)² = 1, a₂ = 1/(1-0)³ = 1, etc. This usually only works if the derivatives have a particularly nice form or if you only care about the first couple of coefficients (it's particularly effective if you only want a₀).

3. If the generating function is of the form 1/Q(z), where Q is a polynomial with Q(0)≠0, then it is generally possible to expand the generating function out as a sum of terms of the form P_c/(1-z/c) where c is a root of Q (i.e. a value such that Q(c) = 0). Each denominator P_c will be a constant if c is not a repeated root; if c is a repeated root, then P_c can be a polynomial of degree up to one less than the multiplicity of c. We like these expanded solutions because we recognize 1/(1-z/c) = ∑_i c^-i zⁱ, and so we can read off the coefficients a_i generated by 1/Q(z) as an appropriately weighted some of c₁^-i, c₂^-i, etc., where the c_j range over the roots of Q.

Example: Take the generating function G = 1/(1-z-z²). We can simplify it by factoring the denominator: 1-z-z² = (1-az)(1-bz) where 1/a and 1/b are the solutions to the equation 1-z-z²=0; in this case a = (1+√5)/2, which is approximately 1.618 and b = (1-√5)/2, which is approximately -0.618. It happens to be the case that we can always expand 1/P(z) as A/(1-az) + B(1-bz) for some constants A and B whenever P is a degree 2 polynomial with constant coefficient 1 and distinct roots a and b, so

• G = A/(1-az) + B/(1-bz),

and here we can recognize the right-hand side as the sum of the generating functions for the sequences A⋅aⁱ and B⋅bⁱ. The A⋅aⁱ term dominates, so we have that T(n) = Theta(aⁿ), where a is approximately 1.618. We can also solve for A and B exactly to find an exact solution if desired.

A rule of thumb that applies to recurrences of the form T(n) = a₁T(n-1) + a₂T(n-2) + ... a_k T(n-k) + f(n) is that unless f is particularly large, the solution is usually exponential in 1/x, where x is the smallest root of the polynomial 1 - a₁z - a₂z² ... - a_k z^k. This can be used to get very quick estimates of the solutions to such recurrences (which can then be proved without fooling around with generating functions).

Exercise: What is the exact solution if T(n) = T(n-1) + T(n-2) + 1? Or if T(n) = T(n-1) + T(n-2) + n?

68.1. Partial fraction expansion and Heaviside's cover-up method

There is a nice trick for finding the numerators in a partial fraction expansion. Suppose we have

Multiply both sides by 1-az to get

Now plug in z = 1/a to get

We can immediately read off A. Similarly, multiplying by 1-bz and then setting 1-bz to zero gets B. The method is known as the "cover-up method" because multiplication by (1-az) can be simulated by covering up (1-az) in the denominator of the left-hand side and all the terms that don't have (1-az) in the denominator in the right hand side.

The cover-up method will work in general whenever there are no repeated roots, even if there are many of them; the idea is that setting 1-qz to zero knocks out all the terms on the right-hand side but one. With repeated roots we have to worry about getting numerators that aren't just a constant, so things get more complicated. We'll come back to this case below.

68.1.1. Example: A simple recurrence

Suppose f(0) = 0, f(1) = 1, and for n≥2, f(n) = f(n-1) + 2f(n-2). Multiplying these equations by zⁿ and summing over all n gives a generating function

With a bit of tweaking, we can get rid of the sums on the RHS by converting them into copies of F:

Now solve for F(z) to get , where we need to solve for A and B.

We can do this directly, or we can use the cover-up method. The cover-up method is easier. Setting z = -1 and covering up 1+z gives A = 1/(1-2(-1)) = 1/3. Setting z = 1/2 and covering up 1-2z gives B = 1/(1+z) = 1/(1+1/2) = 2/3. So we have

So we have f(0) = 0 and, for n≥1, . It's not hard to check that this gives the same answer as the recurrence.

68.1.2. Example: Coughing cows

Let's count the number of strings of each length of the form (M)*(O|U)*(G|H|K)* where (x|y) means we can use x or y and * means we can repeat the previous parenthesized expression 0 or more times (see Regular_expression).

We start with a sequence of 0 or more M's. The generating function for this part is our old friend 1/(1-z). For the second part, we have two choices for each letter, giving 1/(1-2z). For the third part, we have 1/(1-3z). Since each part can be chosen independently of the other two, the generating function for all three parts together is just the product:

Let's use the cover-up method to convert this to a sum of partial fractions. We have

So the exact number of length-n sequences is (1/2) - 4⋅2ⁿ + (9/2)⋅3ⁿ. We can check this for small n:

68.1.3. Example: A messy recurrence

Let's try to solve the recurrence T(n) = 4T(n-1) + 12T(n-2) + 1 with T(0) = 0 and T(1) = 1.

Let F = ∑ T(n)zⁿ.

Summing over all n gives

Solving for F then gives

We want to solve this using partial fractions, so we need to factor (1-4z-12z²) = (1+2z)(1-6z). This gives

From this we can immediately read off the value of T(n) for n≥2:

Let's check this against the solutions we get from the recurrence itself:

We'll try n=3, and get T(3) = (3/20)⋅216 + 8/12 - 1/15 = (3⋅3⋅216 + 40 - 4)/60 = (1944 + 40 - 4)/60 = 1980/60 = 33.

To be extra safe, let's try T(2) = (3/20)⋅36 - 4/12 - 1/15 = (3⋅3⋅36 - 20 - 4)/60 = (324 - 20 - 4)/60 = 300/60 = 5. This looks good too.

The moral of this exercise? Generating functions can solve ugly-looking recurrences exactly, but you have to be very very careful in doing the math.

68.2. Partial fraction expansion with repeated roots

Let a_n = 2a_n-1 + n, with some constant a₀. Find a closed-form formula for a_n.

As a test, let's figure out the first few terms of the sequence:

The a₀ terms look nice (they're 2ⁿa₀), but the 0, 1, 4, 11, 26 sequence doesn't look like anything familiar. So we'll find the formula the hard way.

First we convert the recurrence into an equation over generating functions and solve for the generating function F:

Observe that the right-hand term gives us exactly the 2ⁿa₀ terms we expected, since 1/(1-2z) generates the sequence 2ⁿ. But what about the left-hand term? Here we need to apply a partial-fraction expansion, which is simplified because we already know how to factor the denominator but is complicated because there is a repeated root.

We can now proceed in one of two ways: we can solve directly for the partial fraction expansion, or we can use an extended version of Heaviside's cover-up method that handles repeated roots using differentiation. We'll start with the direct method.

68.2.1. Solving for the PFE directly

Write

We expect B to be a constant and A to be of the form A₁z + A₀.

To find B, use the technique of multiplying by 1-2z and setting z=1/2:

so B = 1/(1-1/2)² = 1/(1/4) = 4.

We can't do this for A, but we can solve for it after substituting in B = 4:

So we have the expansion

from which we get

If we remember that 1/(1-z)² generates the sequence x_n = n+1 and 1/(1-2z) generates x_n = 2ⁿ, then we can quickly read off the solution (for large n):

which we can check by plugging in particular values of n and comparing it to the values we got by iterating the recurrence before.

The reason for the "large n" caveat is that z²/(1-z)² doesn't generate precisely the sequence x_n = n-1, since it takes on the values 0, 0, 1, 2, 3, 4, ... instead of -1, 0, 1, 2, 3, 4, ... . Similarly, the power series for z/(1-2z) does not have the coefficient 2^n-1 = 1/2 when n = 0. Miraculously, in this particular example the formula works for n = 0, even though it shouldn't: 2(n-1) is -2 instead of 0, but 4·2^n-1 is 2 instead of 0, and the two errors cancel each other out.

68.2.2. Solving for the PFE using the extended cover-up method

It is also possible to extend the cover-up method to handle repeated roots. Here we choose a slightly different form of the partial fraction expansion:

Here A, B, and C are all constants. We can get A and C by the cover-up method, where for A we multiply both sides by (1-z)² before setting z=1; this gives A = 1/(1-2) = -1 and C = 1/(1-½)² = 4. For B, if we multiply both sides by (1-z) we are left with A/(1-z) on the right-hand side and a (1-z) in the denominator on the left-hand side. Clearly setting z = 1 in this case will not help us.

The solution is to first multiply by (1-z)² as before but then take a derivative:

Now if we set z = 1, every term on the right-hand side except -B becomes 0, and we get -B = 2/(1-2)² or B = -2.

Plugging A, B, and C into our original formula then gives

and thus

From this we can read off (for large n):

We believe this because it looks like the solution we already got.

69. Asymptotic estimates

We can simplify our life considerably if we only want an asymptotic estimate of a_n (see AsymptoticNotation). The basic idea is that if a_n is non-negative for sufficiently large n and ∑ a_nzⁿ converges for some fixed value z, then a_n must be o(z^-n) in the limit. (Proof: otherwise, a_nzⁿ is at least a constant for infinitely many n, giving a divergent sum.) So we can use the radius of convergence of a generating function F(z), defined as the largest value r such that F(z) is defined for all (complex) z with |z| < r, to get a quick estimate of the growth rate of F's coefficients: whatever they do, we have a_n = O(r^-n).

For generating functions that are rational functions (ratios of polynomials), we can use the partial fraction expansion to do even better. First observe that for F(z) = ∑ f_izⁿ = 1/(1-az)^k, we have f_n = (k+n-1 choose n) aⁿ = ((n+k-1),,(k-1)/(k-1)!) aⁿ = Θ(aⁿ n^k-1). Second, observe that the denominator is irrelevant: if 1/(1-az)^k = Θ(aⁿ n^k-1) then bz^m/(1-az)^k-1 = b Θ(a^n-m (n-m)^k-1) = b a^-m (1-m/n)^k-1 Θ(aⁿ n^k-1) = Θ(aⁿ n^k-1), because everything outside the Θ disappears into the constant for sufficiently large n. Finally, observe that in a partial fraction expansion, the term 1/(1-az)^k with the largest coefficient a (if there is one) wins in the resulting asymptotic sum: Θ(aⁿ) + Θ(bⁿ) = Θ(aⁿ) if |a| > |b|. So we have:

Theorem

Let F(z) = ∑ f_nzⁿ = P(z)/Q(z) where P and Q are polynomials in z. If Q has a root r with multiplicity k, and all other roots s of Q satisfy |r| < |s|, then f_n = Θ((1/r)ⁿ n^k-1).

The requirement that r is a unique minimal root of Q is necessary; for example, F(z) = 2/(1-z²) = 1/(1-z) + 1/(1+z) generates the sequence 0, 2, 0, 2, ..., which is not Θ(1) because of all the zeros; here the problem is that 1-z² has two roots with the same absolute value, so for some values of n it is possible for them to cancel each other out.

A root in the denominator of a rational function F is called a pole. So another way to state the theorem is that the asymptotic value of the coefficients of a rational generating function is determined by the smallest pole.

More examples:

In each case it may be instructive to compare the asymptotic values to the exact values obtained earlier on this page.

70. Recovering the sum of all coefficients

Given a generating function for a convergent series ∑_i a_izⁱ, we can compute the sum of all the a_i by setting z to 1. Unfortunately, for many common generating functions setting z=1 yields 0/0 (if it yields something else divided by zero then the series diverges). In this case we can recover the correct sum by taking the limit as z goes to 1 using L'Hôpital's_rule, which says that lim_x→c f(x)/g(x) = lim_x→c f'(x)/g'(x) when the latter limit exists and either f(c) = g(c) = 0 or f(c) = g(c) = infinity.⁷

70.1. Example

Let's derive the formula for 1+2+...+n. We'll start with the generating function for the series ∑_i=0ⁿ zⁱ, which is (1-z^n+1)/(1-z). Applying the z d/dz method gives us

Plugging z=1 into this expression gives (1-(n+1)+n)/(1-1) = 0/0, which does not make us happy. So we go to the hospital—twice, since one application of L'Hôpital's rule doesn't get rid of our 0/0 problem:

which is our usual formula. Gauss's childhood proof is a lot quicker, but the generating-function proof is something that we could in principle automate most of the work using a computer_algebra_system, and it doesn't require much creativity or intelligence. So it might be the weapon of choice for nastier problems where no clever proof comes to mind.

More examples of this technique can be found on the BinomialCoefficients page, where the binomial theorem applied to (1+x)ⁿ (which is really just a generating function for ∑ (n choose i) zⁱ) is used to add up various sums of binomial coefficients.

71. A recursive generating function

Let's suppose we want to count binary trees with n internal nodes. We can obtain such a tree either by (a) choosing an empty tree (g.f.: z⁰ = 1); or (b) choosing a root with weight 1 (g.f. 1⋅z¹ = z, since we can choose it in exactly one way), and two subtrees (g.f. = F² where F is the g.f. for trees). This gives us a recursive definition

• F = 1 + zF².

Solving for F using the quadratic formula gives

That 2z in the denominator may cause us trouble later, but let's worry about that when the time comes. First we need to figure out how to extract coefficients from the square root term.

The binomial theorem says

For n ≥ 1, we can expand out the (1/2 choose n) terms as

For n=0, the switch from the big product of odd terms to (2n-2)! divided by the even terms doesn't work, because (2n-2)! is undefined. So here we just use the special case (1/2 choose 0) = 1.

Now plug this nasty expression back into F to get

Here we choose minus for the plus-or-minus to get the right answer and then do a little bit of tidying up of the binomial coefficient.

We can check the first few values of f(n):

and these are consistent with what we get if we draw all the small binary trees by hand.

The numbers (1/(n+1))(2n choose n) show up in a lot of places in combinatorics, and are known as the Catalan_numbers.

72. Summary of operations on generating functions

The following table describes all the nasty things we can do to a generating function. Throughout, we assume F = ∑ f_kz^k, G = ∑ g_kz^k, etc.

73. Variants

The exponential generating function or egf for a sequence a₀, ... is given by F(z) = ∑ a_nzⁿ/n!. For example, the egf for the sequence 1, 1, 1, ... is e^z = ∑ z^n/n!. Exponential generating functions admit a slightly different set of operations from ordinary generating functions: differentation gives left shift (since the factorials compensate for the exponents coming down), multiplying by z gives b_n = na_n+1, etc. The main application is that the product F(z)G(z) of two egf's gives the sequence whose n-th term is ∑ (n choose k) a_kb_n-k; so for problems where we want that binomial coefficient in the convolution (e.g. when we are building weight n objects not only by choosing a weight-k object plus a weight-(n-k) object but also by arbitrarily rearranging their unit-weight pieces) we want to use an egf rather than an ogf. We won't use these in CS202, but it's worth knowing they exist.

A probability generating function or pgf is essentially an ordinary generating function where each coefficient a_n is the probability that some random variable equals n. See RandomVariables for more details.

74. Further reading

RosenBook discusses some basic facts about generating functions in §7.4. ConcreteMathematics gives a more thorough introduction. Herbert Wilf's book generatingfunctionology, which can be downloaded from the web, will tell you more about the subject than you probably want to know.

See http://www.swarthmore.edu/NatSci/echeeve1/Ref/LPSA/PartialFraction/PartialFraction.html for very detailed notes on partial fraction expansion.

CategoryAlgorithmNotes CategoryMathNotes

76. History and interpretation

• Gambling: I throw two six-sided dice, what are my chances of seeing a 7?
• Insurance: I insure a typical resident of Smurfington-Upon-Tyne against premature baldness. How likely is it that I have to pay a claim?

Answers to these questions are summarized by a probability, a number in the range 0 to 1 that represents the likelihood that some event occurs. There are two dominant interpretations of this likelihood:

Frequentist interpretation

If an event occurs with probability p, then in the limit as I accumulate many examples of similar events, I will see the number of occurrences divided by the number of samples converging to p. For example, if I flip a fair coin over and over again many times, I expect that heads will come up roughly half of the times I flip it, because the probability of coming up heads is 1/2.

Bayesian interpretation

When I say that an event occurs with probability p, that means my subjective beliefs about the event would lead me to take a bet that would be profitable on average if this were the real probability. So a Bayesian would take a double-or-nothing bet on a coin coming up heads if they believed that the probability it came up heads was at least 1/2.

Frequentists and Bayesians have historically spent a lot of time arguing with each other over which interpretation makes sense. The usual argument against frequentist probability is that it only works for repeatable experiments, and doesn't allow for statements like "the probability that it will rain tomorrow is 50%" or the even more problematic "based on what I know, there is a 50% probability that it rained yesterday". The usual argument against Bayesian probability is that it's hopelessly subjective—it's possible (even likely) that my subjective guesses about the probability that it will rain tomorrow are not the same as yours. As mathematicians, we can ignore such arguments, and treat probability axiomatically as just another form of counting, where we normalize everything so that we always end up counting to exactly 1.

(Note: This caricature of the debate over interpreting probability is thoroughly incomplete. For a thoroughly complete discussion, see Probability, Interpretations Of at the Stanford Encyclopedia of Philosophy.)

77. Probability axioms

Coming up with axioms for probabilities that work in all the cases we want to consider took much longer than anybody expected, and the current set in common use only go back to the 1930's. Before presenting these, let's talk a bit about the basic ideas of probability.

An event A is something that might happen, or might not; it acts like a predicate over possible outcomes. The probability Pr[A] of an event A is a real number in the range 0 to 1, that must satisfy certain consistency rules like Pr[¬A] = 1-Pr[A].

In discrete probability, there is a finite set of atoms, each with an assigned probability, and every event is a union of atoms. The probability assigned to an event is the sum of the probabilities assigned to the atoms it contains. For example, we could consider rolling two six-sided dice. The atoms are the pairs (i,j) that give the value on the first and second die, and we assign a probability of 1/36 to each pair. The probability that we roll a 7 is the sum of the cases (1,6), (2,5), (3,4), (4,3), (5,2), and (6,1), or 6/36 = 1/6.

Discrete probability doesn't work if we have infinitely many atoms. Suppose we roll a pair of dice infinitely many times (e.g., because we want to know the probability that we never accumulate more 6's than 7's in this infinite sequence). Now there are infinitely many possible outcomes: all the sequences of pairs (i,j). If we make all these outcomes equally likely, we have to assign each a probability of zero. But then how do we get back to a probability of 1/6 that the first roll comes up 7?

77.1. The Kolmogorov axioms

A triple (S,F,P) is a probability space if S is a set of outcomes (where each outcome specifies everything that ever happens, in complete detail); F is a sigma-algebra, which is a family of subsets of S, called measurable sets, that is closed under complement (i.e., if A is in F then S-A is in F) and countable union (union of A₁, A₂, ... is in F if each set is); and P is a probability measure that assigns a number in [0,1] to each set in F. The measure P must satisfy three axioms:

1. P(S) = 1.
2. P(Ø) = 0.

3. For any sequence of pairwise disjoint events A₁, A₂, A₃, ..., P(∪A_i) = ∑P(A_i).

From these one can derive rules like P(S-A) = 1-P(A) etc.

Most of the time, S is finite, and we can just make F include all subsets of S, and define Pr[A] to be the sum of Pr[{x}] over all x in A; this gets us back to the discrete probability model we had before.

77.2. Examples of probability spaces

• S = {H,T}, F = ℘S, Pr[A] = |A|/2. This represents a fair coin with two outcomes H and T that each occur with probability 1/2.
• S = {H,T}, F = ℘S, Pr[{H}] = p, Pr[{T}] = 1-p. This represents a biased coin, where H comes up with probability p.
• S = { (i,j): i,j∈{1,2,3,4,5,6} }, F = ℘S, Pr[A] = |A|/36. Roll of two fair dice. A typical event might be "the total roll is 4", which is the set { (1,3), (2,2), (3,1) } with probability 3/36 = 1/12.

• S = ℕ, F = ℘S, Pr[A] = ∑_n∈A 2^-n-1. This is an infinite probability space; a real-world process that might generate it is to flip a fair coin repeatedly and count how many times it comes up tails before the first time it comes up heads. Note that even though it is infinite, we can still define all probabilities by summing over atoms: Pr[0] = 1/2, Pr[1] = 1/4, Pr[2] = 1/8, etc.

It's unusual for anybody doing probability to actually write out the details of the probability space like this. Much more often, a writer will just assert the probabilities of a few basic events (e.g. Pr[H] = 1/2), and claim that any other probability that can be deduced from these initial probabilities from the axioms also holds (e.g. Pr[T] = 1-Pr[H] = 1/2). The main reason Kolmogorov gets his name attached to the axioms is that he was responsible for Kolmogorov's existence theorem, which says (speaking very informally) that as long as your initial assertions are consistent, there exists a probability space that makes them and all their consequences true.

78. Probability as counting

The easiest probability space to work with is a uniform discrete probability space, which has N outcomes each of which occurs with probability 1/N. If someone announces that some quantity is "random" without specifying probabilities (especially if that someone is a computer scientist), the odds are that what they mean is that each possible value of the quantity is equally likely. If that someone is being more careful, they would say that the quantity is "drawn uniformly at random" from a particular set.

Such spaces are among the oldest studied in probability, and go back to the very early days of probability theory where randomness was almost always expressed in terms of pulling tokens out of well-mixed urns, because such urn models where one of the few situtations where everybody agreed on what the probabilities should be.

78.1. Examples

• A random bit has two outcomes, 0 and 1, and each occurs with probability 1/2.

• A die roll has six outcomes, 1 through 6, and each occurs with probability 1/6.

• A roll of two dice has 36 outcomes (order of the dice matters); each occurs with probability 1/36.

• A random n-bit string of length n has 2ⁿ outcomes; each occurs with probability 2^-n. The probability that exactly 1 bit is a 1 is obtained by counting all strings with a single 1 and dividing by 2ⁿ: n2^-n.

• A poker hand consists of a subset of 5 cards drawn uniformly at random from a deck of 52 cards. Depending on whether the order of the 5 cards is considered important (usually it isn't), there are either or (52)₅ possible hands. The probability of getting a flush (all 5 cards in the hand drawn from the same suit of 13 cards) is ; there are 4 choices of suits, and ways to draw 5 cards from each suit.

• A random permutation on n items has n! outcomes, one for each possible permutation. A typical event might be that the first element of a random permutation of 1..n is 1; this occurs with probability (n-1)!/n! = 1/n. Another example of a random permutation might be a uniform shuffling of a 52-card deck (difficult to achieve in practice!): here the probability that we get a particular set of 5 cards as the first 5 in the deck is obtained by counting all the permutations that have those 5 cards in the first 5 positions (there are 5!×47! of them) divided by 52!. The result is the same that we get from the uniform poker hands.

79. Independence and the intersection of two events

Events A and B are independent if Pr[A∩B] = Pr[A]·Pr[B]. In general, a group of events {A_i} is independent if each A_i is independent of any event defined only in terms of the other events.

It can be dangerous to assume that events are independent when they aren't, but quite often when describing a probability space we will explicitly state that certain events are independent. For example, one typically describes the space of random n-bit strings (or n coin flips) by saying that one has n independent random bits and then deriving that each particular sequence occurs with probability 2^-n rather than starting with each sequence occuring with probability 2^-n and then calculating that each particular bit is 1 with independent probability 1/2; the first description makes much more of the structure of the probability space explicitly, and so is more directly useful in calculation.

79.1. Examples

• What is the probability of getting two heads on independent coin flips? Pr[H₁∩H₂] = (1/2)(1/2) = 1/4.

• Suppose the coin-flips are not independent (maybe the two coins are glued together). What is the probability of getting two heads? This can range anywhere from zero (coin 2 always comes up the opposite of coin 1) to 1/2 (if coin 1 comes up heads, so does coin 2).

• What is the probability that both you and I draw a flush (all 5 cards the same suit) from the same poker deck? Since we are fighting over the same collection of same-suit subsets, we'd expect Pr[A∩B] < Pr[A] Pr[B]—the event that you get a flush (A) is not independent of the event that I get a flush (B), and we'd have to calculate the probability of both by counting all ways to draw two hands that are both flushes. But if we put your cards back and then shuffle the deck again, the events in this new case are independent, and we can just square the Pr[flush] we calculated before.

• Suppose the Red Sox play the Yankees. What is the probability that the final score is exactly 4-4? Amazingly, it appears that it is equal to Pr[Red Sox score 4 runs against the Yankees]*Pr[Yankees score 4 runs against the Red Sox] (see http://arXiv.org/abs/math/0509698 for a paper discussing this issue)—to the extent we can measure the underlying probability distribution, the score of each team in a professional baseball game appears to be independent of the score of the other team.

80. Union of two events

What is the probability of A∪B? If A and B are disjoint, then the axioms give Pr[A∪B] = Pr[A] + Pr[B]. But what if A and B are not disjoint?

By analogy to inclusion-exclusion in counting we would expect that

• Pr[A∪B] = Pr[A] + Pr[B] - Pr[A∩B].

Intuitively, when we sum the probabilities of A and B we double-count the event that both occur, and must subtract it off to compensate. To prove this formally, consider the events A∩B, A∩¬B, and ¬A∩B. These are disjoint, so the probability of the union of any subset of this set of events is equal to the sum of its components. So in particular we have

• Pr[A] + Pr[B] - Pr[A∩B] = (Pr[A∩B] + Pr[A∩¬B]) + (Pr[A∩B] + Pr[¬A∩B]) - Pr[A∩B] = Pr[A∩B] + Pr[A∩¬B] + Pr[¬A∩B] = Pr[A∪B].

80.1. Examples

• What is the probability of getting at least one head out of two independent coin-flips? Pr[H₁∩H₂] = 1/2 + 1/2 - (1/2)(1/2) = 3/4.

• What is the probability of getting at least one head out of two coin-flips, when the coin-flips are not independent? Here again we can get any probability from 0 to 1, depending on what 1-Pr[H₁H₂] is.

81. Conditional probability

Suppose I want to answer the question "What is the probability that my dice add up to 6 if I know that the first one is an odd number?" This question involves conditional probability, where we calculate a probability subject to some conditions. The probability of an event A conditioned on an event B, written Pr(A|B), is defined by the formula

One way to think about this is that when we assert that B occurs we are in effect replacing the entire probability space with just the part that sits in B. So we have to divide all of our probabilities by Pr[B] in order to make Pr[B|B] = 1, and we have to replace A with A∩B to exclude the part of A that can't happen any more.

Note also that conditioning on B only makes sense if Pr[B] > 0. If Pr[B] = 0, Pr[A|B] is undefined.

81.1. Conditional probabilities and intersections of non-independent events

Simple algebraic manipulation gives

So one of the ways to compute the probability of two events occurring is to compute the probability of one of them, and the multiply by the probability that the second occurs conditioned on the first. For example, if my attempt to reach the summit of Mount Everest requires that I first learn how to climb mountains (Pr[B] = 10%) and then make it to the top safely (Pr[A|B] = 90%), then my chances of getting to the top are Pr[A∩B] = (90%)(10%) = 9%.

We can do this for sequences of events as well. Suppose that I have an urn that starts with k black balls and 1 red ball. In each of n trials I draw one ball uniformly at random from the urn. If it is red, I give up. If it is black, I put the ball back and add another black ball, thus increasing the number of balls by 1. What is the probability that on every trial I get a black ball?

Let A_i be the event that I get a black ball on the first i trials. Then Pr[A₀] = 1, and for larger i we have Pr[A_i] = Pr[A_i|A_i-1] Pr[A_i-1]. If A_i-1 holds, then at the time of the i-th trial we have k+i total balls in the urn of which one is red. So the probability that we draw a black ball is 1-1/(k+i) = (k+i-1)/(k+i). By induction we can then show that

This is an example of a collapsing product, where the denominator of each fraction cancels out the numerator of the next; we are left only with the denominator k+i of the last term and the numerator k of the first, giving Pr[A_i] = k/(k+i). It follows that we make it through all n trials with probability Pr[A_n] = k/(k+n).

81.2. The law of total probability

We can use the fact that A is the disjoint union of A∧B and A∧¬B to get Pr[A] by case analysis:

So, for example, there is a 20% chance I can make it to the top of Mt Everest safely without learning how to climb first, my chances of getting there go up to (90%)(10%) + (20%)(90%) = 27%.

This method is sometimes given the rather grandiose name of the law of total probability. The most general version is that if B₁..B_n are all disjoint events, then

81.3. Bayes's formula

If one knows Pr[A|B], Pr[A|¬B], and Pr[B], it's possible to compute Pr[B|A]:

This formula is used heavily in statistics, where it goes by the name of Bayes's formula. Say that you have an Airport Terrorist Detector that lights up 75% of the time when inserted into the nostrils of a Terrorist, but lights up 0.1% of the time when inserted into the nostrils of a non-Terrorist. Suppose that for other reasons you know that Granny has only a 0.01% chance of being a Terrorist. What is the probability that Granny is a Terrorist if the detector lights up?

Let B be the event "Granny is a terrorist" and A the event "Detector lights up". Then Pr[B|A] = (75% * 0.01%)/(75% * 0.01% + 0.1% * 99.99%) ≅ 0.07495%. This examples show how even a small "false negative" rate can make it difficult to interpret the results of tests for rare conditions.

82. Random variables

A random variable X is a function from a probability space to some codomain; for more details see RandomVariables.

CategoryMathNotes

84. Random variables

A random variable X is a variable that takes on particular values randomly. This means that for each possible value x, there is an event [X=x] with some probability of occurring that corresponds to X (the random variable, usually written as an upper-case letter) taking on the value x (some fixed value).

Examples of random variables:

• Indicator variables: The indicator variable for an event A is a variable X that is 1 if A occurs and 0 if it doesn't (i.e., X(ω) = 1 if ω∈A and 0 otherwise). Indicator variables are often written using the Greek letter chi (e.g. χ_A) or using bracket notation (e.g., [A], [Y² > 3], [all six coins come up heads]).

• Functions of random variables: Any function you are likely to run across of a random variable or random variables is a random variable, e.g. X+Y, XY, log X, etc.
• Counts: Flip a fair coin n times and let X be the number of times it comes up heads. Then X is an integer-valued random variable.

• Random sets and structures: Suppose that we have a set T of n elements, and we pick out a subset U by flipping an independent fair coin for each element to decide whether to include it. Then U is a set-valued random variable. Or we could consider the infinite sequence X₀, X₁, X₂, ..., where X₀ = 0 and X_n+1 is either X_n+1 or X_n-1, which being chosen by an independent fair coin flip. Then we can think of the entire sequence X as a sequence-valued random variable.

85. The distribution of a random variable

The distribution of a random variable describes the probability that it takes on various values. For discrete random variables (variables that take on only countably many values, each with nonzero probability), the distribution is most easily described by just giving the probability Pr[X=x] for each value x.⁸

Often if we know the distribution of a random variable, we don't bother worrying about what the underlying probability space is. The reason for this is we can just take Ω to be the range of the random variable, and define Pr[ω] for each ω∈Ω to be Pr[X=ω]. For example, a six-sided die corresponds to taking Ω = {1,2,3,4,5,6}, assigning Pr[ω] = 1/6 for all ω∈Ω, and letting X(ω) = ω.

The same thing works if we have multiple random variables, but now we let each point in the space be a tuple that gives the values of all of the variables. Specifying the probability in this case is done using a joint distribution (see below).

85.1. Some standard distributions

Here are some common distributions for a random variable X:

Bernoulli distribution

Pr[X = 1] = p, Pr[X = 0] = q, where p is a parameter of the distribution and q = 1-p. This corresponds to a single biased coin-flip.

Binomial distribution

Pr[X = k] = (n choose k) p^k q^(n-k), where n and p are parameters of the distribution and q = 1-p. This corresponds to the sum of n biased coin-flips.

Geometric distribution

Pr[X = k] = q^kp, where p is a parameter of the distribution and q is again equal to 1-p. This corresponds to number of tails we flip before we get the first head in a sequence of biased coin-flips.

Poisson distribution

Pr[X = k] = e^-λλ^k/k!. This is what happens to a binomial distribution when we fix p = λ/n and then take the limit as n goes to infinity; we can think of it as counting the number of events that occur in one time unit if the events occur at a constant continuous rate that averages λ events per time unit. The canonical example is radioactive decay.

Uniform distribution

The distribution function F of X is given by F(x) = 0 when x ≤ a, (x-a)/(b-a) when a ≤ x ≤ b, and 1 when b ≤ x, where a and b are parameters of the distribution. This is a continuous random variable that has equal probability of landing anywhere in the [a,b] interval.

Another very important distribution is the normal distribution, but it's not discrete so we would need more machinery to talk about it.

85.2. Joint distributions

Two or more random variables can be described using a joint distribution. For discrete random variables, this just gives Pr[X=x ∧ Y=y] for all fixed values x and y, or in general gives Pr[∀i X_i=x_i].

Given a joint distribution on X and Y, we can recover the distribution on X or Y individually by summing up cases: Pr[X=x] = ∑_y Pr[X=x ∧ Y=y]. The distribution of X obtained in this way is called a marginal distribution of the original joint distribution. In general we can't go in the other direction, because just knowing the marginal distributions doesn't tell us how the random variables might be related to each other.

Examples:

• Let X and Y be six-sided dice. Then Pr[X=x ∧ Y=y] = 1/36 for all values of x and y in the right range. The underlying probability space consists of all pairs (x,y) in {1,2,3,4,6}×{1,2,3,4,5,6}.
• Let X be a six-sided die and let Y = 7 - X. Then Pr[X=x ∧ Y=y] = 1/6 if 1 ≤ x ≤ 6 and y = 7-x, and 0 otherwise, with the underlying probability space most easily described by including just six points for the X values (although we could also do {1,2,3,4,5,6}×{1,2,3,4,5,6} as in the previous case, just assigning probability 0 to most of the points). However, even though the joint distribution is very different from the previous case, the marginal distributions of X and Y are exactly the same as before: each of X and Y takes on all values in {1,2,3,4,5,6} with equal probability.

85.3. Independence of random variables

The difference between the two preceding examples is that in the first case, X and Y are independent, and in the second case, they aren't.

Two random variables X and Y are independent if any pair of events of the form X∈A, Y∈B are independent. For discrete random variables, it is enough to show that Pr[X=x ∧ Y=y] = Pr[X=x]⋅Pr[Y=y], or in other words that the events [X=x] and [Y=y] are independent for all values x and y. In practice, we will typically either be told that two random variables are independent or deduce it from how they are generated.

Examples:

• Roll two six-sided dice, and let X and Y be the values of the dice. By convention we assume that these values are independent. This means for example that Pr[X∈{1,2,3} ∧ Y∈{1,2,3}] = [Pr[X∈{1,2,3}]⋅Pr[Y∈{1,2,3}] = (1/2)(1/2) = 1/4, which is a slightly easier computation than counting up the 9 cases (and then argue that each occurs with probability (1/6)², which requires knowing that X and Y are independent).

• Take the same X and Y, and let Z = X+Y. Now Z and X are not independent, because Pr[X=1 ∧ Z=12] = 0, which is not equal to Pr[X=1]⋅Pr[Z=12] = (1/6)(1/36) = 1/216.
• Place two radioactive sources on opposite sides of the Earth, and let X and Y be the number of radioactive decay events in each source during some 10ms interval. Since the sources are 42ms away from each other at the speed of light, we can assert that either X and Y are independent, or the world doesn't behave the way the physicists think it does. This is an example of variables being independent because they are physically independent.
  • Roll one six-sided die X, and let Y = ⌈X/2⌉ and Z = X mod 2. Then Y and Z are independent, even though they are generated using the same physical process.

In general, if we have a collection of random variables X_i, we say that they are all independent if the joint distribution is the product of the marginal distributions, i.e. if Pr[∀i X_i=x_i] = ∏_i Pr[X_i=x_i]. It may be that a collection of random variables is not independent even though all subcollections are.

• Let X and Y be fair coin-flips, and let Z = X⊕Y. Then any two of X, Y, and Z are independent, but the three variables X, Y, and Z are not independent, because (for example) Pr[X = 0 ∧ Y = 0 ∧ Z = 0] = 1/4 instead of 1/8 as one would get by taking the product of the marginal distributions.

Since we can compute the joint distribution from the marginal distributions for independent variables, we will often just specify the marginal distributions and declare that a collection of random variables are independent. This implicitly gives us an underlying probability space consisting of all sequences of values for the variables.

86. The expectation of a random variable

For a real-valued random variable X, its expectation E[X] (sometimes just EX) is its average value, weighted by probability.⁹> For discrete random variables, the expectation is defined by

Example (discrete variable)

Let X be the number rolled with a fair six-sided die. Then E[X] = (1/6) (1+2+3+4+5+6) = 3½.

Example (unbounded discrete variable)

Let X be a geometric random variable with parameter p, i.e., let Pr[X = k] = q^kp, where q = 1-p. Then E[X] = .

Expectation is a way to summarize the distribution of a random variable without giving all the details. If you take the average of many independent copies of a random variable, you will be likely to get a value close to the expectation. Expectations are also used in decision theory to compare different choices. For example, given a choice between a 50% chance of winning $100 (expected value: $50) and a 20% chance of winning $1000 (expected value: $200), a rational decision maker would take the second option. Whether ordinary human beings correspond to an economist's notion of a rational decision maker often depends on other details of the situation.

Terminology note: If you hear somebody say that some random variable X takes on the value z on average, this usually means that E[X] = z.

86.1. Variables without expectations

If a random variable has a particularly annoying distribution, it may not have a finite expectation, even thought the variable itself takes on only finite values. This happens if the sum for the expectation diverges.

For example, suppose I start with a dollar, and double my money every time a fair coin-flip comes up heads. If the coin comes up tails, I keep whatever I have at that point. What is my expected wealth at the end of this process?

Let X be the number of times I get heads. Then X is just a geometric random variable with p = 1/2, so Pr[X=k] = (1-(1/2))^k(1/2)^k = 2^-k-1. My wealth is also a random variable: 2^X. If we try to compute E[2^X], we get

which diverges. Typically we say that a random variable like this has no expected value, although sometimes you will see people writing E[2^X] = ∞.

(For an even nastier case, consider what happens with E[(-2)^X].)

86.2. Expectation of a sum

The expectation operator is linear: this means that E(X+Y) = E(X)+E(Y) and E(aX) = aE(X) when a is a constant. This fact holds for all random variables X and Y, whether they are independent or not, and is not hard to prove for discrete probability spaces:

Linearity of expectation makes computing many expectations easy. Example: Flip a fair coin n times, and let X be the number of heads. What is E[X]? We can solve this problem by letting X_i be the indicator variable for the event "coin i came up heads". Then X = ∑_i X_i and EX = E[∑_i X_i] = ∑_i EX_i = n(½) = n/2. In principle it is possible to calculate the same value from the distribution of X (which involves a lot of binomial coefficients), but linearity of expectation is much easier.

Example

Choose a random permutation f, i.e. a random bijection from 1..n → 1..n. What is the expected number of values i for which f(i) = i?

Solution

Let X_i be the indicator variable for the event that f(i) = i. Then we are looking for E[X₁ + X₂ + ... X_n] = E[X₁] + E[X₂] + ... E[X_n]. But E[X_i] is just 1/n for each i, so the sum is n(1/n) = 1. (Calculating this by computing Pr[∑X_i] = x first would be very painful.)

86.3. Expectation of a product

For products of random variables, the situation is more complicated. Here the rule is that E[XY] = E[X]⋅E[Y] if X and Y are independent. But if X and Y are not independent, their expectation can be arbitrary.

Example

Roll 2 dice and take their product. What value do we get on average? The product formula gives E[XY] = E[X]E[Y] = (7/2)² = (49/4) = 12¼. We could also calculate this directly by summing over all 36 cases, but it would take a while.

Example

Roll 1 die and multiply it by itself. What value do we get on average? Here we are no longer dealing with independent random variables, so we have to do it the hard way: E[X²] = (1²+2²+3²+4²+5²+6²)/6 = 91/6 = 15⅙. This is substantially higher than when the dice are uncorrelated. (Exercise: How can you rig the second die so it still comes up with each value ⅙ of the time but minimizes E[XY]?)

We can prove the product rule without too much trouble for discrete random variables. The easiest way is to start from the right-hand side.

Here we use independence in going from Pr[X=x] Pr[Y=y] to Pr[X=x ∧ Y=y] and use the union rule to convert the x,y sum into Pr[XY=z].

86.4. Conditional expectation

Like conditional probability, there is also a notion of conditional expectation. The simplest version of conditional expectation conditions on a single event A, is written E[X|A], and is defined for discrete random variables by

This is exactly the same as unconditioned expectation except that the probabilities are now conditioned on A.

Example

What is the expected value of a six-sided die conditioned on not rolling a 1? The conditional probability of getting 1 is now 0, and the conditional probability of each of the remaining 5 values is 1/5, so we get (1/5)(2+3+4+5+6) = 4.

Conditional expectation acts very much like regular expectation, so for example we have E[aX+bY|A] = aE[X|A] + bE[Y|A].

One of the most useful applications of conditional expectation is that it allows computing (unconditional) expectations by case analysis, using the fact that

• E[X] = E[X|A]Pr[A] + E[X|¬A]Pr[¬A].

86.4.1. Examples

86.4.1.1. The Treasure on Mt Everest

I have a 50% chance of reaching the top of Mt Everest, where Sir Edmund Hilary and Tenzing Norgay hid somewhere between 0 and 10 kilograms of gold (a random variable with uniform distribution). How much gold do I expect to bring home? Compute E[X] = E[X|reached the top]Pr[reached the top] + E[X|didn't make it]Pr[didn't make it] = 5⋅0.5 + 0⋅0.5 = 2.5.

86.4.1.2. Waiting times

Suppose I flip a coin that comes up heads with probability p until I get heads. How many times on average do I flip the coin?

We'll let X be the number of coin flips. Conditioning on whether the coin comes up heads on the first flip gives E[X] = 1⋅p + (1+E[X'])⋅(1-p), where X' is random variable counting the number of coin-flips needed to get heads ignoring the first coin-flip. But since X' has the same distribution as X, we get EX = p + (1-p) (1+EX) or EX = (p+(1-p))/p = 1/p. So a fair coin must be flipped twice on average to get a head, which is about what we'd expect if we hadn't thought about it much.

86.4.1.3. Rewarding success and punishing failure

Suppose I have my experimental test subjects complete a task that gets scored on a scale of 0 to 100. I decide to test whether rewarding success is a better strategy for improving outcomes than punishing failure. So for any subject that scores high than 50, I give them a chocolate bar. For any subject that scores lower than 50, I give them an electric shock. (Students who score exactly 50 get nothing.) I then have them each perform the task a second time and measure the average change in their scores. What happens?

Let's suppose that there is no effect whatsoever of my rewards and punishments, and that each test subject obtains each possible score with equal probability 1/101. Now let's calculate the average improvement for test subjects who initially score less than 50 or greater than 50. Call the outcome on the first test X and the outcome on the second test Y.

In the first case, we are computing E[Y-X | X < 50]. This is the same as E[Y | X < 50] - E[X | X<50] = E[Y] - E[X|X<50] = 50 - 24.5 = +25.5. So punishing failure produces a 25.5 point improvement on average.

In the second case, we are computing E[Y-X | X > 50]. This is the same as E[Y | X > 50] - E[X | X>50] = E[Y] - E[X|X>50] = 50 - 75.5 = -25.5. So rewarding success produces a 25.5 point decline on average.

Clearly this suggests that we punish failure if we want improvements and reward success if we want backsliding. This is intuitively correct: punishing failure encourages our slacker test subjects to do better next time, while rewarding success just makes them lazy and complacent. But since the test outcomes don't depend on anything we are doing, we get exactly the same answer if we reward failure and punish success: in the former case, a +25.5 point average change, in the later a -25.5 point average change. This is also intuitively correct: rewarding failure makes our subjects like the test so that they will try to do better next time, while punishing success makes them feel that it isn't worth it. From this we learn that our intuitions¹⁰ provide powerful tools for rationalizing almost any outcome in terms of the good or bad behavior of our test subjects. A more careful analysis shows that we performed the wrong comparison, and we are the victim of regression to the mean.

For a real-world example of how similar problems can arise in processing data, the United States Bureau of Labor Statistics defines a small business as any company with 500 or fewer employees. So if a company has 400 employees in 2007, 600 in 2008, and 400 in 2009, then we just saw a net creation of 200 new jobs by a small business in 2007, followed by the destruction of 200 jobs by a large business in 2008. This effect alone accounts for most of the observation that small businesses generate more new jobs than large ones.

86.4.2. Conditioning on a random variable

There is a more general notion of conditional expectation for random variables, where the conditioning is done on some other random variable Y. Unlike E[X|A], which is a constant, the expected value of X conditioned on Y, written E[X|Y], is itself a random variable: when Y = y, it takes on the value E[X|Y=y].

Example

Let us compute E[X+Y|X] where X and Y are the values of independent six-sided dice. When X = x, E[X+Y|X] = E[X+Y|X=x] = x+E[Y] = x + 7/2. For the full random variable we can write E[X+Y|X] = X + 7/2.

Another way to get the result in the preceding example is to use some general facts about conditional expectation:

• E[aX+bY|Z] = aE[X|Z] + bE[Y|Z]. This is the conditional-expectation version of linearity of expectation.
• E[X|X] = X. This is immediate from the definition, since E[X|X=x] = x.
• If X and Y are independent, then E[Y|X] = E[Y]. The intuition is that knowing the value of X gives no information about Y, so E[Y|X=x] = E[Y] for any x in the range of X. (To do this formally requires using the fact that Pr[Y=y|X=x] = Pr[Y=y /\ X=x] / Pr[X=x] = Pr[Y=y]Pr[X=x]/Pr[X=x] = Pr[Y=y], provided X and Y are independent.)
• Also useful: E[E[X|Y]] = E[X]. Averaging a second time removes all dependence on Y.

These in principle allow us to do very complicated calculations involving conditional expectation. For example:

Example

Let X and Y be the values of independent six-sided dice. What is E[X | X+Y]? Here we observe that X+Y = E[X+Y | X+Y] = E[X | X+Y] + E[Y | X+Y] = 2E[X | X+Y] by symmetry. So E[X | X+Y] = (X+Y)/2. This is pretty much what we'd expect: on average, half the total value is supplied by one of the dice. (It also works well for extreme cases like X+Y = 12 or X+Y = 2, giving a quick check on the formula.)

Example

What is E[(X+Y)² | X] when X and Y are independent? Compute E[(X+Y)² | X] = E[X² | X] + 2E[XY | X] + E[Y² | X] = X² + 2X E[Y] + E[Y²]. For example, if X and Y are independent six-sided dice we have E[(X+Y)² | X] = X² + 7X + 91/6, so if you are rolling the dice one at a time and the first one comes up 5, you can expect on average to get a squared total of 25 + 35 + 91/6 = 75 1/6. But if the first one comes up 1, you only get 1 + 7 + 91/6 = 23 1/6 on average.

86.5. Markov's inequality

Knowing the expectation of a random variable gives you some information about it, but different random variables may have the same expectation but very different behavior: consider, for example, the random variable X that is 0 with probability 1/2 and 1 with probability 1/2 and the random variable Y that is 1/2 with probability 1. In some cases we don't care about the average value of a variable so much as its likelihood of reaching some extreme value: for example, if my feet are encased in cement blocks at the beach, knowing that the average high tide is only 1 meter is not as important as knowing whether it ever gets above 2 meters. Markov's inequality lets us bound the probability of unusually high values of non-negative random variables as a function of their expectation. It says that, for any a > 0,

• Pr[X > aEX] < 1/a.

This can be proved easily using conditional expectations. We have:

• EX = E[X|X > aEX] Pr[X > aEX] + E[X|X ≤ aEX] Pr[X > aEX].

Since X is non-negative, E[X|X ≤ aEX] ≥ 0, so subtracting out the last term on the right-hand side can only make it smaller. This gives:

• EX ≥ E[X|X > aEX] Pr[X > aEX] > aEX Pr[X > aEX]

and dividing both side by aEX gives the desired result.

Another version of Markov's inequality replaces > with ≥:

• E[X ≥ aEX] ≤ 1/a.

The proof is essentially the same.

Example

Suppose that that all you know about high tide is that EX = 1 meter and X ≥ 0. What can we say about the probability that X > 2 meters? Using Markov's inequality, we get Pr[X > 2 meters] = Pr[X > 2EX] < 1/2.

There is, of course, a conditional version of Markov's inequality:

• Pr[X > aE[X|A] | A] < 1/a.

This version doesn't get anywhere near as much use as the unconditioned version, but it may be worth remembering that it exists.

87. The variance of a random variable

Expectation tells you the average value of a random variable but it doesn't tell you how far from the average the random variable typically gets: the random variable X = 0 and Y = ±1,000,000,000,000 with equal probability both have expectation 0, though their distributions are very different. Though it is impossible to summarize everything about the spread of a distribution in a single number, a useful approximation for many purposes is the variance Var(X) of a random variable X, which is defined as the expected square of the deviation from the expectation, or E((X-EX)²).

Example

Let X = 0 or 1 with equal probability. Then EX = 1/2, and (X-EX)² is always 1/4. So Var(X) = 1/4.

Example

Let X be the value of a fair six-sided die. Then EX = 7/2, and E((E-EX)²) = (1/6)((1-7/2)² + (2-7/2)² + (3-7/2)² + ... + (6 - 7/2)²) = 35/12.

Computing variance directly from the definition can be tedious. Often it is easier to compute it from E(X²) and EX:

• Var[X] = E[(X-EX)²] = E[X² - 2 X EX + (EX)²] = E[X²] - 2 EX EX + (EX)² = E[X²] = (EX)².

(The second-to-last step uses linearity of expectation and the fact that EX is a constant.)

Example

For X = 0 or 1 with equal probability, we have E[X²] = 1/2 and (EX)² = 1/4, so Var[X] = 1/4.

Example

Let's try the six-sided die again, except this time we'll use an n-sided die. We have

When n = 6, this gives 7⋅13/6 - 49/4 = 35/12. (Ok, maybe it isn't always easier).

87.1. Multiplication by constants

Suppose we are asked to compute the variance of aX, where a is a constant. We have

• Var[aX] = E[(aX)²] - E[aX]² = a²E[X²] - (aE[X])² = a² Var[X].

So, for example, if X = 0 or 2 with equal probability, Var[X] = 4⋅(1/4) = 1. This is exactly what we expect given that X-EX is always ±1.

Another consequence is that Var[-X] = (-1)²Var[X] = Var[X]. So variance is not affected by negation.

87.2. The variance of a sum

What is Var[X+Y]? Write

The quantity E[XY] - EX EY is called the covariance of X and Y and is written Cov(X,Y). So we have just shown that

• Var[X+Y] = Var[X] + Var[Y] + 2 Cov(X,Y).

When Cov(X,Y) = 0, or equivalently when E[XY] = EX EY, X and Y are said to be uncorrelated and their variances add. This occurs when X and Y are independent, but may also occur without X and Y being independent.

For larger sums the corresponding formula is

This simplifies to Var(∑X_i) = ∑Var(X_i) when the X_i are pairwise independent, so that each pair of distinct X_i and X_j are independent. (This is implied by independence but is not equivalent to it.)

Example

What is the variance of the number of heads in n independent fair coin-flips? Let X_i be the indicator variable for the event that the i-th flip comes up heads and let X be the sum of the X_i. We have already seen that Var[X_i] = 1/4, so Var[X] = n Var[X_i] = n/4.

Example

Let a be a constant. What is the variance of X+a? We have Var[X+a] = Var[X] + Var[a] = Var[X], since (1) E[aX] = aE[X] = E[a]E[X] means that a (considered as a random variable) and X are uncorrelated, and (2) Var[a] = E[a-Ea] = E[a-a] = 0. So shifting a random variable up or down doesn't change its variance.

87.3. Chebyshev's inequality

Variance is an expectation, so we can use Markov's inequality on it. The result is Chebyshev's inequality:

• Pr[|X - EX| > r) < Var[X] / r².

Proof: The event |X - EX| > r is the same as the event (X-EX)² > r². By Markov's inequality, the probability that this occurs is at most E[(E-EX)²]/r² = Var[X]/r².

87.3.1. Application: showing that a random variable is close to its expectation

This is the usual statistical application.

Example

Flip a fair coin n times, and let X be the number of heads. What is the probability that |X-n/2| > r? Recall that Var[X] = n/4, so Pr[|X-n/2| > r] < (n/4)/r² = n/(4r²). So, for example, the chances of deviating from the average by more than 1000 after 1000000 coin-flips is less than 1/4.

Example

Out of n voters in Saskaloosa County, m plan to vote for Smith for County Dogcatcher. A polling firm samples k voters (with replacement) and asks them who they plan to vote for. Suppose that m < n/2; compute a bound on the probability that the polling firm incorrectly polls a majority for Smith.