Recent questions tagged counting

Use question $33$ to prove the hockeystick identity from question $27.$ [Hint: First, note that the number of paths from $(0, 0)\: \text{to}\: (n + 1,r)$ equals $\binom{n...

Use question $33$ to prove Pascal’s identity. [Hint: Show that a path of the type described in question $33$ from $(0, 0)\: \text{to}\: (n + 1 − k, k)$ passes through eit...

Use question $33$ to prove Theorem $4.$ [Hint: Count the number of paths with n steps of the type described in question $33.$ Every such path must end at one of the point...

Use question $33$ to give an alternative proof of Corollary $2$ in Section $6.3,$ which states that $\binom{n}{k} = \binom{n}{n−k} $ whenever $k$ is an integer with $0 \l...

In this exercise we will count the number of paths in the $xy$ plane between the origin $(0, 0)$ and point $(m, n),$ where $m$ and $n$ are nonnegative integers, such that...

Prove the binomial theorem using mathematical induction.

Show that a nonempty set has the same number of subsets with an odd number of elements as it does subsets with an even number of elements.

Give a combinatorial proof that $\displaystyle{}\sum_{k = 1}^{n} k \binom{n}{k}^{2} = n \binom{2n−1}{n−1}.$ [Hint: Count in two ways the number of ways to select a commit...

Give a combinatorial proof that $\displaystyle{}\sum_{k = 1}^{n} k \binom{n}{k} = n2^{n−1}.$ [Hint: Count in two ways the number of ways to select a committee and to then...

Show that if $n$ is a positive integer, then $\binom{2n}{2} = 2\binom{n}{2} + n^{2} $ using a combinatorial argument. by algebraic manipulation.

Prove the hockeystick identity $\displaystyle{}\sum_{k=0}^{r} \binom{n + k}{k} = \binom{n + r + 1}{r}$ whenever $n$ and $r$ are positive integers, using a combinatorial a...

Let $n$ and $k$ be integers with $1 \leq k \leq n.$ Show that $\displaystyle{}\sum_{k=1}^{n} \binom{n}{k}\binom{n}{k − 1} = \dfrac{\binom{2n + 2}{n + 1}}{2} − \binom{2n}{...

Show that if $p$ is a prime and $k$ is an integer such that $1 \leq k \leq p − 1,$ then $p$ divides $\binom{p}{k} .$

Show that if $n$ and $k$ are positive integers, then $\binom{n + 1}{k} = \dfrac{(n + 1)\binom {n}{k – 1}}{k}.$ Use this identity to construct an inductive definition of t...

Prove the identity $\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n−k}{r−k} ,$ whenever $n, r,$ and $k$ are nonnegative integers with $r \leq n$ and $k \leq r,$using a co...

Prove that if $n$ and $k$ are integers with $1 \leq k \leq n,$ then $k \binom{n}{k} = n \binom{n−1}{k−1},$using a combinatorial proof. [Hint: Show that the two sides of t...

Suppose that $k$ and $n$ are integers with $1 \leq k<n.$ Prove the hexagon identity $\binom{n-1}{k-1}\binom{n}{k+1}\binom{n+1}{k} = \binom{n-1}{k}\binom{n}{k-1}\binom{n+1...

Prove Pascal’s identity, using the formula for $\binom{n}{r}.$

Show that if $n$ and $k$ are integers with $1 \leq k \leq n,$ then $\binom{n}{k} \leq \frac{n^{k}}{2^{k−1}}.$

Show that $\binom{n}{k} \leq 2^{n}$ for all positive integers $n$ and all integers $k$ with $0 \leq k \leq n.$