Show that $\sum_{n=0}^{\infty} B_nx^n = \sum_{n=0}^{\infty} (x+x^2+x^3+x^4)^n$ where $B_n$ is the number of sequences made of $1,2,3,4$ with sum $n$

Question

Define $B_0 = 1$ and for $n>0$, $B_n$ is the number of sequences made of $1,2,3,4$ such that the sum of the numbers in the sequence is $n$. Show that $$\sum_{n=0}^{\infty}B_nx^n = \sum_{n=0}^{\infty} (x+x^2+x^3+x^4)^n$$
Here is what I did: We check what is the coefficient of $x^n$ is the RHS. Note that this is exactly $B_n$, because for every sequence made of $1,2,3,4$ with sum $n$, say $b_1b_2...b_k$, we can see that $(x+x^2+x^3+x^4)^k = (x+x^2+x^3+x^4)(x+x^2+x^3+x^4)...(x+x^2+x^3+x^4)$ will contain $x^k$ when we simplify: Just take $x^{b_i}$ from the $i$'th bracket. It is quite easy to show that this function, that takes a sequence made of $1,2,3,4$ with sum $n$ and returns some $x^n$ that can be reached when we simplify the sum, is one to one and onto, that is, we reach every $x^n$ that can be reached exactly once. Therefore, the coefficient of $x^n$ is going to be $B_n$, just like in the LHS, therefore the equality holds. Now I'm not sure how to make this solution formal. These are not finite sums, so I don't think it is true to say that if we have the same $x^n$'s in the RHS and in the LHS then the sums will be equal, because those infinite sums are actually limits, not real sums. Can anyone show me how do I make this idea more formal?

Answer 1

There are no limits here, but formal power series. In order to compute the exact coefficient of $x^n$ on the RHS you only have to look at finitely many of the infinitely many terms. E.g., if you want the exact coefficient of $x^{13}$ you only have to look at the powers $(x+x^2+x^3+x^4)^r$ for $0\leq r\leq13$, since all higher powers only give terms $x^k$ with $k>13$.

Your argument is more or less fine, but you have forgotten to mention that the length $r$ of the admissible sequences is not given in advance, and we have to take all possible $r\geq0$ into account.

If an $r\geq0$ is given then multiplying out $(x+x^2+x^3+x^4)^r$ distributively we obtain $4^r$ monomials $x^{b_1}x^{b_2}\cdots x^{b_r}$, one for each sequence $$b: \>\{1,2,\ldots,r\}\to[4], \qquad i\mapsto b_i\ .$$ If we collect all monomials of total exponent $b_1+b_2+\ldots+b_r=n$ we obtain $c x^n$, whereby the coefficient $c$ is the number of such monomials, resp., sequences $b$ of length $r$ summing to $n$. It follows that multiplying out the powers $(\ldots)^r$ and collecting everything according to the resulting powers $x^n$ we obtain $$\sum_{r=0}^\infty (x+x^2+x^3+x^4)^r=\sum_{n=0}^\infty B_n\>x^n\ ,$$ whereby $B_n$ denotes the number of ways to obtain $b_1+b_2+\ldots+b_r=n$ with a nonprescribed $r\geq0$.