Finding the Coefficient of (1+x+x^2)^n

[Harmony]

I need to find a formula that describe the sequence shown above. (The sequence is highlighted.) I am aware that the sequence is the coefficient of the polynomial (1+x+x^2)^n, and have tried using Taylor's expansion. Still, I can't get a nice formula that describe the sequence.

Any help/hint is appreciated. Thanks in advanced.

 

[micromass]

Try the multinomium theorem

(x_1+x_2+x_3)^n=\sum_{k_1+k_2+k_3=n}{\binom{n}{k_1,k_2,k_3}x_1^{k_1}x_2^{k_2}x_3^{k_3}}

Where \binom{n}{k_1,k_2,k_3}=\frac{n!}{k_1!k_2!k_3!}

 

[Harmony]

I have looked into it as well. The formula doesn't express the function in terms of x^k alone, and i have problem converting the expression...

 

[micromass]

So the multinomium says that

(1+x+x^2)^n=\sum_{k+l\leq n}{\binom{n}{k,l,n-k-l}x^{k+2l}}

So if we express the right hand theorem in the usual form, then we have

(1+x+x^2)^n=\sum_{i=0}^{2n}{\left(\sum_{l=\max\{0,i-n\}}^{[i/2]}{\binom{n}{i-2l,l,n-i+l}}\right)x^i}

So the coefficients, you look for, would be

\sum_{l=i-n}^{[i/2]}{\binom{n}{i-2l,l,n-i+l}}

I hope I didn't miscalculate...

I know this isn't really the nice answer you were looking for. But I don't know any better answers...

 

[Harmony]

I am fine with that expression. The only thing is I don't quite understand the derivation (like how you express the right hand theorem). Or maybe I am just being too sleepy..:)

 

[micromass]

So we know that

(1+x+x^2)^n = \sum_{0\leq k+l\leq n}{\binom{n}{k,l,n-k-l}x^{k+2l}}

Let's say that we wish to find the coefficient of x^i. Then we need to find all k and l such that 0\leq k+l \leq n and such that k+2l=i. The term of x^i would then be

\sum_{0\leq k+l\leq n, k+2l=i}{\binom{n}{k,l,n-k-l}}

This would already be good. But if you want, you can write the sum with one parameter l. Just use that k+2l=i (and thus k=i-2l). The multinomial coefficients that yield \binom{n}{i-2l,l,n-i+l}. The hardest part is determining the range of l...