Introduction to generating functions through the Binomial Theorem
Pt En Qual é o coeficiente de $x^5$ na expansão de $(x+1)^{13}$? Ou qual será o coeficiente de $x^i$ na expansão de $(x+1)^{13}$? E de $(x+1)^n$? Então e de $(x+c)^n$? Pelo binómio de Newton temos que $$(x+c)^n = \sum_{i=0}^n \binom{n}{i}c^{n-i}x^i$$ mas como é que podemos chegar a essa fórmula? Vamos começar por escrever os fatores de $(x+c)^n$ todos lado a lado: $$(x+c)\times(x+c)\times\cdots\times(x+c)$$ e agora pensamos no resultado de aplicar a propriedade distributiva neste polinómio todo sem fazer simplificações. A título de exemplo, tomemos $n = 2,3$: $$\begin{align} (x+c)^2 &= (x+c)(x+c) \\ &= xx + xc + cx + cc\\ (x+c)^3 &= (x+c)(x+c)(x+c) \\ &= (xx + xc + cx + cc)(x + c) \\ &= xxx + xxc + xcx + xcc + cxx + cxc + ccx + ccc\end{align}$$ O que podemos ver é que cada parcela final veio de escolher, dentro de cada factor $(x+c)$, ou o $x$ ou o $c$. A parcela $xcx$ vem da escolha $(\underline{x}+c)(x + \underline{c})(\underline{x}+c)$ e a parcela ...