CommeUnJeu · L1 MPSI
Sums, products and binomial coefficients
This chapter is a workshop. We will not introduce a deep theory; we will train the calculus muscles needed for every chapter that follows. Three tools sharpen here. Sums (with the compact notation \(\sum\)): how to manipulate them, change of index, telescopic collapse, double sums. Products and factorial (with \(\prod\)): how the multiplicative analogue works, the factorial \(n!\), telescopic products. Binomial coefficients: \(\binom{n}{p}\), Pascal's triangle, and the famous formula \((a+b)^n\).
The plan has three movements, each independent of the others, each short. We will move fast on the parts that students have already met (in lycée: factorials, the binomial for small \(n\)); we will be deliberate on the genuinely new material (telescopic sums, double sums, the binomial formula). Many proofs in this chapter are by induction on \(n\), or by careful index manipulation --- techniques mastered in the Logic chapter; we apply them here. The companion chapter Properties of \(\mathbb{R}\) (in the Analyse theme) handles the order side: inequalities, absolute value, floor function, supremum/infimum. A pedagogical convention. When clarifying a \(\sum\) identity, we will sometimes write both the formal form and the extended form (terms written out with \texttt{+}) on consecutive lines, so the reader can see what each term looks like.
The plan has three movements, each independent of the others, each short. We will move fast on the parts that students have already met (in lycée: factorials, the binomial for small \(n\)); we will be deliberate on the genuinely new material (telescopic sums, double sums, the binomial formula). Many proofs in this chapter are by induction on \(n\), or by careful index manipulation --- techniques mastered in the Logic chapter; we apply them here. The companion chapter Properties of \(\mathbb{R}\) (in the Analyse theme) handles the order side: inequalities, absolute value, floor function, supremum/infimum. A pedagogical convention. When clarifying a \(\sum\) identity, we will sometimes write both the formal form and the extended form (terms written out with \texttt{+}) on consecutive lines, so the reader can see what each term looks like.
I
Sums
The notation \(\sum\) is shorthand: it abbreviates a sum that would be intractable to write out. We start by stating its rules: how the dummy index works, how to break a sum or shift the index, how two consecutive terms cancel. The five subsections of this section drill these mechanics on classical examples; later chapters will use them everywhere.
I.1
Sigma notation
Given a finite list of real numbers \(a_m, a_{m+1}, \dots, a_n\), their sum \(a_m + a_{m+1} + \dots + a_n\) is denoted \(\sum_{k=m}^{n} a_k\). The variable \(k\) is a dummy index: it ranges over the integers from \(m\) to \(n\) (inclusive), and the value of the sum does not depend on the letter chosen (\(k\), \(i\), \(j\), \(\ell\) all yield the same sum). Two basic rules govern how \(\sum\) interacts with addition and scalar multiplication.
Definition — Sigma notation
For \(m, n \in \mathbb{Z}\) and \((a_k)\) a family of real numbers indexed by integers, the sum \(\sum_{k=m}^{n} a_k\) is defined as follows. - If \(m \le n\): $$ \sum_{k=m}^{n} a_k = a_m + a_{m+1} + \dots + a_n. $$
- If \(m > n\) (the empty sum case): $$ \sum_{k=m}^{n} a_k = 0. $$
Example
\(\sum_{k=1}^{5} k = 1 + 2 + 3 + 4 + 5 = 15\). Proposition — Linearity of \(\sum\)
For \(m, n \in \mathbb{Z}\) with \(m \le n\), \(\lambda, \mu \in \mathbb{R}\), and \((a_k)_{m \le k \le n}\), \((b_k)_{m \le k \le n}\) two finite families of real numbers: $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=m}^{n} (\lambda a_k + \mu b_k) &= \lambda \sum_{k=m}^{n} a_k + \mu \sum_{k=m}^{n} b_k \\
(\lambda a_m + \mu b_m) + \dots + (\lambda a_n + \mu b_n) &= \lambda(a_m + \dots + a_n) + \mu(b_m + \dots + b_n). \end{aligned}} $$ In particular, \(\sum (a_k + b_k) = \sum a_k + \sum b_k\) and \(\sum \lambda a_k = \lambda \sum a_k\). Proposition — Splitting and Chasles relation
For \(m, p, n \in \mathbb{Z}\) with \(m \le p < n\), and \((a_k)_{m \le k \le n}\) a finite family of real numbers: $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=m}^{n} a_k &= \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k \\
a_m + \dots+ a_p + a_{p+1} +\dots+ a_n &= (a_m + \dots + a_p) + (a_{p+1} + \dots + a_n). \end{aligned}} $$ Skills to practice
- Reading and evaluating \(\sum\) sums
I.2
Change of index
The dummy index can be re-named (it stays an integer) or shifted by an additive or symmetric transformation. Two changes of index are everywhere: shift \(j = k - p\) (renumbering by \(p\)) and reflection \(j = n - k\) (counting backwards). Each preserves the sum --- it just reshapes the bounds.
Proposition — Change of index
Let \(m \le n\) be integers (so the index set \(\{m, m+1, \dots, n\}\) is non-empty). - Shift: for \(p \in \mathbb{Z}\), with \(j = k - p\) $$ \textcolor{colorprop}{ \sum_{k=m}^{n} a_k = \sum_{j=m-p}^{n-p} a_{j+p} } $$
- Reflection: with \(j = n - k\) (so \(k = n - j\)), which shifts the lower bound to \(0\), $$ \textcolor{colorprop}{\begin{aligned}\sum_{k=m}^{n} a_k &= \sum_{j=0}^{n-m} a_{n-j}\\ a_m+a_{m+1}+\dots+a_{n-1}+a_n&=a_n+a_{n-1}+\dots+a_{m+1}+a_m \end{aligned} } $$ or, equivalently, in the bound-preserving form, with \(j = n + m - k\) (so \(k = n + m - j\)), $$ \textcolor{colorprop}{ \sum_{k=m}^{n} a_k = \sum_{j=m}^{n} a_{n+m-j} } $$ which keeps the original bounds \(m\) and \(n\) unchanged.
Example
Rewrite \(\sum_{k=3}^{n+3} k^2\) with summation index starting at \(0\).
Set \(j = k - 3\). Then \(k = j + 3\), and as \(k\) ranges from \(3\) to \(n+3\), \(j\) ranges from \(0\) to \(n\). Hence $$ \sum_{k=3}^{n+3} k^2 = \sum_{j=0}^{n} (j+3)^2 = \sum_{j=0}^{n} (j^2 + 6j + 9). $$
Example
Show that \(\sum_{k=0}^{n} a_k = \sum_{k=0}^{n} a_{n-k}\).
Apply the reflection \(j = n - k\): \(k = n - j\), and as \(k\) ranges from \(0\) to \(n\), \(j\) ranges from \(n\) to \(0\), i.e. \(j\) takes the same values as \(k\). Hence $$ \sum_{k=0}^{n} a_k = \sum_{j=0}^{n} a_{n-j} = \sum_{k=0}^{n} a_{n-k} $$ (the last equality just renames the dummy back to \(k\)).
Skills to practice
- Translating and reflecting indices
I.3
Classical sums
Four sums must be at the fingertips: the sum of the first \(n\) integers, the sum of their squares, the sum of their cubes, and the geometric sum. Plus one factorisation that is the algebraic dual of the geometric sum: \(a^n - b^n\). These five formulas underpin every later computation.
Theorem — Classical sums
For \(n \in \mathbb{N}\): - Sum of integers. $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} k &= \frac{n(n+1)}{2} \\ 1 + 2 + 3 + \dots + n &= \frac{n(n+1)}{2}. \end{aligned}} $$
- Sum of squares. $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} k^2 &= \frac{n(n+1)(2n+1)}{6} \\ 1^2 + 2^2 + 3^2 + \dots + n^2 &= \frac{n(n+1)(2n+1)}{6}. \end{aligned}} $$
- Sum of cubes. $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} k^3 &= \left(\frac{n(n+1)}{2}\right)^2 \\ 1^3 + 2^3 + 3^3 + \dots + n^3 &= \left(\frac{n(n+1)}{2}\right)^2. \end{aligned}} $$
The proofs use two recurring ideas: change of index (for the sum of integers) and telescoping of a difference \(u_{k+1} - u_k\) followed by polynomial expansion (for the sums of squares and cubes, and for the geometric sum). We use telescoping here in anticipation: it is stated and proved in full as the telescoping Proposition of the next subsection (Telescopic sums below); only its conclusion \(\sum_{k=m}^{n}(u_{k+1}-u_k) = u_{n+1} - u_m\) is invoked here.
- Sum of integers --- change of index. Let \(S = \sum_{i=0}^{n} i\). With the change of index \(i \mapsto n - i\), the same sum can also be written \(S = \sum_{i=0}^{n} (n - i)\). Add the two expressions of \(S\): $$ \begin{aligned} 2S &= \sum_{i=0}^{n} i + \sum_{i=0}^{n} (n - i) \\ &= \sum_{i=0}^{n} \big(i + (n - i)\big) && \text{(linearity)} \\ &= \sum_{i=0}^{n} n && \text{(simplification: } i + (n-i) = n\text{)} \\ &= n \sum_{i=0}^{n} 1 && \text{(linearity)} \\ &= n (n+1) && \text{(} \sum_{i=0}^{n} 1 = n+1 \text{)}. \end{aligned} $$ Hence \(\displaystyle\sum_{k=0}^{n} k = \frac{n(n+1)}{2}\).
- Sum of squares --- telescoping with cubes. Apply telescoping to \(u_k = k^3\) and chain the operations: $$ \begin{aligned} \sum_{k=0}^{n} \big((k+1)^3 - k^3\big) &= (n+1)^3 && \text{(telescoping, } u_k = k^3 \text{)} \\ \sum_{k=0}^{n} (3k^2 + 3k + 1) &= (n+1)^3 && \text{(expand } (k+1)^3 - k^3\text{)} \\ 3 \sum_{k=0}^{n} k^2 + 3 \sum_{k=0}^{n} k + \sum_{k=0}^{n} 1 &= (n+1)^3 && \text{(linearity)} \\ 3 \sum_{k=0}^{n} k^2 + 3 \cdot \frac{n(n+1)}{2} + (n+1) &= (n+1)^3 && \text{(known sums)} \\ 3 \sum_{k=0}^{n} k^2 &= (n+1)^3 - \frac{3n(n+1)}{2} - (n+1) && \text{(isolate)} \\ 6 \sum_{k=0}^{n} k^2 &= 2(n+1)^3 - 3n(n+1) - 2(n+1) && \text{(}\times 2\text{)} \\ 6 \sum_{k=0}^{n} k^2 &= (n+1)\big[2(n+1)^2 - 3n - 2\big] && \text{(factor } (n+1) \text{)} \\ 6 \sum_{k=0}^{n} k^2 &= (n+1)\big[2n^2 + 4n + 2 - 3n - 2\big] && \text{(expand } 2(n+1)^2 = 2n^2 + 4n + 2 \text{)} \\ 6 \sum_{k=0}^{n} k^2 &= (n+1)(2n^2 + n) && \text{(collect terms inside the bracket)} \\ 6 \sum_{k=0}^{n} k^2 &= n(n+1)(2n+1) && \text{(factor } n \text{).} \end{aligned} $$ Hence \(\displaystyle\sum_{k=0}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\).
- Sum of cubes --- same trick with \((k+1)^4 - k^4\). Apply telescoping to \(u_k = k^4\), expand \((k+1)^4 - k^4 = 4k^3 + 6k^2 + 4k + 1\), and reuse \(\sum k\) and \(\sum k^2\): $$ \begin{aligned} \sum_{k=0}^{n} \big((k+1)^4 - k^4\big) &= (n+1)^4 && \text{\doublecolumnscriptsize (telescoping, } u_k = k^4 \text{)} \\ \sum_{k=0}^{n} (4k^3 + 6k^2 + 4k + 1) &= (n+1)^4 && \text{\doublecolumnscriptsize (expand)} \\ 4 \sum k^3 + 6 \sum k^2 + 4 \sum k + \sum 1 &= (n+1)^4 && \text{\doublecolumnscriptsize (linearity)} \\ 4 \sum k^3 + n(n+1)(2n+1) \\ \quad + 2n(n+1) + (n+1) &= (n+1)^4 && \text{\doublecolumnscriptsize (known sums)} \\ 4 \sum k^3 &= (n+1)^4 - n(n+1)(2n+1) \\ &\quad - 2n(n+1) - (n+1) && \text{\doublecolumnscriptsize (isolate)} \\ 4 \sum k^3 &= (n+1)\big[(n+1)^3 - n(2n+1) - 2n - 1\big] && \text{\doublecolumnscriptsize (factor } (n+1) \text{)} \\ 4 \sum k^3 &= (n+1)\big[n^3 + 3n^2 + 3n + 1 \\ &\quad - 2n^2 - n - 2n - 1\big] && \text{\doublecolumnscriptsize (expand } (n+1)^3, n(2n+1)\text{)} \\ 4 \sum k^3 &= (n+1)(n^3 + n^2) && \text{\doublecolumnscriptsize (collect bracket terms)} \\ 4 \sum k^3 &= n^2(n+1)^2 && \text{\doublecolumnscriptsize (factor } n^2 \text{).} \end{aligned} $$ Hence \(\displaystyle\sum_{k=0}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2\).
- Geometric sum --- telescoping after multiplying by \((1-x)\). For \(x \ne 1\): $$ \begin{aligned} (1 - x) \sum_{k=0}^{n} x^k &= \sum_{k=0}^{n} x^k - x \sum_{k=0}^{n} x^k && \text{(distribute)} \\ &= \sum_{k=0}^{n} x^k - \sum_{k=0}^{n} x^{k+1} && \text{(factor inside the sum)} \\ &= \sum_{k=0}^{n} (x^k - x^{k+1}) && \text{(linearity)} \\ &= x^0 - x^{n+1} && \text{(telescoping, } u_k = x^k \text{)} \\ &= 1 - x^{n+1}. \end{aligned} $$ Divide by \(1 - x\): \(\displaystyle\sum_{k=0}^{n} x^k = \frac{1 - x^{n+1}}{1 - x}\).
Example
Compute \(\displaystyle \sum_{k=1}^{100} k\).
\(\sum_{k=1}^{100} k = 100 \cdot 101 / 2 = 5050\).
Example
Compute \(\displaystyle \sum_{k=0}^{n} 2^k\).
Geometric sum with \(x = 2\): \(\sum_{k=0}^{n} 2^k = (2^{n+1} - 1)/(2 - 1) = 2^{n+1} - 1\).
Proposition — Factorisation of \(a^n - b^n\)
For \(a, b \in \mathbb{R}\) and \(n \in \mathbb{N}^*\): $$ \textcolor{colorprop}{a^n - b^n = (a - b)\sum_{k=0}^{n-1} a^{n-1-k} b^{k} = (a-b)(a^{n-1} + a^{n-2}b + \dots + a b^{n-2} + b^{n-1})}. $$
Set \(u_k = a^{n-k} b^k\). Distributing \((a - b)\) on the sum produces a telescoping sum: $$ (a - b) \sum_{k=0}^{n-1} a^{n-1-k} b^k = \sum_{k=0}^{n-1} \big( a^{n-k} b^k - a^{n-1-k} b^{k+1} \big) = \sum_{k=0}^{n-1} (u_k - u_{k+1}) = u_0 - u_n = a^n - b^n. $$
Skills to practice
- Recognising and applying closed forms
- Combining classical sums by linearity
I.4
Telescopic sums
A telescopic sum is a sum of consecutive differences \(u_{k+1} - u_k\), in which all middle terms cancel pairwise --- only the endpoints survive. The trick is to recognize when a summand can be written as such a difference, because then the entire sum collapses to two terms.
Proposition — Telescopic sum
For any sequence \((u_k)\) and integers \(m \le n\): $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=m}^{n} (u_{k+1} - u_k) &= u_{n+1} - u_m \\
(u_{m+1}-u_m) + (u_{m+2}-u_{m+1}) + \dots + (u_{n+1}-u_n) &= u_{n+1} - u_m \end{aligned}} $$
Three perspectives on the same result: two formal proofs and one visual.
- Proof 1 --- induction on \(n\) (with \(m\) fixed). Initialization. For \(n = m\), the sum has one term: \(\sum_{k=m}^{m} (u_{k+1} - u_k) = u_{m+1} - u_m\), which equals \(u_{n+1} - u_m\) at \(n=m\). \(\checkmark\) Heredity. Assume the formula at rank \(n\). At rank \(n+1\): $$ \begin{aligned} \sum_{k=m}^{n+1} (u_{k+1} - u_k) &= \sum_{k=m}^{n} (u_{k+1} - u_k) + (u_{n+2} - u_{n+1}) && \text{(Chasles, split off the last term)} \\ &= (u_{n+1} - u_m) + (u_{n+2} - u_{n+1}) && \text{(induction hypothesis)} \\ &= u_{n+2} - u_m && \text{(simplify).} \end{aligned} $$ Heredity holds; the result follows for all \(n \ge m\).
- Proof 2 --- change of index. $$ \begin{aligned} \sum_{k=m}^{n} (u_{k+1} - u_k) &= \sum_{k=m}^{n} u_{k+1} - \sum_{k=m}^{n} u_k && \text{(linearity)} \\ &= \sum_{j=m+1}^{n+1} u_j - \sum_{k=m}^{n} u_k && \text{(change of index } j = k+1 \text{)} \\ &= u_{n+1} + \sum_{j=m+1}^{n} u_j - \sum_{k=m}^{n} u_k && \text{(Chasles, peel off } j=n+1\text{)} \\ &= u_{n+1} + \sum_{j=m+1}^{n} u_j - u_m - \sum_{k=m+1}^{n} u_k && \text{(Chasles, peel off } k=m\text{)} \\ &= u_{n+1} - u_m && \text{(the two inner sums are equal --- dummy index).} \end{aligned} $$
- Visual idea --- expand and watch terms cancel. Writing the sum out term by term: $$ \sum_{k=m}^{n} (u_{k+1} - u_k) = (u_{m+1} - u_m) + (u_{m+2} - u_{m+1}) + \dots + (u_{n+1} - u_n). $$ Every \(u_j\) with \(m+1 \le j \le n\) appears exactly twice --- once with a \(+\) sign, once with a \(-\) sign --- and the two occurrences cancel. Only \(-u_m\) at the start and \(+u_{n+1}\) at the end survive: the sum collapses to \(u_{n+1} - u_m\).
Example
Compute \(\displaystyle \sum_{k=1}^{n} \frac{1}{k(k+1)}\).
Decompose: \(\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}\). Setting \(u_k = -\frac{1}{k}\), the summand is \(u_{k+1} - u_k\). By the telescopic formula $$ \sum_{k=1}^{n} \frac{1}{k(k+1)} = u_{n+1} - u_1 = -\frac{1}{n+1} + 1 = \frac{n}{n+1}. $$
Example
Compute \(\displaystyle \sum_{k=1}^{n} \ln\!\left(1 + \frac{1}{k}\right)\).
\(\ln(1 + 1/k) = \ln((k+1)/k) = \ln(k+1) - \ln(k)\). Setting \(u_k = \ln(k)\), the summand is \(u_{k+1} - u_k\). Hence $$ \sum_{k=1}^{n} \ln\!\left(1 + \frac{1}{k}\right) = \ln(n+1) - \ln(1) = \ln(n+1). $$
Method — Recognize a telescopic sum
Look for the pattern \(u_{k+1} - u_k\) (a single-step difference). Two frequent triggers: - Rational fraction \(\dfrac{1}{k(k+1)}\): partial-fraction decomposition gives \(\dfrac{1}{k(k+1)} = \dfrac{1}{k} - \dfrac{1}{k+1}\), a single-step difference of \(u_k = -\dfrac{1}{k}\). (For wider gaps \(\dfrac{1}{k(k+a)}\) with \(a \ge 2\), the decomposition produces an \(a\)-step difference --- handled in the going-further section of the exercises.)
- Logarithm of a ratio: \(\ln\!\big(f(k+1)/f(k)\big) = \ln f(k+1) - \ln f(k)\).
Skills to practice
- Decomposing then collapsing
I.5
Double sums
A double sum \(\sum_{i,j}\) runs over a rectangle (or a triangle) of pairs \((i, j)\). Three simplifications: when the rectangle is full and the summand factors, the sum is a product of two simple sums; the order of summation can be permuted (Fubini for sums); for triangles, one swaps the roles of the inner and outer variables.
Proposition — Double-sum identities
- Permutation (Fubini): $$ \textcolor{colorprop}{\sum_{i=m}^{n} \sum_{j=p}^{q} a_{i,j} = \sum_{j=p}^{q} \sum_{i=m}^{n} a_{i,j}}. $$
- Factorisation (separable summand): if \(a_{i,j} = b_i c_j\) $$ \textcolor{colorprop}{\sum_{i=m}^{n} \sum_{j=p}^{q} b_i c_j = \left(\sum_{i=m}^{n} b_i\right)\!\left(\sum_{j=p}^{q} c_j\right)}. $$
- Triangle: swap inside and outside: $$ \textcolor{colorprop}{\sum_{1 \le i \le j \le n} a_{i,j} = \sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j} = \sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}}. $$
The three identities all rest on commutativity and associativity of addition on \(\mathbb{R}\) --- which let us re-order any finite sum freely --- combined with linearity of \(\sum\).
- Permutation (Fubini) --- expand and re-collect. The rectangular double sum enumerates every cell \((i,j)\) of the \((n - m + 1) \times (q - p + 1)\) index rectangle exactly once. Both nested orderings list the same cells; the resulting finite sums of the same numbers are equal: $$ \sum_{i=m}^{n} \sum_{j=p}^{q} a_{i,j} = \sum_{\substack{m \le i \le n \\ p \le j \le q}} a_{i,j} = \sum_{j=p}^{q} \sum_{i=m}^{n} a_{i,j}. $$
- Factorisation (separable summand). Fix \(i\) in the inner sum and apply linearity (\(b_i\) is constant with respect to \(j\)): $$ \begin{aligned} \sum_{i=m}^{n} \sum_{j=p}^{q} b_i c_j &= \sum_{i=m}^{n} \left[ b_i \sum_{j=p}^{q} c_j \right] && \text{(linearity, } b_i \text{ does not depend on } j\text{)} \\ &= \left(\sum_{j=p}^{q} c_j\right) \sum_{i=m}^{n} b_i && \text{(linearity, the parenthesised factor does not depend on } i\text{)} \\ &= \left(\sum_{i=m}^{n} b_i\right) \left(\sum_{j=p}^{q} c_j\right). \end{aligned} $$
- Triangle: swap inside and outside. The set \(\{(i,j) : 1 \le i \le j \le n\}\) partitions in two equivalent ways:
- ordering on \(j\) outside: for each \(j \in \{1, \dots, n\}\), the inner index \(i\) runs over \(\{1, \dots, j\}\), giving \(\sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j}\);
- ordering on \(i\) outside: for each \(i \in \{1, \dots, n\}\), the inner index \(j\) runs over \(\{i, \dots, n\}\), giving \(\sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}\).
Example
Compute \(\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} ij\).
The summand \(ij\) is separable. Factorisation: $$ \sum_{i=1}^{n} \sum_{j=1}^{n} ij = \left(\sum_{i=1}^{n} i\right)\!\left(\sum_{j=1}^{n} j\right) = \left(\frac{n(n+1)}{2}\right)^2. $$
Example
Compute \(\displaystyle \sum_{1 \le i \le j \le n} 1\).
Triangle of pairs \((i, j)\) with \(1 \le i \le j \le n\). Sum of \(1\) over this triangle = number of pairs = \(n(n+1)/2\). Verify by ordering on \(j\): \(\sum_{j=1}^{n} \sum_{i=1}^{j} 1 = \sum_{j=1}^{n} j = n(n+1)/2\).
Method — Compute a double sum
Three reflexes, in order: - Separable summand: if \(a_{i,j} = b_i c_j\), factor \(\sum_{i,j} b_i c_j = \bigl(\sum_i b_i\bigr)\bigl(\sum_j c_j\bigr)\) --- two single sums.
- Triangular range: choose the inner sum so the bounds of the inner variable are visible. With \(1 \le i \le j \le n\), ordering on \(j\) outside gives \(\sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j}\); ordering on \(i\) outside gives \(\sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}\). Pick whichever makes the inner sum a known classical sum.
- Stuck rectangle: if neither of the above helps, swap the order of summation (Fubini) and try again --- often the swapped form reveals a separable structure or a recognisable inner sum.
Skills to practice
- Swapping and splitting double indices
II
Products
The notation \(\prod\) is the multiplicative cousin of \(\sum\). The same machinery applies: dummy index, change of index, telescopic collapse. The only structural change is the convention for the empty product (it is \(1\), not \(0\)). The most useful product is the factorial.
II.1
Pi notation and factorial
The factorial \(n!\) counts the number of orderings of \(n\) objects. Algebraically, it is the product of the first \(n\) positive integers. It will appear everywhere: in binomial coefficients, in Taylor expansions, in counting problems.
Definition — Pi notation\(\virgule\) factorial
- For \(m, n \in \mathbb{Z}\) and a family \((a_k)\) of real numbers indexed by integers, the product \(\prod_{k=m}^{n} a_k\) is defined as follows.
- If \(m \le n\): $$ \prod_{k=m}^{n} a_k = a_m \cdot a_{m+1} \cdot \dots \cdot a_n. $$
- If \(m > n\) (the empty product case): \(\prod_{k=m}^{n} a_k = 1\).
- For \(n \in \mathbb{N}\), the factorial of \(n\) is $$ \textcolor{colordef}{n!} = \prod_{k=1}^{n} k = 1 \cdot 2 \cdot 3 \cdots n. $$ By convention, \(\textcolor{colordef}{0!} = 1\) (empty product).
Example
- \(0! = 1\), \(1! = 1\), \(2! = 2\), \(3! = 6\), \(4! = 24\), \(5! = 120\).
- \(10! = 3628800\) (already large).
Proposition — Recurrence and ratios of factorials
For \(n \in \mathbb{N}\): $$ \textcolor{colorprop}{(n+1)! = (n+1) \cdot n!}. $$ For \(n \ge p \ge 0\): $$ \textcolor{colorprop}{\frac{n!}{p!} = (p+1)(p+2)\cdots n = \prod_{k=p+1}^{n} k}. $$ Skills to practice
- Manipulating products and factorials
II.2
Telescopic products
The multiplicative analogue of the telescopic sum: a product of ratios \(u_{k+1}/u_k\) collapses to two endpoint terms. Useful when a fraction can be rewritten as such a ratio.
Proposition — Telescopic product
For a sequence \((u_k)\) of nonzero real numbers and \(m \le n\): $$ \textcolor{colorprop}{\prod_{k=m}^{n} \frac{u_{k+1}}{u_k} = \frac{u_{n+1}}{u_m}}. $$ Example
Compute \(\displaystyle \prod_{k=1}^{n} \frac{k+1}{k}\).
Setting \(u_k = k\), the term is \(u_{k+1}/u_k\). By the telescopic product $$ \prod_{k=1}^{n} \frac{k+1}{k} = \frac{u_{n+1}}{u_1} = \frac{n+1}{1} = n+1. $$
Method — Recognize a telescopic product
Look for the pattern \(u_{k+1}/u_k\). Common triggers: - Explicit ratio of consecutive values: \(\dfrac{f(k+1)}{f(k)}\) for some sequence \((f(k))\).
- Ratio of consecutive factorials: \(\dfrac{(k+1)!}{k!} = k+1\), so \(\prod_{k=1}^{n}\dfrac{(k+1)!}{k!} = (n+1)!\).
- Logarithmic fall-back: when the factors are positive, take \(\ln\) to convert the product into a telescopic sum of \(\ln u_{k+1} - \ln u_k\), then re-exponentiate.
Skills to practice
- Collapsing multiplicative chains
III
Binomial coefficients
The binomial coefficient \(\binom{n}{k}\) counts the number of ways to choose \(k\) objects out of \(n\) (without order). The same number appears as the coefficient of \(a^{n-k}b^k\) in the expansion of \((a+b)^n\). The two faces --- combinatorial and algebraic --- are equivalent, and we will use whichever is most convenient. The chapter culminates in the binomial formula, the most famous algebraic identity in elementary mathematics.
III.1
Definition and properties
We define \(\binom{n}{k}\) by its factorial formula and observe its three fundamental properties: it will appear (in the binomial formula proved below) as the coefficient of \(a^{n-k} b^k\) in the symmetric polynomial \((a+b)^n\), it is symmetric in \(k\) and \(n-k\), and it satisfies a recurrence relation that gives Pascal's triangle.
Definition — Binomial coefficient
For \(n \in \mathbb{N}\) and \(k \in \mathbb{Z}\), the binomial coefficient \(\binom{n}{k}\) is defined by: $$ \textcolor{colordef}{\binom{n}{k}} = \begin{cases} \dfrac{n!}{k!\,(n-k)!} & \text{if } 0 \le k \le n, \\
0 & \text{otherwise.} \end{cases} $$ It reads « \(n\) choose \(k\) ». The factorial expression above is the definition; the fact that this number also equals the count of subsets of size \(k\) in a set of \(n\) elements is the combinatorial interpretation, established separately by a counting argument (it is not part of the definition). Proposition — Standard values of binomial coefficients
For \(n \in \mathbb{N}\): - \(\textcolor{colorprop}{\binom{n}{0} = \binom{n}{n} = 1}\) (one way to choose nothing or everything);
- \(\textcolor{colorprop}{\binom{n}{1} = \binom{n}{n-1} = n}\) (\(n\) singletons or \(n\) subsets missing one element);
- for \(n \ge 2\), \(\textcolor{colorprop}{\binom{n}{2} = \binom{n}{n-2} = \dfrac{n(n-1)}{2}}\).
Example
\(\binom{5}{2} = \dfrac{5!}{2!\,3!} = \dfrac{5 \cdot 4}{2} = 10\) --- there are ten ways to choose a pair from a \(5\)-element set. Proposition — Symmetry\(\virgule\) Pascal\(\virgule\) absorption
For \(n \in \mathbb{N}\) and \(k \in \mathbb{Z}\) with \(0 \le k \le n\): - Symmetry: \(\textcolor{colorprop}{\binom{n}{k} = \binom{n}{n-k}}\).
- Pascal's identity: for \(1 \le k \le n-1\), \(\textcolor{colorprop}{\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}}\).
- Absorption: for \(1 \le k \le n\), \(\textcolor{colorprop}{k\binom{n}{k} = n\binom{n-1}{k-1}}\).
The core of all three proofs is the same: put the fractions on a common denominator using the factorial identities \(k \cdot (k-1)! = k!\) and \((n-k) \cdot (n-k-1)! = (n-k)!\).
- Symmetry. Apply the factorial formula and simplify the second factor: $$ \begin{aligned} \binom{n}{n-k} &= \frac{n!}{(n-k)! \, \big(n - (n-k)\big)!} && \text{(factorial formula at index } n-k \text{)} \\ &= \frac{n!}{(n-k)! \, k!} && \text{(simplification: } n - (n-k) = k\text{)} \\ &= \frac{n!}{k! \, (n-k)!} && \text{(swap factors in the denominator)} \\ &= \binom{n}{k} && \text{(factorial formula at index } k\text{).} \end{aligned} $$
- Pascal. The common denominator we aim for is \(k!\,(n-k)!\). We multiply each fraction by \(1\) in a way that lets the factorials extend to it: $$ \begin{aligned} \binom{n-1}{k-1} + \binom{n-1}{k} &= \frac{(n-1)!}{(k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-k-1)!} && \text{\doublecolumnscriptsize (factorial formula)} \\ &= \frac{k \cdot (n-1)!}{k \cdot (k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-k-1)!} && \text{\doublecolumnscriptsize (multiply 1st fraction by } k/k \text{)} \\ &= \frac{k \cdot (n-1)!}{k!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-k-1)!} && \text{\doublecolumnscriptsize (}k \cdot (k-1)! = k! \text{ in 1st denom.)} \\ &= \frac{k \cdot (n-1)!}{k!\,(n-k)!} \\ &\quad + \frac{(n-k) \cdot (n-1)!}{k!\,(n-k) \cdot (n-k-1)!} && \text{\doublecolumnscriptsize (multiply 2nd fraction by } (n-k)/(n-k) \text{)} \\ &= \frac{k \cdot (n-1)!}{k!\,(n-k)!} + \frac{(n-k) \cdot (n-1)!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (}(n-k) \cdot (n-k-1)! = (n-k)! \text{ in 2nd denom.)} \\ &= \frac{k \cdot (n-1)! + (n-k) \cdot (n-1)!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (common denominator reached)} \\ &= \frac{(n-1)! \, \big[k + (n-k)\big]}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (factor } (n-1)! \text{)} \\ &= \frac{n \cdot (n-1)!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (}k + (n-k) = n\text{)} \\ &= \frac{n!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (}n \cdot (n-1)! = n!\text{)} \\ &= \binom{n}{k}. \end{aligned} $$
- Absorption. Same idea, simpler: pull a factor in or out of a factorial. $$ \begin{aligned} k \binom{n}{k} &= \frac{k \cdot n!}{k! \, (n-k)!} && \text{(factorial formula)} \\ &= \frac{k \cdot n!}{k \cdot (k-1)! \, (n-k)!} && \text{(}k! = k \cdot (k-1)!\text{)} \\ &= \frac{n!}{(k-1)! \, (n-k)!} && \text{(cancel the factor } k\text{)} \\ &= \frac{n \cdot (n-1)!}{(k-1)! \, (n-k)!} && \text{(}n! = n \cdot (n-1)!\text{)} \\ &= n \binom{n-1}{k-1}. \end{aligned} $$
Skills to practice
- Proving identities by calculation
III.2
Pascal's triangle
Pascal's identity gives a recursive procedure to compute \(\binom{n}{k}\): each entry is the sum of the two entries above. The resulting array is Pascal's triangle, a fixture of elementary combinatorics.
Example
Method — Build Pascal's triangle row by row
To compute \(\binom{n}{k}\) for small \(n\), use Pascal's recurrence: - start with row \(0\): \(\binom{0}{0} = 1\);
- each new row begins and ends with \(1\);
- interior entries are the sum of the two entries diagonally above (above-left and above-right).
Skills to practice
- Building and exploiting the triangle
III.3
Binomial formula
The binomial formula expresses \((a+b)^n\) as an explicit linear combination of monomials \(a^{n-k}b^k\) with coefficients exactly the binomial coefficients. It is the key identity that links combinatorics, algebra, and analysis: it underlies Taylor expansions and many counting arguments.
Theorem — Binomial formula (Newton)
For \(a, b \in \mathbb{R}\) (or \(\mathbb{C}\)) and \(n \in \mathbb{N}\): $$ \textcolor{colorprop}{(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k}. $$
Induction on \(n\).
- Initialization. For \(n = 0\): \((a+b)^0 = 1\) and \(\sum_{k=0}^{0} \binom{0}{k} a^{0-k} b^k = \binom{0}{0} = 1\). \(\checkmark\)
- Heredity. Assume the formula at rank \(n\). Compute \((a+b)^{n+1}\) step by step: $$ \begin{aligned} (a+b)^{n+1} &= (a+b)\,(a+b)^n && \text{\doublecolumnscriptsize (split off one factor)} \\ &= (a+b) \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k && \text{\doublecolumnscriptsize (by induction hypothesis)} \\ &= a \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k \\ &\quad + b \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k && \text{\doublecolumnscriptsize (distribute)} \\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k+1} && \text{\doublecolumnscriptsize (factor inside the sums)} \\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=1}^{n+1} \binom{n}{k-1} a^{n+1-k} b^k && \text{\doublecolumnscriptsize (change of index } k \to k+1\text{ in the 2nd sum)} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=1}^{n+1} \binom{n}{k-1} a^{n+1-k} b^k && \text{\doublecolumnscriptsize (peel } k=0 \text{ off the 1st sum)} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=1}^{n} \binom{n}{k-1} a^{n+1-k} b^k + b^{n+1} && \text{\doublecolumnscriptsize (peel } k=n+1 \text{ off the 2nd sum)} \\ &= a^{n+1} + \sum_{k=1}^{n} \Big[\binom{n}{k} + \binom{n}{k-1}\Big] a^{n+1-k} b^k + b^{n+1} && \text{\doublecolumnscriptsize (combine the two sums on } k=1\text{..}n\text{)} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n+1}{k} a^{n+1-k} b^k + b^{n+1} && \text{\doublecolumnscriptsize (Pascal's identity)} \\ &= \sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k} b^k && \text{\doublecolumnscriptsize (reabsorb }a^{n+1}\text{ and }b^{n+1}\text{).} \end{aligned} $$ Heredity holds. The result follows for all \(n \in \mathbb{N}\).
Example
Expand \((a+b)^4\).
Read the row \(n=4\) of Pascal's triangle: \(1, 4, 6, 4, 1\). Hence $$ (a+b)^4 = a^4 + 4 a^3 b + 6 a^2 b^2 + 4 a b^3 + b^4. $$
Example
Compute \(\sum_{k=0}^{n} \binom{n}{k}\) and \(\sum_{k=0}^{n} (-1)^k \binom{n}{k}\).
Apply the binomial formula with \(a = b = 1\): $$ 2^n = (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} 1^k = \sum_{k=0}^{n} \binom{n}{k}. $$ With \(a = 1, b = -1\), for \(n \ge 1\): $$ 0 = (1-1)^n = \sum_{k=0}^{n} \binom{n}{k} (-1)^k. $$
Method — Apply the binomial formula
For an expansion \((a+b)^n\): - read the binomial coefficients from Pascal's triangle (small \(n\)) or compute them by the factorial formula;
- write each term as \(\binom{n}{k} a^{n-k} b^k\) for \(k = 0, \dots, n\).
Skills to practice
- Applying and inverting Newton's formula
Jump to section