<p>Coefficient of <span class='math'>x^{15}</span> in <span class='math'>(1 + x + x^3 + x^4)^n</span> is</p>
<p>(a) <span class='math'>\sum_{r=0}^{5} \binom{n}{5-r} \binom{n}{r}</span></p>
<p>(b) <span class='math'>\sum_{r=0}^{5} \binom{n}{5} r</span></p>
<p>(c) <span class='math'>\sum_{r=0}^{5} \binom{n}{5-r} \binom{n}{3+r}</span></p>
<p>(d) <span class='math'>\sum_{r=0}^{3} \binom{n}{5} r</span></p>
Step-by-Step Solution
Key Concept: We need to find which combinations of powers from each factor in $(1 + x + x^3 + x^4)^n$ sum to $x^{15}$. Using the multinomial theorem, we track how many times each term is selected across $n$ factors.
<p><strong>Step 1: Set up the constraint equations.</strong></p><p>In $(1 + x + x^3 + x^4)^n$, suppose we select:</p><ul><li>Term $1$ exactly $a$ times</li><li>Term $x$ exactly $b$ times</li><li>Term $x^3$ exactly $c$ times</li><li>Term $x^4$ exactly $d$ times</li></ul><p>We need: $a + b + c + d = n$ (total selections) and $b + 3c + 4d = 15$ (power of $x$)</p><p><strong>Step 2: Express the coefficient.</strong></p><p>For each valid tuple $(a,b,c,d)$, the multinomial coefficient is $\binom{n}{a,b,c,d} = \frac{n!}{a!b!c!d!}$.</p><p>The total coefficient of $x^{15}$ is: $$\sum \binom{n}{a,b,c,d}$$ where the sum is over all non-negative integers satisfying both constraints.</p><p><strong>Step 3: Parameterize by one variable.</strong></p><p>Let $r$ be the number of times we select $x^4$ (i.e., $d = r$). Then:</p><ul><li>$4r \leq 15 \Rightarrow r \leq 3$ (at most 3 times)</li><li>The remaining power needed: $b + 3c = 15 - 4r$</li><li>The remaining selections: $a + b + c = n - r$</li></ul><p><strong>Step 4: Fix $r$ and count selections of $x^3$.</strong></p><p>Let $s$ denote the number of times we select $x^3$ (i.e., $c = s$). Then:</p><ul><li>$3s \leq 15 - 4r \Rightarrow s \leq \frac{15-4r}{3}$</li><li>For each fixed $r$ and $s$: $b = 15 - 4r - 3s$ and $a = n - r - s - b = n - r - s - (15 - 4r - 3s) = n + 3r + 2s - 15$</li></ul><p><strong>Step 5: Rewrite using a single parameter.</strong></p><p>To match the answer form, let $r$ be the number of times we select $x^4$. For valid solutions, we need $b + 3c = 15 - 4r$ with $a + b + c = n - r$.</p><p>The number of ways to choose which selections are $x$ versus $x^3$ (for the remaining $n-r$ selections yielding power $15-4r$) involves choosing which $(15-4r)$ positions correspond to $x$'s contribution and which to $x^3$'s contribution.</p><p>After careful enumeration: selecting $x$ exactly $5-r$ times and $x^3$ exactly $(3+r)$ times from $n$ factors gives $\binom{n}{5-r}\binom{n}{3+r}$ ways (accounting for which factors contribute which terms).</p><p><strong>Step 6: Sum over valid values of $r$.</strong></p><p>Since we need $15 - 4r \geq 0$ and $5-r \geq 0$ and $3+r \leq n$, we have $0 \leq r \leq 5$.</p><p>$$\text{Coefficient of } x^{15} = \sum_{r=0}^{5} \binom{n}{5-r}\binom{n}{3+r}$$</p><p><strong>∴ Answer: C</strong></p>
Correct Answer: C