Find the the coefficient of $\,x^r\,$ in $\,(1+x+x^2)^n$

Question

I want to be able to explicitly write it as $a_r = \dots $

When using multinomial theorem, I'm getting stuck at 2 conditions, but I'm not able to simplify from there.

I wrote $(1+x+x^2)^n =\displaystyle \sum_{a,b,c}^{a+b+c=n}\frac{n!}{a!b!c!}(1)^a(x)^b(x^2)^c = \frac{n!}{a!b!c!}x^{b+2c} $

so my conditions are $b+2c=r$ and $a+b+c=n$, how do I proceed from here?

Edit: Since in this particular case, we are able to write $ (1+x+x^2)^n = \displaystyle(\frac{1-x^3}{1-x})^n$, how can we do it for any random multinomial like $(1+3x+7x^2)^n $?

Answer 1

Guide:

One possible way\begin{align} (1+x+x^2)^n &= \left(\frac{1-x^3}{1-x}\right)^n \\ &= (1-x^3)^n (1-x)^{-n} \end{align}

Try to find the expansion for each term.

Answer 2

First, observe that $$ x^2+x+1=(x+w)(x+\overline{w}) $$ where $w=\frac{1}{2}+\frac{i\sqrt{3}}{2}$. Thus $$ \sum_{r=0}^{2n}c_rx^r=(x^2+x+1)^n=(x+w)^n(x+\overline{w})^n=\sum_{k=0}^n\binom{n}{k}x^kw^{n-k}\cdot \sum_{k=0}^n\binom{n}{\ell}x^\ell \overline{w}^{n-\ell} $$ and hence $$ c_r=\sum_{j=0}^r\binom{n}{j}\binom{n}{r-j}w^{n-j}\overline{w}^{\,n-(r-j)}=\sum_{j=0}^r\binom{n}{j}\binom{n}{r-j}w^{r-2j} $$ since $w\overline{w}=1$.

Answer 3

With respect to OP's edit: We can consecutively apply the binomial theorem in order to determine the coefficient of $x^r$. It is convenient to use the coeffcient of operator $[x^r]$ to denote the coefficient of $x^r$.

We obtain \begin{align*} \color{blue}{[x^r]}\color{blue}{(1+3x+7x^3)} &=[x^r]\sum_{j=0}^n\binom{n}{j}(3x+7x^2)^j\\ &=\sum_{j=0}^r\binom{n}{j}3^j[x^{r-j}]\left(1+\frac{7}{3}x\right)^j\tag{1}\\ &=\sum_{j=0}^r\binom{n}{j}3^j\binom{j}{r-j}\left(\frac{7}{3}\right)^{r-j}\tag{2}\\ &\,\,\color{blue}{=\sum_{j=0}^r\binom{n}{j}\binom{j}{r-j}7^{r-j}3^{2j-r}} \end{align*}

Comment:

• In (1) we factor out $(3x)^j$ and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$. We also set the upper bound of the sum to $r$ since the power of $x$ is non-negative.

• In (2) we select the coefficient of $[x^{r-j}]$.

Answer 4

$\,x^r\,$ in $\,(1+x+x^2)^n$

I see a combinatorics way, notice the zero set consists of $\omega$ and $\omega^2$ repeated $n$ times. Coefficient of $x^r=x^{2n-p}$ for some $p \in \mathbb{N}$. Now, this coefficient by Vieta's theorem is sum of all the ways we can take roots $p$ at a time with a minus power:

$$ \text{coeff} = ( \text{roots taken p at a time} )(-1)^p$$

Suppose we take $t$ copies of $\omega$ then we take $p-t$ copies of $\omega^2$, the contribution to the choice to the coefficient is:

$$ (-1)^p \binom{n}{t} \omega^t \binom{n}{p-t} \omega^{2p-2t}$$

This simplifies into:

$$ (-1)^p \omega^{-t+ 2p} \binom{n}{t} \binom{n}{p-t}$$

To get the total coefficient, we have to add up the terms:

$$ \text{coeff} = \left[ \sum_{t=0}^p \omega^{-t} \binom{n}{t} \binom{n}{p-t}\right] \omega^{2p} (-1)^p $$

---

Sanity check:

Suppose $n=1$,$r=1$ and $p=1$ then:

$$ \text{coeff}= \sum_{t=0}^1 \left[ \omega^{-t} \binom{1}{t}^2 \right] \omega^{2} (-1)^p=1$$

Answer 5

Here is an easier method to solve this without complex analysis:

$\left(1+x+x^{2}\right)^{n}=\left(\frac{1-x^{3}}{1-x}\right)^{n}=\left(1-x^{3}\right)^{n}(1-x)^{-n}$

Now,

$\begin{aligned}\left[x^{r}\right]\left(1+x+x^{2}\right)^{n} &=\left[x^{r}\right]\left(1-{ }^{n} C_{1} x^{3}+{ }^{n} C_{2} x^{6} -\ldots\right )(1-x)^{-n} \\ &=\left[x^{r}\right]\left(\sum_{k=0}^{n} { (-1)^k} \ ^{n} C_{k} x^{3 k}\right)(1-x)^{-n} \end{aligned}$

We also know that cofficient of $x^{n}$ in $(1-x)^{-r}$ is ${ }^{n+r-1} C_{r-1}$

$\begin{aligned} \therefore \ \left[x^{r}\right]\left(1+x+x^{2}\right)^{n} &=\sum_{k=0}^{n}(-1)^{k}\ { }^{n} C_{k}\left[x^{r-3 k}\right](1-x)^{-r} \\ \left[x^{r}\right]\left(1+x+x^{2}\right)^{n} &=\sum_{k=0}^{n}(-1)^{k}\ \ {}^{n} C_{k} \ { }^{n+r-3 k-1}C_{n-1} \end{aligned}$

Which is the required coefficient. You are welcome to do any sanity checks as desired.