5
$\begingroup$

I need to compute coefficients of $i$-th power of $x$ from simplifying of $(x^2 + x + 1)^n$ From that site i know about trinomial triangle.

But how can compute coeficients of $i$-th element at $n$-th row without computing all upper elements?

2 Answers 2

4

Denote by $\sum_{k=0}^{m(s-1)}{\binom{m}{k}}_{s}x^{k}=(1 + x + ... + x^{s-1})^{m}\,$ the expansion of multinomial of degree $s-1$

From that relation follow that

$ \sum_{k=0}^{m(s-1)}{\binom{m}{k}}_{s}x^{k}=\sum_{k=0}^{\infty}{\binom{m}{k}}_{s}x^{k}=\left(\frac{1-x^{s}}{1-x}\right)^{m}=(1-x^{s})^{m}(1-x)^{-m}\,$

from binomial formula we have

$(1-x^{s})^{m}=\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}x^{si}$

and from Taylor formula

$(1-x)^{-m}=\sum_{j=0}^{\infty}\binom{m+j-1}{j}x^{j}$

after substitutions we get

$ \sum_{k=0}^{\infty}{\binom{m}{k}}_{s}x^{k}=\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}x^{si}\sum_{j=0}^{\infty}\binom{m+j-1}{j}x^{j}=$

$=\sum_{j=0}^{\infty}\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}\binom{m+j-1}{j}x^{si+j}=$

$ =\sum_{k=0}^{\infty}\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}\binom{m+k-si-1}{k-si}x^{k}\,$

for $si+j=k$ follow that $j=k-si$ then equate the coefficients next to x follow formula

${\binom{m}{k}}_{s}=\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}\binom{m+k-si-1}{m-1}\,$

put $s=3$ you get what you ask

2

These are known as Gegenbauer polynomials. Specifically

$ (x^2+x+1)^n = \sum_{m=0}^\infty C_m^{(-n)}(-\frac{1}{2}) x^m $

This follows directly from generating function for these polynomials. There is also an explicit sum representation on that wikipedia page.

Also this sequence is known as trinomial coefficient, and typically denoted $T(n,m)$. See MathWorld for example.

  • 0
    For computational purposes, it's better to use the three-term recurrence than to use the explicit sum representation, which is rather cancellation-prone.2011-08-13