Formula & theorem reference

This isn't really a theorem to prove so much as a fact to see. Lay the first choice's m options down the rows of a grid and the second choice's n options across the columns. Every cell of that grid is exactly one valid pairing — one option from the first choice matched with one option from the second — and every valid pairing lands in exactly one cell. A grid with m rows and n columns has m \times n cells. Counting the pairings and counting the cells are the same question, so they have the same answer. Chaining a third independent choice onto the pair just replaces each cell of that grid with a fresh n_3-row stack, and multiplication absorbs each new stage the same way.

This is just the counting principle, run r times in a row. The first position in the arrangement can be filled by any of the n items. The second position can be filled by any of the n - 1 items that remain (one has been used). The third by any of the n-2 remaining, and so on, down to the rth position, which has n - (r-1) = n - r + 1 choices left. Multiply across all r positions: P(n,r) = n \cdot (n-1) \cdot (n-2) \cdots (n - r + 1). That product has exactly r factors, starting at n and counting down. To see it equals \frac{n!}{(n-r)!}, write n! in full and notice the tail end cancels: n! = \bigl[n(n-1)\cdots(n-r+1)\bigr] \cdot (n-r)!, so dividing both sides by (n-r)! leaves exactly the product above.

Start from P(n,r), which counts every arrangement of r chosen items. Each unordered group of r items corresponds to many of those arrangements — specifically, every one of the r! ways to reorder that same group is a different permutation but the exact same combination. So P(n,r) overcounts each combination by a factor of r!, and dividing it out gives the true count: C(n,r) = \frac{P(n,r)}{r!} = \frac{n!/(n-r)!}{r!} = \frac{n!}{r!\,(n-r)!}.

Count the size-k subsets of an n-element set \{1, 2, \ldots, n\} two ways. The left side, \binom{n}{k}, counts them directly. For the right side, split every size-k subset by whether it contains the element n or not — an exhaustive, non-overlapping split. A subset containing n is n together with a size-(k-1) subset of the remaining n-1 elements: \binom{n-1}{k-1} such subsets. A subset not containing n is a size-k subset chosen entirely from those same n-1 elements: \binom{n-1}{k} of those. Every size-k subset falls into exactly one of the two cases, so the two counts add to the original total.

Each edge e = \{u, v\} of G has exactly two endpoints, u and v (a loop at v is the case u = v, still contributing two to that one vertex's degree count, which is exactly why a loop is defined to add 2 to \deg(v) rather than 1). Build the sum \sum_{v\in V}\deg(v) by counting, for every edge, how many times that edge gets counted across the whole sum.

Fix one edge e=\{u,v\}. It is counted once when computing \deg(u) (since e is incident to u) and once more when computing \deg(v) (since e is also incident to v), and it is never counted in any other vertex's degree, since e touches no vertex besides u and v. So every edge contributes exactly 2 to the total \sum_{v\in V}\deg(v), and there are |E| edges, giving \sum_{v \in V} \deg(v) = \sum_{e \in E} 2 = 2|E|.

The odd-degree count is even. Split V into V_{\text{even}} (even degree) and V_{\text{odd}} (odd degree). Then \sum_{v \in V_{\text{even}}} \deg(v) + \sum_{v \in V_{\text{odd}}} \deg(v) = 2|E|, an even number. The first sum is a sum of even numbers, so it's even. Subtracting an even number from an even number leaves an even number, so \sum_{v \in V_{\text{odd}}} \deg(v) is even too. A sum of odd numbers is even only when there is an even count of them (an odd count of odd numbers always sums to something odd), so |V_{\text{odd}}| itself must be even.

Sanity check: a triangle (3 vertices, each of degree 2) has degree sum 2+2+2=6, and 2|E| = 2(3) = 6 -- matches, and 0 vertices have odd degree, which is indeed even.

Induct on n. A tree with n = 1 vertex has no edges at all, and n - 1 = 0, so the base case holds.

Assume every tree on k vertices has exactly k - 1 edges, for some k \geq 1. Let T be a tree on k + 1 vertices. Every tree with more than one vertex has at least one leaf (a vertex of degree 1) — following any path outward without repeating a vertex must eventually stop somewhere, since T is finite and acyclic, and it can only stop at a vertex with no unused edge left, degree 1. Remove that leaf v and its single incident edge. What remains is still connected (no other vertex's connections ran through v, since v had only one edge) and still acyclic (deleting a vertex can't create a cycle), so it is a tree on k vertices. By the inductive hypothesis it has k - 1 edges. Adding v's one edge back gives T exactly (k - 1) + 1 = k edges, which is (k+1) - 1, as required.

By induction, every tree on n vertices has n - 1 edges for all n \geq 1.

Induct on n. The base case n=1 gives 1 = \frac{1\cdot2\cdot3}{6}, true. Assume the formula holds for n=k. Then \sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\left[\frac{k(2k+1)}{6}+(k+1)\right] = (k+1)\cdot\frac{2k^2+7k+6}{6} = \frac{(k+1)(k+2)(2k+3)}{6}, which is the formula at n=k+1. By induction the formula holds for every n \geq 1.

Start from n!, the count if every one of the n objects were secretly distinct (as if each carried its own invisible label). Within that count, every group of n_1 identical objects can be relabeled among themselves in n_1! ways without changing the arrangement anyone can actually see — so n! overcounts the first repeated group by a factor of n_1!. The same overcounting happens independently for the second group (factor n_2!), the third, and so on. Dividing n! by n_1!\, n_2! \cdots n_k! removes every one of those redundant relabelings at once, since the groups' internal shufflings are independent of each other.

Line the n items up in a row first: there are n! such arrangements. Bending any one row into a circle produces exactly n different rows that land on the same circular arrangement — one for each rotation of which item is "first." So every circular arrangement is counted n times among the n! linear ones, and dividing removes the overcount: \frac{n!}{n} = (n-1)!. Equivalently: fix one item's seat to remove rotational symmetry, then arrange the other n-1 items in the remaining seats in any order.

Represent the n items as n stars in a row. Splitting them into k bins is the same as choosing where to place k-1 dividing bars among the stars — everything before the first bar goes in bin 1, everything between the first and second bar goes in bin 2, and so on. The row now has n stars and k-1 bars, n+k-1 symbols in total, and a distribution is completely determined by which k-1 of those n+k-1 positions hold bars. That is exactly \binom{n+k-1}{k-1} choices.

The substitution y_i = x_i - m_i is a bijection between solutions with x_i \geq m_i and solutions with y_i \geq 0: adding m_i back to each y_i recovers a unique x_i, and every valid x_i \geq m_i comes from exactly one y_i \geq 0. Summing the shifted equation confirms the new total is n - \sum m_i, so the shifted count is the ordinary stars-and-bars count applied to that smaller total.

Picture n as a row of n dots with n-1 gaps between consecutive dots. A composition of n corresponds exactly to a choice of which gaps become dividers, splitting the row into parts — insert a divider or don't, independently, at each of the n-1 gaps. By the product rule there are 2^{n-1} such choices, and each yields a distinct ordered sequence of positive part sizes summing to n.

Every such path is a sequence of m+n steps, each either right (R) or up (U), containing exactly m R's and n U's. A path is completely determined by choosing which m of the m+n step positions are R's — the rest are forced to be U's. That is exactly \binom{m+n}{m} choices.

Every unrestricted monotone path from (0,0) to (n,n) that crosses above the diagonal touches the line y=x+1 at some first step. Reflecting the portion of the path up to that first touch across y=x+1 gives a bijection between paths that cross the diagonal and unrestricted monotone paths from (-1,1) to (n,n), of which there are \binom{2n}{n-1}. Subtracting the crossing paths from all \binom{2n}{n} paths gives C_n = \binom{2n}{n} - \binom{2n}{n-1} = \binom{2n}{n}\left(1-\frac{n}{n+1}\right) = \frac{1}{n+1}\binom{2n}{n}.

Count the size-k subsets of an n-element set \{1, 2, \ldots, n\} two ways. The left side, \binom{n}{k}, counts them directly. For the right side, split every size-k subset by whether it contains the element n or not — an exhaustive, non-overlapping split. A subset containing n is n together with a size-(k-1) subset of the remaining n-1 elements: \binom{n-1}{k-1} such subsets. A subset not containing n is a size-k subset chosen entirely from those same n-1 elements: \binom{n-1}{k} of those. Every size-k subset falls into exactly one of the two cases, so the two counts add to the original total.

Row 1 of Pascal's triangle already matches the claim: (a+b)^1 = a+b = \binom{1}{0}a + \binom{1}{1}b.

Suppose the formula holds for some row n: (a+b)^n = \sum_{k=0}^n \binom{n}{k}a^{n-k}b^k. Multiply both sides by (a+b): (a+b)^{n+1} = \sum_{k=0}^n \binom{n}{k}a^{n+1-k}b^k \ + \ \sum_{k=0}^n \binom{n}{k}a^{n-k}b^{k+1}. Reindex the second sum by k \to k-1 and combine it with the first: the coefficient of a^{n+1-k}b^k in the total is \binom{n}{k}+\binom{n}{k-1}, which is exactly \binom{n+1}{k} by the same row-building identity that produces Pascal's triangle. So (a+b)^{n+1} = \sum_{k=0}^{n+1}\binom{n+1}{k}a^{n+1-k}b^k, the identical formula one row later. That row-to-row step is precisely how each row of Pascal's triangle is generated from the one above it, so the formula holds for every row, starting from row 1.

Count the size-r subsets of a set split into a group of m elements and a separate group of n elements, m+n elements total, two ways. The left side counts them directly, ignoring the split. For the right side, every size-r subset chooses some k elements from the m-group and the remaining r-k from the n-group, for some value of k between 0 and r; for each fixed k there are \binom{m}{k}\binom{n}{r-k} such subsets. Summing over every possible k covers every size-r subset exactly once, matching the left side.

Count the size-(k+1) subsets of \{1, 2, \ldots, n+1\} two ways. The right side counts them directly. For the left side, split every such subset by its largest element, some value i+1 with i ranging from k to n (the largest element must be at least k+1, since k smaller elements are still needed below it). Once the largest element is fixed at i+1, the remaining k elements are any size-k subset of \{1,\ldots,i\}: \binom{i}{k} choices. Every size-(k+1) subset has exactly one largest element, so summing \binom{i}{k} over every valid i counts each subset exactly once.

Count the ways to choose a size-k committee from n people and then designate one committee member as chair, two ways. The left side first chooses the committee (\binom{n}{k} ways) and then the chair from within it (k ways). The right side first chooses the chair directly (n ways) and then fills the remaining k-1 committee seats from the other n-1 people (\binom{n-1}{k-1} ways). Both procedures build the exact same object, a committee with one member marked as chair, so the two counts agree.

Choose the first group of k_1 items from all n: \binom{n}{k_1} ways. From the n - k_1 that remain, choose the second group of k_2: \binom{n-k_1}{k_2} ways. Continue until every item is placed. By the product rule, the total count is \binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\cdots = \frac{n!}{k_1!(n-k_1)!}\cdot\frac{(n-k_1)!}{k_2!(n-k_1-k_2)!}\cdots. Every factorial in a denominator cancels the matching factorial in the next numerator except the very last, leaving \dfrac{n!}{k_1!\,k_2!\,\cdots\,k_m!}. Setting m=2 recovers the ordinary binomial coefficient \binom{n}{k_1,\,n-k_1} = \binom{n}{k_1}.

Expanding (x_1+\cdots+x_m)^n as n copies of (x_1+\cdots+x_m) multiplied together, every term in the expansion picks one variable from each of the n factors and multiplies the n picks together. A term equal to x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m} arises from every way of assigning which k_1 of the n factors contributed an x_1, which k_2 contributed an x_2, and so on — exactly the multinomial coefficient \binom{n}{k_1,\ldots,k_m} of ways to split n labeled factors into labeled groups of those sizes. Summing over every valid (k_1,\ldots,k_m) accounts for every term the expansion produces.

