# coefficient of $x^{17}$ in the expansion of $(1+x^5+x^7)^{20}$

I found this questions from past year maths competition in my country, I've tried any possible way to find it, but it is just way too hard.

find the coefficient of $x^{17}$ in the expansion of $(1+x^5+x^7)^{20}$

(A)3400 (B)3410 (C)3420 (D)3430 (E)3440

so it would be $$x^{140} + ...... + 1$$

This requires binomial theorem and Multinomial theorem, but I'm not sure how to calculate it. Any tips or formula would be appreciate.

• Hint: The only way to produce $17$ as a sum of 5's and 7's is as $5+5+17$. So you need to assign two $x^5$s and one $x^7$ among the 20 factors. – Henning Makholm Jul 27 '15 at 15:18
• "I found this questions from past year maths competition in my country, I've tried any possible way to find it, but it is just way too hard." You really may not include this preamble in any question. – Michael Galuza Jul 27 '15 at 15:19

Usage of the multinomial coefficient $(k_1, k_2, \cdots, k_n)$!:

$$\big( 1 + x^5 + x^7\big)^{20} = \sum_{k_1=1}^{20} \sum_{k_2=1}^{20-k_1} (k_1, k_2, 20 - k_1 - k_2)! x^{5k_1} x^{7k_2},$$

where

$$(k_1, k_2, \cdots, k_n)! = \frac{ (k_1 + k_2 + \cdots + k_n )! } { k_1! k_2! \cdots k_n!}.$$

So we get $k_1=2$ and $k_2=1$, thus

$$(2,1,17)! = \frac{(2+1+17)!}{ \begin{array} {ccc}2! & 1! & 17!\\ \downarrow & \downarrow & \downarrow\\ 2 \times 5 & 1 \times 7 & 17 \times 0 \end{array} } = 3420.$$

[change in order due to comment of @Henning Makholm]

• For consistency with your first formula you should be speaking abouth $(2,1,17)!$ rather than $(17,2,1)!$. – Henning Makholm Jul 27 '15 at 16:05
• That would be nicer indeed. But there is symmetry in the coefficients... I changed it in the answer. – johannesvalks Jul 27 '15 at 16:20

$17$ can only be obtained by using two $5$s and one $7$ . These two $5$s can be obtained in $\binom{20}2$ ways which is $190$ and the $7$ can be got in from one of the remaining 18 brackets. So $190$ x $18$ = $3420$ is the answer.

$$(1 + x^5 + x^7)^{20}$$

That intuitively is just

$$((1 + x^5) + x^7) \times ((1 + x^5) + x^7) \times ((1 + x^5) + x^7) ...$$

Which can be expanded out term by term. By the Binomial Theorem as

$$(1 + x^5)^{20} (x^7)^0 + \begin{pmatrix} 20 \\ 1\end{pmatrix}(1 + x^5)^{19}x^7 + \begin{pmatrix} 20 \\ 2\end{pmatrix}(1 + x^5)^{18}x^{14} ...$$

Now we can take each of the $$(1 + x^5)$$ terms and expand them as well.

Note that the number 17 can be expressed as sum in terms of multiples of 5 and 7 as

$$10 + 7$$

If we consider say $15$ in the sum it's too big, and same for $14$ likewise arguments can be made to show that $5$ by itself won't add to a positive multiple of 7 to make 17.

So that means every power of 17 is contained in the term

$$\begin{pmatrix} 20 \\ 1\end{pmatrix}(1 + x^5)^{19}x^7$$

Of our binomial expression. We need to find the coefficient of $x^{10}$ in

$$(1 + x^5)^{19}$$

Call that C. Then

$$C \begin{pmatrix} 20 \\ 1\end{pmatrix}$$ Is the answer.

By Binomial Theorem:

$$(1 + x^5)^{19} = 1 + \begin{pmatrix} 19 \\ 1\end{pmatrix}x^5 + \begin{pmatrix} 19 \\ 2\end{pmatrix}x^{10} ...$$

So then $C = \begin{pmatrix} 19 \\ 2\end{pmatrix}$

$$\begin{pmatrix} 19 \\ 2\end{pmatrix} \begin{pmatrix} 20 \\ 1\end{pmatrix}$$

To get more advanced techniques (it is worthwhile to take a look at the multinomial theorems). They generalize these ideas for arbitrarily large sums raised to integer powers like the binomial theorem for 2 elements raised to a power.

Note that

$$\begin{pmatrix} 19 \\ 2\end{pmatrix} \begin{pmatrix} 20 \\ 1\end{pmatrix} = \frac{19!}{2!17!} 20 = 19 \times 9 \times 20 = 3420$$

$(1+x^5+x^7)^{20}=\{(1+x^5)+x^7\}^{20}$

$=(1+x^5)^{20}+\binom{20}1(1+x^5)^{20-1}(x^7)^1+\binom{20}2(1+x^5)^{20-2}(x^7)^2+\cdots+(x^7)^{20}$

So the required sum will be

the coefficient of $x^{17}$ in $(1+x^5)^{20}$

$+\binom{20}1\cdot$ the coefficient of $x^{17-7}$ in $(1+x^5)^{20-1}$

$+\binom{20}2\cdot$ the coefficient of $x^{17-7\cdot2}$ in $(1+x^5)^{20-2}$

Clearly the exponent of $x$ in $(1+x^5)^n$ will be divisible by $5$

So, the first & the last summand must be zero

Now for the coefficient of $x^{17-7\cdot1}$ in $(1+x^5)^{20-1},$

the $r+1$th term $\binom{19}r(x^5)^r=\binom{19}rx^{5r}$ and we need $5r=10\iff r=?$