Induction & Combinatorics

Mathematical induction is a proof technique for statements $P(n)$ that depend on a natural number $n$. It consists of two steps:

1. Base case: prove that $P(1)$ (or $P(n_0)$ for the smallest relevant $n$) is true.
2. Inductive step: assume $P(k)$ holds for an arbitrary $k\geq n_0$ (inductive hypothesis) and prove that $P(k+1)$ follows from it.

If both steps are verified, by induction $P(n)$ holds for all $n\geq n_0$.

Example — sum of first $n$ naturals: prove $S(n)=\sum_{i=1}^n i = n(n+1)/2$.

• Base $n=1$: $S(1)=1 = 1\cdot2/2$. True.
• Inductive step: assume $S(k)=k(k+1)/2$. Then $S(k+1)=S(k)+(k+1)=k(k+1)/2+(k+1)=(k+1)(k+2)/2$. True.

Bernoulli inequality: for $x\geq-1$ and $n\in\mathbb{N}$, $(1+x)^n \geq 1+nx$. Proved by induction (base $n=0$, inductive step uses $(1+x)^{k+1}=(1+x)^k(1+x)$).

The binomial coefficient $${n \choose k}$$ counts the number of ways to choose $k$ elements from a set of $n$ (order irrelevant):

$${n \choose k} = C(n,k) = \frac{n!}{k!(n-k)!}, \qquad 0\leq k\leq n.$$

Properties: symmetry $${n \choose k}={n \choose n-k}$$; Pascal's identity $${n \choose k}+{n \choose k+1}={n+1 \choose k+1}$$.

Pascal's triangle: each entry is the sum of the two above it. Row $n$ contains the coefficients $${n \choose 0},{n \choose 1},\dots,{n \choose n}$$.

Newton's binomial theorem:

$$(a+b)^n = \sum_{k=0}^n {n \choose k} a^{n-k} b^k.$$

Key identity: $$\sum_{k=0}^n {n \choose k} = 2^n$$ (set $a=b=1$).

Arithmetic progression: a sequence where each term differs from the previous by a constant $d$: $a_k = a_1 + (k-1)d$.

$$\sum_{k=1}^n a_k = \frac{n(a_1+a_n)}{2} = \frac{n[2a_1+(n-1)d]}{2}.$$

Geometric progression: a sequence where each term is obtained by multiplying the previous by a constant $q$: $a_k = a_1 q^{k-1}$.

$$\sum_{k=1}^n a_k = a_1\frac{1-q^n}{1-q} \qquad (q\neq1).$$

If $|q|<1$, the infinite geometric series converges: $$\sum_{k=0}^\infty a_1 q^k = \frac{a_1}{1-q}.$$

Useful identities:

• $\sum_{k=1}^n k = n(n+1)/2$
• $\sum_{k=1}^n k^2 = n(n+1)(2n+1)/6$
• $\sum_{k=1}^n k^3 = [n(n+1)/2]^2$