Adding |A| and |B| counts every element of A \cup B at least once, but any element lying in both sets gets counted twice -- once inside |A| and once inside |B|. Subtracting |A \cap B| removes exactly one of those two duplicate counts for each such element, leaving every element of A \cup B counted exactly once. Formally, A \cup B splits into the three disjoint pieces A \setminus B, A \cap B, and B \setminus A, so |A \cup B| = |A \setminus B| + |A \cap B| + |B \setminus A|. Since |A| = |A \setminus B| + |A \cap B| and |B| = |B \setminus A| + |A \cap B|, adding |A|+|B| double-counts |A \cap B| by exactly one extra copy, which the subtraction removes.

Add |A|+|B|+|C|. An element in exactly one of the three sets is counted once, correct. An element in exactly two sets, say A and B only, is counted twice, once in |A| and once in |B|, so it needs one copy removed. Subtracting the three pairwise intersections removes one copy from every element in at least two sets, but an element in all three sets sits inside all three pairwise intersections at once, so those three subtractions strip it from three counts down to zero, one copy too many. Adding back |A\cap B\cap C| restores that element to being counted exactly once, while an element in only one or two sets is untouched by this last term since it isn't in the triple overlap.

Fix an element x that lies in exactly k\ge 1 of the sets, say A_{i_1},\ldots,A_{i_k}. On the right side, x is counted once for every subset S of \{i_1,\ldots,i_k\} with sign (-1)^{|S|+1}, since x \in \bigcap_{i\in S}A_i exactly when S is drawn entirely from those k indices. The number of size-j subsets of a k-element set is \binom{k}{j}, so x's total contribution to the right side is \sum_{j=1}^k (-1)^{j+1}\binom{k}{j}. The binomial theorem gives \sum_{j=0}^k (-1)^j \binom{k}{j} = (1-1)^k = 0, so \sum_{j=1}^k (-1)^{j+1}\binom{k}{j} = -\left(\sum_{j=1}^k (-1)^j\binom{k}{j}\right) = -(0 - \binom{k}{0}) = 1. Every element that lies in at least one set contributes exactly 1 to the right side, matching its single contribution to the left side; an element in none of the sets contributes 0 to both.

