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

Master Combinatorics with Mathbee

Practice this topic under real exam conditions with strict timers, or ask our AI Mentor to explain the concepts step-by-step.

Start Practicing for Free