# Upper bounding n choose k

We want to show that for $1\leq k\leq n$, the following holds: ${n\choose k} \leq \Big(\frac{n\cdot e}{k}\Big)^k.$

First, recall the power series $e^k=\sum_{i=0}^\infty{\frac{k^i}{i!}}$. For $k \geq 1$, this sum is definitely larger than its $k$th term only. In other words, $e^k \geq k^k/k!$, which implies $k! \geq (k/e)^k$. Now,

$\begin{matrix}{n\choose k} &=& \frac{n!}{k! \cdot (n-k)!}\\ &=& \frac{n(n-1)(n-2)\cdots (n-(k-1))}{k!}\\ &\leq& \frac{n^k}{k!} \\ &\leq& \frac{n^k}{(k/e)^k} \\ &=& (\frac{en}{k})^k.\\ \end{matrix}$

This proof is extracted from the StackExchange discussion here. For more inequalities/bounds for binomial coefficients, see Wikipedia.

# Stirling Numbers of First and Second Kind: A Combinatorial Explanation of the Recursive Definitions

Stirling Numbers (of the first and second kind) are famous in combinatorics. There are well known recursive formulas for them, and they can be expressed through generating functions. Below we mention and explain the recursive definitions of the Stirling numbers through combinatorial ideas.

Since the Stirling numbers of the second kind are more intuitive, we will start with them.

# Proofs from the Book

This book, inspired from Paul Erdős‘ notion of the Book, presents some beautiful proofs to some intriguing math problems. Both the problems and proofs presented here are elegant, clear, and artistic.