Let A_i be the set of permutations of \{1,\ldots,n\} that fix position i (send i to itself). A derangement is a permutation in none of the A_i, so D_n = n! - \left|\bigcup_{i=1}^n A_i\right|. Fixing any particular k positions and permuting the rest freely gives (n-k)! permutations in a k-fold intersection A_{i_1}\cap\cdots\cap A_{i_k}, and there are \binom{n}{k} ways to choose which k positions to fix. By the general inclusion-exclusion formula, \left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k+1}\binom{n}{k}(n-k)! Substituting \binom{n}{k}(n-k)! = \frac{n!}{k!} and simplifying, D_n = n! - \sum_{k=1}^n (-1)^{k+1}\frac{n!}{k!} = n! + \sum_{k=1}^n (-1)^{k}\frac{n!}{k!} = n!\sum_{k=0}^n \frac{(-1)^k}{k!} since the k=0 term of the last sum is n!.

There are m^n total functions from the n-set to the m-set. Let A_j be the set of functions that miss target element j (never map anything to j). A function is surjective exactly when it lies in none of A_1,\ldots,A_m, so the count is m^n - \left|\bigcup_{j=1}^m A_j\right|. Fixing any i target elements to be missed leaves m-i allowed targets for every one of the n inputs, so a i-fold intersection has (m-i)^n functions, and there are \binom{m}{i} ways to choose which i targets to miss. The general inclusion-exclusion formula gives \left|\bigcup_{j=1}^m A_j\right| = \sum_{i=1}^m (-1)^{i+1}\binom{m}{i}(m-i)^n, so the surjection count is m^n - \sum_{i=1}^m (-1)^{i+1}\binom{m}{i}(m-i)^n = \sum_{i=0}^m (-1)^i\binom{m}{i}(m-i)^n, since the i=0 term of the final sum is exactly m^n.

Let A_i be the set of integers in \{1,\ldots,n\} divisible by p_i. An integer coprime to n is one divisible by none of the primes p_1,\ldots,p_k, so \varphi(n) = n - \left|\bigcup_{i=1}^k A_i\right|. Exactly n/p_i integers in the range are divisible by p_i, and for any subset of primes p_{i_1},\ldots,p_{i_j}, exactly n/(p_{i_1}\cdots p_{i_j}) integers are divisible by all of them (since the primes are distinct, divisibility by all is divisibility by their product). The general inclusion-exclusion formula turns \left|\bigcup_i A_i\right| into an alternating sum over subsets of primes, which factors as n - \left|\bigcup_{i=1}^k A_i\right| = n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right) because expanding the product on the right generates exactly one term \pm n/(p_{i_1}\cdots p_{i_j}) per subset, with the sign matching the inclusion-exclusion alternation.

There are m^n total functions from the n-set to the m-set. Let A_j be the set of functions that miss target element j (never map anything to j). A function is surjective exactly when it lies in none of A_1,\ldots,A_m, so the count is m^n - \left|\bigcup_{j=1}^m A_j\right|. Fixing any i target elements to be missed leaves m-i allowed targets for every one of the n inputs, so a i-fold intersection has (m-i)^n functions, and there are \binom{m}{i} ways to choose which i targets to miss. The general inclusion-exclusion formula gives \left|\bigcup_{j=1}^m A_j\right| = \sum_{i=1}^m (-1)^{i+1}\binom{m}{i}(m-i)^n, so the surjection count is m^n - \sum_{i=1}^m (-1)^{i+1}\binom{m}{i}(m-i)^n = \sum_{i=0}^m (-1)^i\binom{m}{i}(m-i)^n, since the i=0 term of the final sum is exactly m^n.

Every partition of \{1,\ldots,n\} into k nonempty blocks treats element n in exactly one of two ways, and the two cases are disjoint.

Case 1: element n is a block all by itself. Deleting that singleton block leaves a partition of \{1,\ldots,n-1\} into k-1 nonempty blocks, and every such partition arises from exactly one partition of this case (re-attach the singleton \{n\}). This case therefore contributes S(n-1,k-1).

Case 2: element n shares its block with at least one other element. Deleting n from its block leaves that block nonempty, so what remains is a partition of \{1,\ldots,n-1\} into k nonempty blocks. Each such partition is reached from exactly k partitions of this case, one for each of its k blocks that n could have been sitting in. This case therefore contributes k\,S(n-1,k).

The two cases together cover every partition exactly once, so S(n,k) = k\,S(n-1,k) + S(n-1,k-1). The base cases hold because the empty set has exactly one partition into zero blocks, a nonempty set has none, and no partition of the empty set uses a nonempty block.

Let f be a surjection from an n-set A onto an m-set B. The fibers f^{-1}(b) for b\in B are pairwise disjoint, cover A, and are all nonempty precisely because f is onto — so they form a partition of A into exactly m nonempty blocks. Conversely, start from any partition of A into m nonempty blocks and any bijection from its blocks to B; sending each element to the label of its block defines a surjection onto B. These two constructions invert each other: a surjection recovers its own fiber partition together with the labeling "block f^{-1}(b) maps to b," and distinct (partition, labeling) pairs give distinct surjections. There are S(n,m) choices of partition and, independently, m! bijections from its m blocks to B, so the product rule gives \operatorname{Surj}(n,m) = m!\,S(n,m).

Classify the partitions of \{1,\ldots,n+1\} by the block containing the element n+1. Suppose that block consists of n+1 together with some set T of other elements, and let k = n - |T| be the number of elements left outside the block. Choosing which k of the n elements 1,\ldots,n stay outside determines T as the complement, and there are \binom{n}{k} such choices (equivalently \binom{n}{n-k}=\binom{n}{k} choices of T itself). The elements outside the block of n+1 can then be partitioned among themselves in any way whatsoever, in B_k ways, and this choice is independent of the choice of T. Every partition of \{1,\ldots,n+1\} arises from exactly one pair (choice of T, partition of the outside), since the partition itself determines the block of n+1 and hence both components. Summing the product \binom{n}{k} B_k over the possible values k = 0, 1, \ldots, n counts each partition exactly once, so B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k. The base case B_0=1 counts the empty partition of the empty set.

Every a\in A satisfies a\sim a by reflexivity, so a\in[a] and the classes cover A. Suppose two classes [a] and [b] share an element c, so c\sim a and c\sim b. By symmetry a\sim c, and by transitivity a\sim c and c\sim b give a\sim b. Then for any x\in[a], x\sim a and a\sim b give x\sim b, so x\in[b], and the same argument in reverse gives [b]\subseteq[a]. Hence [a]=[b]: two classes that share even one element are the same class, so distinct classes never overlap. Combined with the classes covering A, this makes the collection of distinct classes a partition of A.

Count the size-k subsets of an n-element set \{1, 2, \ldots, n\} two ways. The left side, \binom{n}{k}, counts them directly. For the right side, split every size-k subset by whether it contains the element n or not — an exhaustive, non-overlapping split. A subset containing n is n together with a size-(k-1) subset of the remaining n-1 elements: \binom{n-1}{k-1} such subsets. A subset not containing n is a size-k subset chosen entirely from those same n-1 elements: \binom{n-1}{k} of those. Every size-k subset falls into exactly one of the two cases, so the two counts add to the original total.

Count the size-(k+1) subsets of \{1, 2, \ldots, n+1\} two ways. The right side counts them directly. For the left side, split every such subset by its largest element, some value i+1 with i ranging from k to n (the largest element must be at least k+1, since k smaller elements are still needed below it). Once the largest element is fixed at i+1, the remaining k elements are any size-k subset of \{1,\ldots,i\}: \binom{i}{k} choices. Every size-(k+1) subset has exactly one largest element, so summing \binom{i}{k} over every valid i counts each subset exactly once.

