Counting and Combinatorial Identities

$\binom {n}{k} = \binom {n}{n-k}$.

Find the sum $\binom {n}{0} + \ldots + \binom {n}{n}$.

Pascal's rule. $\binom {n+1}{k+1} = \binom {n}{k+1} + \binom {n}{k}$ if $0 \leqslant k \leqslant n-1$.

\begin{Bmatrix} \end{Bmatrix} n+1 \\ k+1 \end{Bmatrix} = (k+1)\begin{Bmatrix} \end{Bmatrix} n \\ k+1 \end{Bmatrix} + \begin{Bmatrix} \end{Bmatrix} n \\ k \end{Bmatrix}. Here \begin{Bmatrix} \end{Bmatrix} n \\ k \end{Bmatrix} is the number of partitions of an $n$-element set into $k$ parts (i.e. nonempty subsets); partitions are considered unordered, i.e. the partition of the set $\{ 1,2,3\}$ into the parts $\{ 1,2\}$ and $\{ 3\}$ and the partition of the same set into the parts $\{ 3\}$ and $\{ 1,2\}$ are considered the same. Cf. Problem 1.4.7(5).

How many subsets of the set $\mathscr {R}_{11}$ contain no two consecutive numbers?

The same for three consecutive numbers.

$\binom {n}{k} = \dfrac {n!}{k!(n-k)!} = \dfrac {n(n-1)\ldots (n-k+1)}{k!}$.

The binomial theorem. $(a+b)^n = \displaystyle \sum_{j=0}^{n}\binom {n}{j}a^jb^{n-j}$.

$\binom {n}{0} - \binom {n}{1} + \ldots + (-1)^n\binom {n}{n}$;

$\binom {n}{0} + \dfrac {1}{2}\binom {n}{1} + \dfrac {1}{3}\binom {n}{2} + \ldots + \dfrac {1}{n+1}\binom {n}{n}$;

$\binom {n}{1} + 2\binom {n}{2} + 3\binom {n}{3} + \ldots + n\binom {n}{n}$;

$\binom {n}{k} + \binom {n+1}{k+1} + \ldots + \binom {n+m}{k+m}$;

$\binom {n}{0}^2 + \ldots + \binom {n}{n}^2$;

$\binom {n}{0}\binom {m}{k} + \binom {n}{1}\binom {m}{k-1} + \ldots + \binom {n}{k}\binom {m}{0}$;

$\binom {2n}{0} - \binom {2n-1}{1} + \binom {2n-2}{2} - \ldots + (-1)^n\binom {n}{n}$;

$\binom {2n}{n} + 2\binom {2n-1}{n} + 4\binom {2n-2}{n} + \ldots + 2^n\binom {n}{n}$.

Find $\displaystyle \sum_{k \geqslant 0}\binom {n}{2k}$.

Find $\displaystyle \sum_{k \geqslant 0}\binom {n}{4k}$.

Find $\displaystyle \sum_{k \geqslant 0}\binom {n}{3k}$.