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?

Skip to content
# [Math] How to compute coefficients in Trinomial triangle at specific position

###### Related Question

exponentiationpolynomialspower series

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?

## Best Answer

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