Count the size-r subsets of a set split into a group of m elements and a separate group of n elements, m+n elements total, two ways. The left side counts them directly, ignoring the split. For the right side, every size-r subset chooses some k elements from the m-group and the remaining r-k from the n-group, for some value of k between 0 and r; for each fixed k there are \binom{m}{k}\binom{n}{r-k} such subsets. Summing over every possible k covers every size-r subset exactly once, matching the left side.

Unroll the recurrence one step at a time. Substituting the recurrence into itself, a_n = c\,a_{n-1} + d = c(c\,a_{n-2} + d) + d = c^2 a_{n-2} + cd + d, and after k substitutions a_n = c^k a_{n-k} + d\left(c^{k-1} + c^{k-2} + \cdots + c + 1\right). (Formally this is an induction on k: the case k=1 is the recurrence itself, and applying the recurrence to a_{n-k} extends the pattern from k to k+1.) Taking k = n reaches the initial term: a_n = c^n a_0 + d\sum_{i=0}^{n-1} c^i. Since c \neq 1, the finite geometric sum evaluates to \sum_{i=0}^{n-1} c^i = \frac{c^n - 1}{c - 1}, giving a_n = c^n a_0 + d\,\frac{c^n - 1}{c - 1}. When n = 0 both sides equal a_0, so the formula holds for all n \ge 0.

The form solves the recurrence. Substitute a_n = c_1 r_1^n + c_2 r_2^n into the right side of A a_{n-1} + B a_{n-2}: A\left(c_1 r_1^{n-1} + c_2 r_2^{n-1}\right) + B\left(c_1 r_1^{n-2} + c_2 r_2^{n-2}\right) = c_1 r_1^{n-2}\left(Ar_1 + B\right) + c_2 r_2^{n-2}\left(Ar_2 + B\right). Since each r_i satisfies r_i^2 = Ar_i + B (that is exactly what being a root of x^2 - Ax - B = 0 means), Ar_i + B = r_i^2, so the right side becomes c_1 r_1^{\,n} + c_2 r_2^{\,n} = a_n. The proposed form satisfies the recurrence for every choice of c_1, c_2, regardless of the initial conditions.

The constants are pinned down uniquely. Requiring a_0 and a_1 to match the given starting values produces the linear system c_1 + c_2 = a_0, \qquad c_1 r_1 + c_2 r_2 = a_1. This system has exactly one solution for (c_1, c_2) whenever r_1 \neq r_2, since its determinant r_2 - r_1 is then nonzero. Combined with the first part, this shows the resulting a_n is not merely a solution matching the initial conditions — it is the only one, because any sequence satisfying a second-order recurrence is completely determined once a_0 and a_1 are fixed.

Sanity check: take a_n = 3a_{n-1} - 2a_{n-2} with a_0 = 2, a_1 = 3. The characteristic equation x^2 - 3x + 2 = 0 factors as (x-1)(x-2)=0, giving roots r_1=1, r_2=2. Solving c_1+c_2=2, c_1+2c_2=3 gives c_1=1, c_2=1, so a_n = 1 + 2^n. Checking directly: a_2 should be 3(3)-2(2)=5, and the formula gives 1+2^2=5. They agree.

Since (x-r)^2 = x^2 - 2rx + r^2, matching coefficients gives s = 2r and t = -r^2, so the recurrence reads a_n = 2r\,a_{n-1} - r^2 a_{n-2}.

First, a_n = r^n is a solution, since r satisfies the characteristic equation: 2r\cdot r^{n-1} - r^2\cdot r^{n-2} = 2r^n - r^n = r^n.

Second, a_n = n\,r^n is also a solution. Substituting, 2r\,(n-1)r^{n-1} - r^2\,(n-2)r^{n-2} = r^n\big(2(n-1) - (n-2)\big) = r^n\,n = n\,r^n. Because the recurrence is linear and homogeneous, every combination a_n = (A + Bn)r^n = A\,r^n + B\,n r^n is therefore a solution.

Finally, this family covers every solution: a second-order linear recurrence is determined by its two initial values, and for any given a_0, a_1 the system A = a_0, (A + B)r = a_1 has the unique solution A = a_0, B = a_1/r - a_0 (using r \neq 0). So each pair of initial conditions is matched by exactly one choice of A and B, and (A + Bn)r^n is the general solution.

Unroll the recurrence as a recursion tree. Level i (with the root at level 0) contains a^i subproblems, each of size n/b^i, so with f(n) = \Theta(n^d) the total work at level i is a^i \cdot \Theta\!\left(\left(\frac{n}{b^i}\right)^{d}\right) = \Theta\!\left(n^d\left(\frac{a}{b^d}\right)^{i}\right) The tree has \log_b n levels below the root, so summing over levels gives a geometric series with ratio r = a/b^d: T(n) = \Theta\!\left(n^d \sum_{i=0}^{\log_b n} r^{i}\right) Note that r < 1 \iff d > \log_b a, r = 1 \iff d = \log_b a, and r > 1 \iff d < \log_b a, since \log_b r = \log_b a - d.

Case r < 1 (root dominates). The series is bounded by the convergent geometric series \sum_{i \ge 0} r^i = \frac{1}{1-r}, a constant, so the sum is \Theta(1) and T(n) = \Theta(n^d): the root term alone already gives the lower bound, and the constant caps the rest.

Case r = 1 (balanced). Every one of the 1 + \log_b n levels contributes exactly \Theta(n^d), so T(n) = \Theta(n^d \log_b n) = \Theta(n^d \log n), the base of the logarithm being absorbed into the constant.

Case r > 1 (leaves dominate). A geometric series with ratio r > 1 is dominated by its last term: \sum_{i=0}^{L} r^i = \frac{r^{L+1}-1}{r-1} = \Theta(r^L) with L = \log_b n. Then n^d\, r^{\log_b n} = n^d \cdot n^{\log_b r} = n^{d + \log_b a - d} = n^{\log_b a} so T(n) = \Theta\!\left(n^{\log_b a}\right) — exactly the number of leaves, a^{\log_b n} = n^{\log_b a}, each doing constant work.

Unroll the recurrence as a recursion tree. Level i (with the root at level 0) contains a^i subproblems, each of size n/b^i, so with f(n) = \Theta(n^d) the total work at level i is a^i \cdot \Theta\!\left(\left(\frac{n}{b^i}\right)^{d}\right) = \Theta\!\left(n^d\left(\frac{a}{b^d}\right)^{i}\right) The tree has \log_b n levels below the root, so summing over levels gives a geometric series with ratio r = a/b^d: T(n) = \Theta\!\left(n^d \sum_{i=0}^{\log_b n} r^{i}\right) Note that r < 1 \iff d > \log_b a, r = 1 \iff d = \log_b a, and r > 1 \iff d < \log_b a, since \log_b r = \log_b a - d.

Case r < 1 (root dominates). The series is bounded by the convergent geometric series \sum_{i \ge 0} r^i = \frac{1}{1-r}, a constant, so the sum is \Theta(1) and T(n) = \Theta(n^d): the root term alone already gives the lower bound, and the constant caps the rest.

Case r = 1 (balanced). Every one of the 1 + \log_b n levels contributes exactly \Theta(n^d), so T(n) = \Theta(n^d \log_b n) = \Theta(n^d \log n), the base of the logarithm being absorbed into the constant.

