Combinatorial arguments are among the most beautiful in all of mathematics. Oftentimes, statements that can be proved by other, more complicated methods (usually involving large amounts of tedious algebraic manipulations) have very short proofs once you can make a connection to counting. In this section, we introduce a new way of thinking about combinatorial problems with several examples. Our goal is to help you develop a “gut feeling” for combinatorial problems.

##### Example2.13

Let $n$ be a positive integer. Use Figure 2.14 to explain why

\begin{equation*} 1+2+3+\dots+n=\frac{n(n+1)}{2}. \end{equation*}
Solution
##### Example2.15

Let $n$ be a positive integer. Explain why

\begin{equation*} 1+3+5+\dots+2n-1=n^2. \end{equation*}
Solution
##### Example2.17

Let $n$ be a positive integer. Explain why

\begin{equation*} \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\dots+\binom{n}{n}=2^n. \end{equation*}
Solution
##### Example2.18

Let $n$ and $k$ be integers with $0\le k\lt n\text{.}$ Explain why

\begin{equation*} \binom{n}{k+1} = \binom{k}{k} + \binom{k+1}{k} + \binom{k+2}{k} +\dots+ \binom{n-1}{k}. \end{equation*}
Solution
##### Example2.19

Explain the identity

\begin{equation*} 3^n=\binom{n}{0}2^0+\binom{n}{1}2^1+\binom{n}{2}2^2+ \dots+\binom{n}{n}2^n. \end{equation*}
Solution
##### Example2.20

Explain why, for each non-negative integer $n\text{,}$

\begin{equation*} \binom{2n}{n}= {\binom{n}{0}}^2+{\binom{n}{1}}^2+{\binom{n}{2}}^2+\dots+ {\binom{n}{n}}^2. \end{equation*}
Solution