Coefficient of $x^n$ in $(x^2+3x+2)^n$

Question

So I was doing a binomial coefficient sum problem, and was finally able to convert the sum into finding the coefficient of $x^n$ in $(x+1)^n(x+2)^n$ or equivalently $(x^2+3x+2)^n$. Now I am struggling to find the coefficient of $x^n$ in this expression. Would I have to resort to multinomial theorem? No other way? And even multinomial theorem's method doesn't seem obvious here. Kindly help.

Answer 1

As you already know, first express $(x^{2}+3x+2)=(x+2)(x+1)$. Then apply the binomial theorem, which results in $$[ \sum_{k=0}^{n}\binom{n}{k} x^{n} 2^{n-k}] [\sum_{k=0}^{n} \binom{n}{k} x^{n}]$$ For simplicity, write the entire expression out, so you have $$(x^{n}+ \binom{n}{n-1}x^{n-1} \cdot 2 + \cdot \cdot \cdot + 2^{n})(x^{n}+ \binom{n}{n-1}x^{n-1} + \cdot \cdot \cdot + 1)$$ The coefficient of $x^{n}$ will be the sum of the coefficients of the different combinations of the power of $x$'s that results in $n$, therefore, it would be the first term of the first expansion multiplied to the last term of the second expansion and so forth. The resulting coefficient would be in the form of $$1 + \binom{n}{n-1} \binom{n}{1} \cdot 2+ \binom{n}{n-2} \binom{n}{2} \cdot 2^{2} + \cdot \cdot \cdot + \binom{n}{n-n}\binom{n}{n} 2^{n}$$ and since $\binom{n}{k}=\binom{n}{n-k}$, it becomes $$1 + (\binom{n}{1})^{2} \cdot 2 + \cdot \cdot \cdot + 2^{n}$$, which written in compact form yields $$\sum_{k=0}^{n} (\binom{n}{k})^{2}2^{k}$$ Correct me if I'm wrong, thank you