Case r > 1 (leaves dominate). A geometric series with ratio r > 1 is dominated by its last term: \sum_{i=0}^{L} r^i = \frac{r^{L+1}-1}{r-1} = \Theta(r^L) with L = \log_b n. Then n^d\, r^{\log_b n} = n^d \cdot n^{\log_b r} = n^{d + \log_b a - d} = n^{\log_b a} so T(n) = \Theta\!\left(n^{\log_b a}\right) — exactly the number of leaves, a^{\log_b n} = n^{\log_b a}, each doing constant work.

Unroll the recurrence as a recursion tree. Level i (with the root at level 0) contains a^i subproblems, each of size n/b^i, so with f(n) = \Theta(n^d) the total work at level i is a^i \cdot \Theta\!\left(\left(\frac{n}{b^i}\right)^{d}\right) = \Theta\!\left(n^d\left(\frac{a}{b^d}\right)^{i}\right) The tree has \log_b n levels below the root, so summing over levels gives a geometric series with ratio r = a/b^d: T(n) = \Theta\!\left(n^d \sum_{i=0}^{\log_b n} r^{i}\right) Note that r < 1 \iff d > \log_b a, r = 1 \iff d = \log_b a, and r > 1 \iff d < \log_b a, since \log_b r = \log_b a - d.

Case r < 1 (root dominates). The series is bounded by the convergent geometric series \sum_{i \ge 0} r^i = \frac{1}{1-r}, a constant, so the sum is \Theta(1) and T(n) = \Theta(n^d): the root term alone already gives the lower bound, and the constant caps the rest.

Case r = 1 (balanced). Every one of the 1 + \log_b n levels contributes exactly \Theta(n^d), so T(n) = \Theta(n^d \log_b n) = \Theta(n^d \log n), the base of the logarithm being absorbed into the constant.

Case r > 1 (leaves dominate). A geometric series with ratio r > 1 is dominated by its last term: \sum_{i=0}^{L} r^i = \frac{r^{L+1}-1}{r-1} = \Theta(r^L) with L = \log_b n. Then n^d\, r^{\log_b n} = n^d \cdot n^{\log_b r} = n^{d + \log_b a - d} = n^{\log_b a} so T(n) = \Theta\!\left(n^{\log_b a}\right) — exactly the number of leaves, a^{\log_b n} = n^{\log_b a}, each doing constant work.

Unroll the recurrence as a recursion tree. Level i (with the root at level 0) contains a^i subproblems, each of size n/b^i, so with f(n) = \Theta(n^d) the total work at level i is a^i \cdot \Theta\!\left(\left(\frac{n}{b^i}\right)^{d}\right) = \Theta\!\left(n^d\left(\frac{a}{b^d}\right)^{i}\right) The tree has \log_b n levels below the root, so summing over levels gives a geometric series with ratio r = a/b^d: T(n) = \Theta\!\left(n^d \sum_{i=0}^{\log_b n} r^{i}\right) Note that r < 1 \iff d > \log_b a, r = 1 \iff d = \log_b a, and r > 1 \iff d < \log_b a, since \log_b r = \log_b a - d.

Case r < 1 (root dominates). The series is bounded by the convergent geometric series \sum_{i \ge 0} r^i = \frac{1}{1-r}, a constant, so the sum is \Theta(1) and T(n) = \Theta(n^d): the root term alone already gives the lower bound, and the constant caps the rest.

Case r = 1 (balanced). Every one of the 1 + \log_b n levels contributes exactly \Theta(n^d), so T(n) = \Theta(n^d \log_b n) = \Theta(n^d \log n), the base of the logarithm being absorbed into the constant.

Case r > 1 (leaves dominate). A geometric series with ratio r > 1 is dominated by its last term: \sum_{i=0}^{L} r^i = \frac{r^{L+1}-1}{r-1} = \Theta(r^L) with L = \log_b n. Then n^d\, r^{\log_b n} = n^d \cdot n^{\log_b r} = n^{d + \log_b a - d} = n^{\log_b a} so T(n) = \Theta\!\left(n^{\log_b a}\right) — exactly the number of leaves, a^{\log_b n} = n^{\log_b a}, each doing constant work.

Unroll the recurrence as a recursion tree. Level i (with the root at level 0) contains a^i subproblems, each of size n/b^i, so with f(n) = \Theta(n^d) the total work at level i is a^i \cdot \Theta\!\left(\left(\frac{n}{b^i}\right)^{d}\right) = \Theta\!\left(n^d\left(\frac{a}{b^d}\right)^{i}\right) The tree has \log_b n levels below the root, so summing over levels gives a geometric series with ratio r = a/b^d: T(n) = \Theta\!\left(n^d \sum_{i=0}^{\log_b n} r^{i}\right) Note that r < 1 \iff d > \log_b a, r = 1 \iff d = \log_b a, and r > 1 \iff d < \log_b a, since \log_b r = \log_b a - d.

Case r < 1 (root dominates). The series is bounded by the convergent geometric series \sum_{i \ge 0} r^i = \frac{1}{1-r}, a constant, so the sum is \Theta(1) and T(n) = \Theta(n^d): the root term alone already gives the lower bound, and the constant caps the rest.

Case r = 1 (balanced). Every one of the 1 + \log_b n levels contributes exactly \Theta(n^d), so T(n) = \Theta(n^d \log_b n) = \Theta(n^d \log n), the base of the logarithm being absorbed into the constant.

Case r > 1 (leaves dominate). A geometric series with ratio r > 1 is dominated by its last term: \sum_{i=0}^{L} r^i = \frac{r^{L+1}-1}{r-1} = \Theta(r^L) with L = \log_b n. Then n^d\, r^{\log_b n} = n^d \cdot n^{\log_b r} = n^{d + \log_b a - d} = n^{\log_b a} so T(n) = \Theta\!\left(n^{\log_b a}\right) — exactly the number of leaves, a^{\log_b n} = n^{\log_b a}, each doing constant work.

All four rules are proved the same way: expand each side as a formal power series and compare the coefficient of x^n.

Scalar multiple. cA(x) = c\sum_n a_n x^n = \sum_n (c\,a_n)x^n, so the coefficient of x^n in cA(x) is c\,a_n.

Sum. A(x)+B(x) = \sum_n a_n x^n + \sum_n b_n x^n = \sum_n (a_n+b_n)x^n, since like powers of x collect together. The coefficient of x^n is a_n+b_n.

Shift. xA(x) = \sum_n a_n x^{n+1} = \sum_{m\ge 1} a_{m-1} x^m after re-indexing with m=n+1. The coefficient of x^0 is 0 and the coefficient of x^m for m\ge 1 is a_{m-1} — exactly the sequence (0, a_0, a_1, \ldots).

Product. Multiplying the two series and collecting the terms whose exponents sum to n, A(x)B(x) = \sum_{i\ge 0}\sum_{j\ge 0} a_i b_j\, x^{i+j} = \sum_{n\ge 0}\left(\sum_{i=0}^{n} a_i\, b_{n-i}\right) x^n, because a term contributes to x^n exactly when j = n-i with 0 \le i \le n. The coefficient of x^n is the convolution \sum_{i=0}^n a_i b_{n-i}. Each inner sum is finite, so the product is well-defined as a formal power series with no convergence assumption.

