# Questions tagged [generating-functions]

Generating functions are formed by making a series $\sum_{n\geq 0} a_n x^n$ out of a sequence $a_n$. They are used to count objects in enumerative combinatorics.

2,844 questions
9k views

### Factorial and exponential dual identities

There are two identities that have a seemingly dual correspondence: $$e^x = \sum_{n\ge0} {x^n\over n!}$$ and $$n! = \int_0^{\infty} {x^n\over e^x}\ dx.$$ Is there anything to this comparison? (I ...
2k views

### Expected maximum number of unpaired socks

Like all combinatoric problems, this one is probably equivalent to another, well-known one, but I haven't managed to find such an equivalent problem (and OEIS didn't help), so I offer this one as ...
33k views

### The generating function for the Fibonacci numbers

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers, i.e., the sequence $\left\{1,1,2,3,5,8,13,21,...\right\}$.
7k views

### Why are generating functions useful?

I was under the mistaken impression that if one could find the generating function for a sequence of numbers, you could just plug in a natural number $n$ to find the nth term of the sequence. I ...
941 views

### Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
7k views

1k views

### Solving the recursion $3a_{n+1}=2(n+1)a_n+5(n+1)!$ via generating functions

I have been trying to solve the recurrence: \begin{align*} a_{n+1}=\frac{2(n+1)a_n+5((n+1)!)}{3}, \end{align*} where $a_0=5$, via generating functions with little success. My progress until now is ...
750 views

585 views

### Why is it important to have the closed form of a generating function?

I am having introductory lectures on combinatorial analysis, I've been presented to the concept of generating functions and it's applications to solving combinatorial problems. The generating function ...
960 views

### Why would you take the logarithmic derivative of a generating function?

Today, my climbing expedition scaled Mt. Sloane to request the Oracle's Extensive Insight into Sequences. The monks there had never heard of our plight, so they inscribed our query in mystical runes ...
412 views

### Words built from $\{0,1,2\}$ with restrictions which are not so easy to accomodate.

We assume a ternary alphabet $V=\{0,1,2\}$ and are looking for a generating function describing the number of words of $V^*$ fulfilling certain restrictions. The words I am interested in do not ...
201 views

408 views

### Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus. Here is what I have so far, but I think I made a mistake: \begin{align*} e^{\log\...
980 views

1k views

### Generating functions for context-free languages

I have a question about context free grammars and their relationship with generating functions. It is well-know how to associate a generating function $\mathsf{gf}{(R)}$ with a non-ambiguous regular ...