# Find the $x^n$ coefficient of $(1+x+x^2)^n$

I've tried a bunch of different groupings of the three terms so that I could use the binomial expansion forumula, but I haven't been able to go much further than that. This is an example of what I've tried so far: $$(1+x+x^2)^n=\sum_{n=0}^{\infty} {n \choose k}(1+x)^{n-k}x^{2k} =\sum_{k=0}^{\infty}\sum_{i=0}^{\infty}{n \choose k}{{n-k} \choose i}x^{2k+i}$$

I decided to show this as it has the closest looking coefficient to the expected answer, which states that the coefficient of $$x^n$$ is $$\sum_{k=0}^{n}{n \choose k}{{n-k} \choose k}$$. I'm assuming I'm taking the wrong approach so I'd appreciate some input.

• This is OEIS A002426 Commented Oct 1, 2021 at 15:49

The terms that contribute to the coefficient on $$x^n=x^{2k+i}$$ can be thought of summing over the ways of writing $$n$$ as $$2k+i=n$$,

$$\sum_{2k+i=n} \binom{n}{k}\binom{n-k}{i}$$

Since $$i=n-2k$$ we can replace it in the binomial term $$\binom{n-k}{i}=\binom{n-k}{n-2k}=\binom{n-k}{n-k-(n-2k)}=\binom{n-k}{k}$$,

$$\sum_{2k+i=n} \binom{n}{k}\binom{n-k}{k}$$

The terms of the sum no longer have any dependence on $$i$$, so we can fixate on what values of $$k$$ are valid. Every choice of $$k$$ will automatically have a unique choice of $$i$$ that make $$n$$, if $$n$$ is even we can go all the way up to $$2(\frac{n}{2})+0=n$$ and if $$n$$ is odd we can go all the way up to $$2(\frac{n-1}{2})+1=n$$, so $$k$$ goes up to $$\lfloor \frac{n}{2}\rfloor$$,

$$\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{k}\binom{n-k}{k}$$

Essentially you want as many $$1$$s as $$x^2$$s, but not more than $$\frac n2$$ of either

If you have $$k$$ of $$1$$s and $$k$$ of $$x^2$$s then you also have $$n-2k$$ of $$x$$s and these can be in any order so I would have written

$$\sum\limits_{k=0}^{\lfloor n/2 \rfloor} \frac{n!}{k!^2(n-2k)!}=\sum\limits_{k=0}^{\lfloor n/2 \rfloor} {n \choose k}{n-k \choose k}$$

As Mike Earnest has observed, this is the same as the expected answer since for larger $$k$$ you have $${n-k \choose k}=0$$

• Both you and OP have the correct upper bound; OP's extra terms are zero. Commented Oct 1, 2021 at 16:06
• @MikeEarnest - that is helpful as I could not see an error Commented Oct 1, 2021 at 16:09

Hint: There is no closed formula available for $$\sum_{k=0}^{n}{n \choose k}{{n-k} \choose k}$$

In fact it can be shown that \begin{align*} [x^n](a+bx+cx^2)^n=[x^n]\frac{1}{\sqrt{1-2bx+(b^2-4ac)x^2}} \end{align*} has a closed form solution if and only if $$abc(b^2-4ac)=0$$

In case of central trinomial coefficients we have $$a=b=c=1$$. Since then the expression $$\color{blue}{abc(b^2-4ac)=-3\ne 0}$$ there is no such closed form for the central trinomial coefficients.

A somewhat more detailed information is given in this answer.

This is same as the number of ways we can distribute $$n$$ balls among $$n$$ kids such that each receive $$0,1$$ or $$2$$ balls. Suppose $$a$$ kids receive $$1$$ ball and $$b$$ kids receive $$2$$ balls then there are $$n-a-b$$ kids who does not recieve a ball. $$a+2b=n$$ because the total number of balls is $$n$$ .

You can choose $$b$$ kids out of $$n$$ kids to give $$2$$ balls and $$a$$ balls out of the remaing $$n-b$$ kids to give $$1$$ ball.
This same as $${n \choose b}{n-b \choose a}={n \choose b}{n-b \choose n-2b}={n \choose b}{n-b \choose b}$$
$$0\le b\le\lceil n/2\rceil$$ so the total number of ways is $$\sum_{i=0}^{\lceil n/2\rceil}{n \choose b}{n-b \choose b}$$

For another way , let say that $$(1+x+x^2)^n= \bigg(\frac{1-x^3}{1-x} \bigg)^n$$

Then , it is obvious that $$\bigg(\frac{1-x^3}{1-x} \bigg)^n = (1-x^3)^n \times \bigg(\frac{1}{1-x} \bigg)^n$$

We can conclude that we obtain two $$x$$ values from this expression and the summation of their exponentials will be equal to $$n$$. So , lets say that our exponential coming from $$(1-x^3)^n$$ is equal to $$3m$$ (because $$x^3$$ gives always the exponentials which are multiplications of $$3$$ , and exponential coming from $$\bigg(\frac{1}{1-x} \bigg)^n$$ is equal to $$k$$. Then , $$3m+k=n$$..

We can see that $$\binom{n}{m}(-1)^m(x^{3m})\times \binom{n+k-1}{k}x^k$$ where $$3m+k=n$$

The bad aspect of this approach , you should see the all solutions for $$m$$ and $$k$$.However ,it is good for small numbers.For example , lets assume that $$n=5$$ , then $$(m=0,k=5)$$ or $$(m=1 , k=2)$$

In that cases ,

• If $$(n=5,m=0,k=5)$$ then $$\binom{5}{0}(-1)^0 \times \binom{5+5-1}{5}=126$$

• If $$(n=5,m=1,k=2)$$ then $$\binom{5}{1}(-1)^1 \times \binom{5+2-1}{2}=-75$$

Then , $$126+(-75)=51$$

CALCULATION BY WOLFRAM-ALPHA