Let F(x)=\sum_{n\ge 0}F_n x^n. Multiply the recurrence F_n = F_{n-1}+F_{n-2} by x^n and sum over every n\ge 2 where it holds: \sum_{n\ge 2} F_n x^n \;=\; \sum_{n\ge 2} F_{n-1}x^n \;+\; \sum_{n\ge 2} F_{n-2}x^n. Each sum is a piece of F(x). The left side is F(x) minus its first two terms: F(x) - F_0 - F_1 x = F(x) - x. Re-indexing the first sum on the right with m = n-1 gives \sum_{m\ge 1} F_m x^{m+1} = x\bigl(F(x)-F_0\bigr) = xF(x), and re-indexing the second with m=n-2 gives \sum_{m\ge 0} F_m x^{m+2} = x^2 F(x). So F(x) - x = xF(x) + x^2F(x). Collecting every F(x) term on the left, F(x)\left(1 - x - x^2\right) = x, and dividing by the formal power series 1-x-x^2 (invertible since its constant term is nonzero) gives F(x) = \frac{x}{1-x-x^2}. Factoring 1-x-x^2 = (1-\varphi x)(1-\psi x) with \varphi = \frac{1+\sqrt5}{2} and \psi = \frac{1-\sqrt5}{2}, partial fractions split F(x) into two geometric series and reading off the coefficient of x^n recovers Binet's formula F_n = \frac{\varphi^n - \psi^n}{\sqrt5}.

Picture n as a row of n dots with n-1 gaps between consecutive dots. A composition of n corresponds exactly to a choice of which gaps become dividers, splitting the row into parts — insert a divider or don't, independently, at each of the n-1 gaps. By the product rule there are 2^{n-1} such choices, and each yields a distinct ordered sequence of positive part sizes summing to n.

Picture n as a row of n dots with n-1 gaps between consecutive dots. A composition of n corresponds exactly to a choice of which gaps become dividers, splitting the row into parts — insert a divider or don't, independently, at each of the n-1 gaps. By the product rule there are 2^{n-1} such choices, and each yields a distinct ordered sequence of positive part sizes summing to n.

Draw a partition \lambda = (\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_r) of n as a Ferrers diagram: row i contains \lambda_i left-justified dots. Its conjugate \lambda' is the partition read off the columns: \lambda'_j is the number of rows with at least j dots. Since \lambda_1 \ge \lambda_2 \ge \cdots, the column lengths \lambda'_1 \ge \lambda'_2 \ge \cdots are also weakly decreasing, so \lambda' is a genuine partition, and it has the same total n because conjugation merely re-reads the same set of dots by columns instead of rows. Conjugation is an involution — reflecting the diagram across its main diagonal twice returns the original diagram, so (\lambda')' = \lambda — and hence a bijection from partitions of n to partitions of n.

Under this bijection the two restrictions trade places: \lambda has at most k parts exactly when its diagram has at most k rows, which happens exactly when every column of the diagram has length at most k, i.e. exactly when every part of \lambda' is at most k. So conjugation restricts to a bijection between the two counted sets, and the counts are equal.

Expand each factor as a geometric series: \frac{1}{1-x^k} = 1 + x^k + x^{2k} + x^{3k} + \cdots, whose term x^{m_k \cdot k} records the choice "use the part k exactly m_k times." Multiplying the factors for k = 1, 2, 3, \ldots and expanding, each term of the product is formed by picking one term x^{m_k k} from each factor (all but finitely many picks being the constant 1), contributing x^{m_1 \cdot 1 + m_2 \cdot 2 + m_3 \cdot 3 + \cdots}. So a term contributes to the coefficient of x^n exactly when m_1 \cdot 1 + m_2 \cdot 2 + m_3 \cdot 3 + \cdots = n, i.e. exactly when the multiset with m_k copies of each part k is a partition of n. Distinct choices of the multiplicities (m_1, m_2, \ldots) give distinct partitions and conversely, so the coefficient of x^n counts partitions of n: it is p(n).

(For the formal-series bookkeeping: the coefficient of x^n only involves the factors with k \le n, a finite product, so every coefficient of the infinite product is a well-defined finite count.)

We exhibit inverse bijections between the two sets, built on the fact that every positive integer m factors uniquely as m = 2^a \cdot b with b odd.

Distinct \to odd (splitting). Given a partition of n into distinct parts, write each part as 2^a \cdot b with b odd, and replace it by 2^a copies of b. The total is unchanged, and every resulting part is odd.

Odd \to distinct (binary merging). Given a partition of n into odd parts, suppose the odd number b occurs m_b times. Write m_b in binary, m_b = 2^{a_1} + 2^{a_2} + \cdots with distinct exponents a_i, and replace the m_b copies of b by the parts 2^{a_1} b,\ 2^{a_2} b,\ \ldots The total contributed by b is still m_b \cdot b. The new parts are distinct: two parts 2^{a}b and 2^{a'}b' with b, b' odd are equal only if b = b' (the odd part of a factorization is unique) and a = a', but for a fixed b the exponents drawn from one binary expansion are distinct.

The maps are inverse. Splitting 2^{a}b into 2^a copies of b and then regrouping asks: how many copies of b arrived in total? It is \sum_i 2^{a_i}, summed over the distinct parts 2^{a_i} b that share odd part b — and since the a_i were distinct, this sum is the unique binary expansion of that multiplicity, so merging recovers exactly the original distinct parts. Conversely, merging then splitting returns each copy count m_b to its own copies of b by uniqueness of binary representation. Two mutually inverse maps make each map a bijection, so the two sets have the same size.

Draw a partition \lambda = (\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_r) of n as a Ferrers diagram: row i contains \lambda_i left-justified dots. Its conjugate \lambda' is the partition read off the columns: \lambda'_j is the number of rows with at least j dots. Since \lambda_1 \ge \lambda_2 \ge \cdots, the column lengths \lambda'_1 \ge \lambda'_2 \ge \cdots are also weakly decreasing, so \lambda' is a genuine partition, and it has the same total n because conjugation merely re-reads the same set of dots by columns instead of rows. Conjugation is an involution — reflecting the diagram across its main diagonal twice returns the original diagram, so (\lambda')' = \lambda — and hence a bijection from partitions of n to partitions of n.

Under this bijection the two restrictions trade places: \lambda has at most k parts exactly when its diagram has at most k rows, which happens exactly when every column of the diagram has length at most k, i.e. exactly when every part of \lambda' is at most k. So conjugation restricts to a bijection between the two counted sets, and the counts are equal.

