Find the sequence $(y_{k})_{k}$ that gives rise to the generating function $Y(s) = (3 – s)^{n}$, $n \in \mathbb{N}$.
Someone can help me? Thank you in advance.
Find the sequence using generating functions
combinatoricsgenerating-functions
Related Solutions
$$(x^{2} + x^{3} + x^{4} + x^{5} + x^{6})^{8}=(x^2(1+x+x^2+x^3+x^4))^8=$$ $$=x^{16}\left(\frac{1-x^5}{1-x}\right)^8=x^{16}(1-x^5)^8(1-x)^{-8}=$$ $$=x^{16}\sum_{k=0}^{8}\binom{8}{k}(-x)^{5k}\sum_{l=0}^{\infty}\binom{8+l-1}{l}x^l=$$ $$=\sum_{l=0}^{\infty}\sum_{k=0}^{8}(-1)^{5k}\binom{8+l-1}{l}\binom{8}{k}x^{16+5k+l}$$ $$16+5k+l=21\Rightarrow k=1,l=0 \text{and}k=0,l=5$$ coefficient next $x^{21}$ is $$(-1)^0\binom{8+5-1}{5}\binom{8}{0}+(-1)^5\binom{8+0-1}{0}\binom{8}{1}=\binom{12}{5}-8$$
You have more or less the right idea, but the right hand side is the sequence $(4n)$, not $(4)$. We have, \begin{align*} \sum_{n=0}^\infty 4n x^n &= \sum_{n=0}^\infty 4(n + 1)x^n - \sum_{n=0}^\infty 4x^n \\ &= \frac{\mathrm{d}}{\mathrm{d}x}\sum_{n=0}^\infty 4x^{n+1} - \sum_{n=0}^\infty 4x^n \\ &= \frac{\mathrm{d}}{\mathrm{d}x}\left(\frac{4}{1 - x} - 4\right) - \frac{4}{1 - x} \\ &= \frac{4}{(1 - x)^2} - \frac{4}{1 - x} \\ &= \frac{4x}{(1 - x)^2}. \end{align*}
As you noted, we have \begin{align*} A(x) - xA(x) - 2x^2A(x) &= a_0 + (a_1 - a_0)x + (a_2 - a_1 - 2a_0)x^2 + (a_3 - a_2 - 2a_1)x^3 + \ldots \\ &= a_0 + (a_1 - a_0)x + (4 \cdot 2)x^2 + (4 \cdot 3)x^3 + \ldots + 4n x^n + \ldots \\ &= \frac{4x}{(1 - x)^2} + a_0 + (a_1 - a_0)x - 4x \\ &= \frac{4x}{(1 - x)^2} - 4 + (-5 + 4)x - 4x \\ &= \frac{4x}{(1 - x)^2} - 4 - 5x \\ &= \frac{4x - (4 + 5x)(1 - x)^2}{(1 - x)^2} \\ &= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2} \\ A(x) &= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2(1 - x - 2x^2)} \\ &= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2(1 - 2x)(1 + x)}. \end{align*} Before we apply partial fractions, it's worth testing if this fraction can be simplified at all. Plugging in $x = -1$ produces $0$, meaning that $1 + x$ divides it. Dividing out $1 + x$ from the numerator and denominator, $$A(x) = \frac{-5x^2 + 11x - 4}{(1 - x)^2(1 - 2x)}$$
Now we apply partial fractions. We wish to find $a, b, c$ such that $$A(x) = \frac{a}{1 - x} + \frac{b}{(1 - x)^2} + \frac{c}{1 - 2x},$$ or equivalently, $$-5x^2 + 11x - 4 = a(1 - x)(1 - 2x) + b(1 - 2x) + c(1 - x)^2.$$ Considering $x = 1$, $$-5 \cdot 1^2 + 11 \cdot 1 - 4 = b \cdot (-1) \implies b = -2.$$ Considering $x = \frac{1}{2}$, $$-5 \cdot \left(\frac{1}{2}\right)^2 + 11 \cdot \frac{1}{2} - 4 = c \cdot \left( \frac{1}{2}\right)^2 \cdot \implies c = 1.$$ Now, using these values of $b$ and $c$, we can find $a$ by substituting a different value for $x$, e.g. $x = 0$: $$-4 = a + (-2) \cdot 1 + 1 \cdot 1^2 \implies a = -3.$$ That is, $$A(x) = \frac{-3}{1 - x} + \frac{-2}{(1 - x)^2} + \frac{1}{1 - 2x}.$$ We finally convert these generating functions back to sequences: $$a_n = -3 + (-2)(n + 1) + 2^n = -5 + 2n + 2^n,$$ as required.
Best Answer
We observe $Y(s)=(3-s)^n$ is a polynomial in $s$ of degree $n$. This implies the polynomial admits a representation \begin{align*} Y(s)=\sum_{k=0}^ny_k s^k \end{align*} Application of the binomial theorem to $Y(s)=(3-s)^n$ gives \begin{align*} Y(s)&=\sum_{k=0}^n\binom{n}{k}(-s)^k3^{n-k}\\ &=\sum_{k=0}^n\binom{n}{k}(-1)^k3^{n-k}s^k \end{align*} from which we deduce the sequence $(y_k)_k$ is the finite sequence \begin{align*} (y_k)_{0\leq k\leq n}=\color{blue}{\left(\binom{n}{k}(-1)^k3^{n-k}\right)_{0\leq k\leq n}} \end{align*}