1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Simon Rose Feb 18 '15 at 8:39
  • $\begingroup$ Also, isn't there a unique string of length $n$ all of whose entries are 1, namely $\underbrace{1 \cdots 1}_{n \text{ times}}$? $\endgroup$ – Simon Rose Feb 18 '15 at 8:40
  • $\begingroup$ 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. $\endgroup$ – ballin Feb 18 '15 at 8:45
  • $\begingroup$ 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$ $\endgroup$ – Simon Rose Feb 18 '15 at 8:47
  • $\begingroup$ Actually, since your sum starts at $n = 0$ it should actually be $1 + x + x^2 + \cdots$ $\endgroup$ – Simon Rose Feb 18 '15 at 8:49
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.