Combinatorics
Binomial Coefficients
MJAT None
Grade 12
Question:
For nonnegative integers $s$ and $r$, let $\binom{s}{r} = \begin{cases} \frac{s!}{r!(s-r)!} & \text{if } r \leq s, \\ 0 & \text{if } r > s. \end{cases}$ For positive integers $m$ and $n$, let $g(m, n) = \sum_{p=0}^{m+n} \frac{f(m, n, p)}{\binom{n+p}{p}}$, where for any nonnegative integer $p$, $f(m, n, p) = \sum_{i=0}^{p} \binom{m}{i} \binom{n+i}{p} \binom{p+n}{p-i}$. Then which of the following statements is/are TRUE?
A) $g(m, n) = g(n, m)$ for all positive integers $m, n$
B) $g(m, n+1) = g(m+1, n)$ for all positive integers $m, n$
C) $g(2m, 2n) = 2 g(m, n)$ for all positive integers $m, n$
D) $g(2m, 2n) = (g(m, n))^2$ for all positive integers $m, n$
Step-by-Step Solution
Key Concept: Use Vandermonde’s convolution to collapse the inner sum, then rewrite the rational factors as shifted binomial coefficients so that a second Vandermonde (Chu–Vandermonde) evaluates the outer sum.
1. **Simplify $f(m, n, p)$ using binomial identities**:
$$f(m, n, p) = \sum_{i=0}^{p} \binom{m}{i} \binom{n+i}{p} \binom{p+n}{p-i}$$
Using the product identity $\binom{n+i}{p} \binom{p+n}{p-i} = \binom{n+p}{p} \binom{n+i}{p-i} = \binom{n+p}{p} \binom{n+i}{n}$, we factor out the term independent of $i$:
$$f(m, n, p) = \binom{n+p}{p} \sum_{i=0}^{p} \binom{m}{i} \binom{n+i}{n}$$
By Vandermonde's convolution (Chu-Vandermonde identity), the sum simplifies to:
$$\sum_{i=0}^{p} \binom{m}{i} \binom{n+i}{i} = \binom{m+n}{p}$$
Therefore, we have the simplified closed form:
$$f(m, n, p) = \binom{n+p}{p} \binom{m+n}{p}$$
2. **Calculate $g(m, n)$**:
Substitute $f(m, n, p)$ into $g(m, n)$:
$$g(m, n) = \sum_{p=0}^{m+n} \frac{\binom{n+p}{p} \binom{m+n}{p}}{\binom{n+p}{p}} = \sum_{p=0}^{m+n} \binom{m+n}{p}$$
Using the binomial theorem sum identity $\sum_{p=0}^{k} \binom{k}{p} = 2^k$ (where $k = m+n$):
$$g(m, n) = 2^{m+n}$$
3. **Verify the options**:
- **Option A**: $g(m, n) = 2^{m+n}$ is symmetric in $m$ and $n$, so $g(m, n) = g(n, m)$ is **TRUE**.
- **Option B**: $g(m, n+1) = 2^{m+n+1}$ and $g(m+1, n) = 2^{m+n+1}$, so $g(m, n+1) = g(m+1, n)$ is **TRUE**.
- **Option C**: $g(2m, 2n) = 2^{2m+2n}$, while $2g(m, n) = 2 \cdot 2^{m+n} = 2^{m+n+1}$. These are not equal generally, so **FALSE**.
- **Option D**: $g(2m, 2n) = 2^{2m+2n} = (2^{m+n})^2 = (g(m, n))^2$, so **TRUE**.
4. **Conclusion**:
The correct options are A, B, and D.
Correct Answer: A, B, D