Each edge e = \{u, v\} of G has exactly two endpoints, u and v (a loop at v is the case u = v, still contributing two to that one vertex's degree count, which is exactly why a loop is defined to add 2 to \deg(v) rather than 1). Build the sum \sum_{v\in V}\deg(v) by counting, for every edge, how many times that edge gets counted across the whole sum.

Fix one edge e=\{u,v\}. It is counted once when computing \deg(u) (since e is incident to u) and once more when computing \deg(v) (since e is also incident to v), and it is never counted in any other vertex's degree, since e touches no vertex besides u and v. So every edge contributes exactly 2 to the total \sum_{v\in V}\deg(v), and there are |E| edges, giving \sum_{v \in V} \deg(v) = \sum_{e \in E} 2 = 2|E|.

The odd-degree count is even. Split V into V_{\text{even}} (even degree) and V_{\text{odd}} (odd degree). Then \sum_{v \in V_{\text{even}}} \deg(v) + \sum_{v \in V_{\text{odd}}} \deg(v) = 2|E|, an even number. The first sum is a sum of even numbers, so it's even. Subtracting an even number from an even number leaves an even number, so \sum_{v \in V_{\text{odd}}} \deg(v) is even too. A sum of odd numbers is even only when there is an even count of them (an odd count of odd numbers always sums to something odd), so |V_{\text{odd}}| itself must be even.

Sanity check: a triangle (3 vertices, each of degree 2) has degree sum 2+2+2=6, and 2|E| = 2(3) = 6 -- matches, and 0 vertices have odd degree, which is indeed even.

Each edge e = \{u, v\} of G has exactly two endpoints, u and v (a loop at v is the case u = v, still contributing two to that one vertex's degree count, which is exactly why a loop is defined to add 2 to \deg(v) rather than 1). Build the sum \sum_{v\in V}\deg(v) by counting, for every edge, how many times that edge gets counted across the whole sum.

Fix one edge e=\{u,v\}. It is counted once when computing \deg(u) (since e is incident to u) and once more when computing \deg(v) (since e is also incident to v), and it is never counted in any other vertex's degree, since e touches no vertex besides u and v. So every edge contributes exactly 2 to the total \sum_{v\in V}\deg(v), and there are |E| edges, giving \sum_{v \in V} \deg(v) = \sum_{e \in E} 2 = 2|E|.

The odd-degree count is even. Split V into V_{\text{even}} (even degree) and V_{\text{odd}} (odd degree). Then \sum_{v \in V_{\text{even}}} \deg(v) + \sum_{v \in V_{\text{odd}}} \deg(v) = 2|E|, an even number. The first sum is a sum of even numbers, so it's even. Subtracting an even number from an even number leaves an even number, so \sum_{v \in V_{\text{odd}}} \deg(v) is even too. A sum of odd numbers is even only when there is an even count of them (an odd count of odd numbers always sums to something odd), so |V_{\text{odd}}| itself must be even.

Sanity check: a triangle (3 vertices, each of degree 2) has degree sum 2+2+2=6, and 2|E| = 2(3) = 6 -- matches, and 0 vertices have odd degree, which is indeed even.

Induct on n. A tree with n = 1 vertex has no edges at all, and n - 1 = 0, so the base case holds.

Assume every tree on k vertices has exactly k - 1 edges, for some k \geq 1. Let T be a tree on k + 1 vertices. Every tree with more than one vertex has at least one leaf (a vertex of degree 1) — following any path outward without repeating a vertex must eventually stop somewhere, since T is finite and acyclic, and it can only stop at a vertex with no unused edge left, degree 1. Remove that leaf v and its single incident edge. What remains is still connected (no other vertex's connections ran through v, since v had only one edge) and still acyclic (deleting a vertex can't create a cycle), so it is a tree on k vertices. By the inductive hypothesis it has k - 1 edges. Adding v's one edge back gives T exactly (k - 1) + 1 = k edges, which is (k+1) - 1, as required.

By induction, every tree on n vertices has n - 1 edges for all n \geq 1.

We sketch the Prüfer correspondence, a bijection between labeled trees on the vertex set \{1, \ldots, n\} and sequences of length n-2 whose entries come from \{1, \ldots, n\}. Since there are n^{n-2} such sequences, the bijection proves the count.

Tree to sequence. Given a tree T on \{1, \ldots, n\}, repeat the following step n-2 times: find the leaf with the smallest label, write down the label of its unique neighbor, and delete the leaf. The n-2 recorded neighbor labels, in order, form the Prüfer sequence of T. The process is deterministic, so each tree yields exactly one sequence.

Sequence to tree. Given a sequence (a_1, \ldots, a_{n-2}), the degree of each vertex v in the corresponding tree must be one plus the number of times v appears in the sequence: every non-leaf vertex is recorded once for each of its leaf-neighbors deleted while it remains, and once more when it is itself deleted or survives at the end. Rebuild the tree by reversing the deletions: at step i, join a_i to the smallest-labeled vertex that is not among a_i, a_{i+1}, \ldots, a_{n-2} and has not yet been used, then mark that vertex used. After n-2 joins, exactly two vertices remain unused; join them to each other. Each step is forced, so each sequence yields exactly one tree, and rebuilding the sequence's tree recovers the original sequence.

The two maps are mutually inverse, giving a bijection. Hence the number of labeled trees on n vertices equals the number of sequences of length n-2 over an alphabet of size n, which is n^{n-2}. Small cases confirm it: n = 3 gives 3^1 = 3 trees (the three paths on three labeled vertices), and n = 4 gives 4^2 = 16.

We sketch the Prüfer correspondence, a bijection between labeled trees on the vertex set \{1, \ldots, n\} and sequences of length n-2 whose entries come from \{1, \ldots, n\}. Since there are n^{n-2} such sequences, the bijection proves the count.

Tree to sequence. Given a tree T on \{1, \ldots, n\}, repeat the following step n-2 times: find the leaf with the smallest label, write down the label of its unique neighbor, and delete the leaf. The n-2 recorded neighbor labels, in order, form the Prüfer sequence of T. The process is deterministic, so each tree yields exactly one sequence.

Sequence to tree. Given a sequence (a_1, \ldots, a_{n-2}), the degree of each vertex v in the corresponding tree must be one plus the number of times v appears in the sequence: every non-leaf vertex is recorded once for each of its leaf-neighbors deleted while it remains, and once more when it is itself deleted or survives at the end. Rebuild the tree by reversing the deletions: at step i, join a_i to the smallest-labeled vertex that is not among a_i, a_{i+1}, \ldots, a_{n-2} and has not yet been used, then mark that vertex used. After n-2 joins, exactly two vertices remain unused; join them to each other. Each step is forced, so each sequence yields exactly one tree, and rebuilding the sequence's tree recovers the original sequence.

The two maps are mutually inverse, giving a bijection. Hence the number of labeled trees on n vertices equals the number of sequences of length n-2 over an alphabet of size n, which is n^{n-2}. Small cases confirm it: n = 3 gives 3^1 = 3 trees (the three paths on three labeled vertices), and n = 4 gives 4^2 = 16.

A full proof needs linear-algebra machinery beyond this course, so we state the structure honestly and verify a case rather than pretend to derive it. The standard argument writes L = M M^{\mathsf T}, where M is the incidence matrix of an arbitrary orientation of G, and applies the Cauchy-Binet formula to expand \det(L_{(i)}) as a sum of squared determinants of (n-1) \times (n-1) submatrices of M, one for each choice of n-1 edges. Each such determinant is \pm 1 when the chosen edges form a spanning tree and 0 when they contain a cycle, so the sum counts spanning trees exactly.

Verification on K_3: each vertex has degree 2, so L = \begin{pmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{pmatrix}, \qquad L_{(1)} = \begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}, and \det(L_{(1)}) = 4 - 1 = 3. The triangle indeed has exactly three spanning trees, one for each edge left out. Applying the theorem to K_n recovers Cayley's formula n^{n-2}, since every labeled tree on n vertices is a spanning tree of K_n.

Necessity. Suppose a matching M saturates L, and let S \subseteq L be any subset. Each vertex of S is matched by M to its own vertex of R, and these matched partners are distinct because no two edges of a matching share an endpoint. Every matched partner of a vertex in S is, in particular, a neighbor of that vertex, so all |S| of them lie in N(S). Hence |N(S)| \ge |S|. Equivalently: if some set S has |N(S)| < |S|, the |S| vertices of S would need distinct partners drawn from fewer than |S| available neighbors, which is impossible — the deficiency |S| - |N(S)| counts vertices of S that must go unmatched.

Sufficiency (sketch). Suppose |N(S)| \ge |S| for every S \subseteq L, and let M be a matching of maximum size. If M did not saturate L, pick an unmatched vertex u \in L and consider all vertices reachable from u by alternating paths (paths whose edges alternate between non-matching and matching edges). Let A \subseteq L and B \subseteq R be the reachable vertices on each side. A standard argument shows every vertex of B is matched (otherwise an augmenting path would let us enlarge M, contradicting maximality) and that B = N(A) with each vertex of A \setminus \{u\} matched into B. Counting then gives |N(A)| = |B| = |A| - 1 < |A|, violating Hall's condition. So M saturates L. The full details of the reachability argument are the standard augmenting-path proof of the theorem.

Necessity. Suppose a matching M saturates L, and let S \subseteq L be any subset. Each vertex of S is matched by M to its own vertex of R, and these matched partners are distinct because no two edges of a matching share an endpoint. Every matched partner of a vertex in S is, in particular, a neighbor of that vertex, so all |S| of them lie in N(S). Hence |N(S)| \ge |S|. Equivalently: if some set S has |N(S)| < |S|, the |S| vertices of S would need distinct partners drawn from fewer than |S| available neighbors, which is impossible — the deficiency |S| - |N(S)| counts vertices of S that must go unmatched.

Sufficiency (sketch). Suppose |N(S)| \ge |S| for every S \subseteq L, and let M be a matching of maximum size. If M did not saturate L, pick an unmatched vertex u \in L and consider all vertices reachable from u by alternating paths (paths whose edges alternate between non-matching and matching edges). Let A \subseteq L and B \subseteq R be the reachable vertices on each side. A standard argument shows every vertex of B is matched (otherwise an augmenting path would let us enlarge M, contradicting maximality) and that B = N(A) with each vertex of A \setminus \{u\} matched into B. Counting then gives |N(A)| = |B| = |A| - 1 < |A|, violating Hall's condition. So M saturates L. The full details of the reachability argument are the standard augmenting-path proof of the theorem.

Suppose, for contradiction, that every one of the m boxes holds at most one object. Then the total number of objects placed is at most m \cdot 1 = m. But n objects were placed, and n > m, so n \leq m and n > m both hold — an impossibility. So some box must hold at least 2 objects.

The general form follows the same contradiction. If every box held strictly fewer than \lceil n/m \rceil objects, each box would hold at most \lceil n/m \rceil - 1 objects, giving a total of at most m\bigl(\lceil n/m \rceil - 1\bigr) < n objects placed — contradicting that all n objects were placed somewhere.

Path P_n. Color the vertices in order along the path. The first vertex takes any of the k colors. Each later vertex must only avoid the color of the single neighbor already colored, leaving exactly k-1 choices regardless of which color that neighbor received. By the product rule, P(P_n,k) = k(k-1)^{n-1}.

Tree T. Root the tree anywhere and color vertices in any order that visits each vertex after its parent (for example, breadth-first). The root takes k colors; every other vertex has exactly one already- colored neighbor (its parent) to avoid, giving k-1 choices each. The count k(k-1)^{n-1} follows exactly as for the path — a path is just the special case of a tree with no branching.

Cycle C_n. Sequential coloring fails at the last vertex, whose two neighbors may or may not share a color, so we use deletion–contraction. Let e be any edge of C_n. Colorings of C_n - e (a path P_n) split into those where e's endpoints differ (proper colorings of C_n) and those where they agree (in bijection with proper colorings of the contraction C_n / e = C_{n-1}). Hence P(C_n,k) = P(P_n,k) - P(C_{n-1},k) = k(k-1)^{n-1} - P(C_{n-1},k). With base case P(C_3,k) = k(k-1)(k-2) = (k-1)^3 - (k-1), induction gives the closed form: assuming P(C_{n-1},k) = (k-1)^{n-1} + (-1)^{n-1}(k-1), P(C_n,k) = k(k-1)^{n-1} - (k-1)^{n-1} - (-1)^{n-1}(k-1) = (k-1)^n + (-1)^n(k-1) since k(k-1)^{n-1} - (k-1)^{n-1} = (k-1)^n and -(-1)^{n-1} = (-1)^n.

Path P_n. Color the vertices in order along the path. The first vertex takes any of the k colors. Each later vertex must only avoid the color of the single neighbor already colored, leaving exactly k-1 choices regardless of which color that neighbor received. By the product rule, P(P_n,k) = k(k-1)^{n-1}.

Tree T. Root the tree anywhere and color vertices in any order that visits each vertex after its parent (for example, breadth-first). The root takes k colors; every other vertex has exactly one already- colored neighbor (its parent) to avoid, giving k-1 choices each. The count k(k-1)^{n-1} follows exactly as for the path — a path is just the special case of a tree with no branching.

Cycle C_n. Sequential coloring fails at the last vertex, whose two neighbors may or may not share a color, so we use deletion–contraction. Let e be any edge of C_n. Colorings of C_n - e (a path P_n) split into those where e's endpoints differ (proper colorings of C_n) and those where they agree (in bijection with proper colorings of the contraction C_n / e = C_{n-1}). Hence P(C_n,k) = P(P_n,k) - P(C_{n-1},k) = k(k-1)^{n-1} - P(C_{n-1},k). With base case P(C_3,k) = k(k-1)(k-2) = (k-1)^3 - (k-1), induction gives the closed form: assuming P(C_{n-1},k) = (k-1)^{n-1} + (-1)^{n-1}(k-1), P(C_n,k) = k(k-1)^{n-1} - (k-1)^{n-1} - (-1)^{n-1}(k-1) = (k-1)^n + (-1)^n(k-1) since k(k-1)^{n-1} - (k-1)^{n-1} = (k-1)^n and -(-1)^{n-1} = (-1)^n.

Let G be triangle-free on n vertices with m edges. The key observation: if uv is an edge, then u and v share no common neighbor (a common neighbor would complete a triangle), so their neighborhoods are disjoint subsets of the n vertices and d(u) + d(v) \le n \quad \text{for every edge } uv. Sum this inequality over all m edges. On the left, each vertex w appears once for each edge incident to it, contributing d(w) each time, so the total is \sum_w d(w)^2. Therefore \sum_{w} d(w)^2 \le mn. On the other hand, the Cauchy–Schwarz inequality (or the fact that the mean of squares is at least the square of the mean) gives \sum_w d(w)^2 \ge \frac{\left(\sum_w d(w)\right)^2}{n} = \frac{(2m)^2}{n} = \frac{4m^2}{n}, using the handshaking identity \sum_w d(w) = 2m. Combining, \frac{4m^2}{n} \le mn \implies m \le \frac{n^2}{4}, and since m is an integer, m \le \lfloor n^2/4 \rfloor.

For sharpness, take K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}: it is bipartite, hence triangle-free (a triangle would need an odd cycle), and it has exactly \lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \lfloor n^2/4 \rfloor edges.