# Closed Form of a Generating Function

Given $\sum_{n \geq 0} a_n x^n$, where $a_n$ is the number of strings of length n all of whose entries equals 1, find a closed form.

If I am correct so far, I have (0, 1, 2, 3, ...) as the counting sequence, equivalent to $(x + 2x^2 + 3x^3 + \cdots)$.

How does one go from sequence to closed form generating function?

• It's unclear what you're trying to sum. Are you trying to sum $a_n x^n$ or $a \cdot n \cdot x^n$? – Simon Rose Feb 18 '15 at 8:39
• Also, isn't there a unique string of length $n$ all of whose entries are 1, namely $\underbrace{1 \cdots 1}_{n \text{ times}}$? – Simon Rose Feb 18 '15 at 8:40
• The first one is what I meant. Yes, I figure the size of each element of the counting sequence would simply be n since the only option is all 1's. I don't understand how to derive the closed form from this. – ballin Feb 18 '15 at 8:45
• It would be helpful to learn a little bit of LaTeX so that questions like this are more clear. Anyhow, in this case, since there is a unique string of length $n$, we should have that $a_n = 1$ for all $n$, and so your sequence is actually $x + x^2 + x^3 + x^4 + \cdots$ – Simon Rose Feb 18 '15 at 8:47
• Actually, since your sum starts at $n = 0$ it should actually be $1 + x + x^2 + \cdots$ – Simon Rose Feb 18 '15 at 8:49

Since there is a unique string of length $n$ consisting only of 1s, you have for each $n$ that $a_n = 1$, and so your generating function is $$\sum_{n=0}^\infty a_nx^n = 1 + x + x^2 + x^3 + x^4 + \cdots$$ This is a geometric series, and it follows that $$\sum_{n=0}^\infty a_nx^n = \frac{1}{1 - x}$$ is the closed form that you're looking for.