Paragraph

\(2^n\) is the number of lattice paths which have length \(n\text{,}\) since for each step you can go up or right. Such a path would end along the line \(x + y = n\text{.}\) So you will end at \((0,n)\text{,}\) or \((1,n-1)\) or \((2, n-2)\) or … or \((n,0)\text{.}\) Counting the paths to each of these points separately, give \({n \choose 0}\text{,}\) \({n \choose 1}\text{,}\) \({n \choose 2}\text{,}\) …, \({n \choose n}\) (each time choosing which of the \(n\) steps to be to the right). These two methods count the same quantity, so are equal.

in-context