Generating function for sequence of natural numbers?

Question

How do I find the generating function for the sequence of natural numbers 1,2,3... by formulating the closed form of the recurrence relation

$a_{n+1}=a_n+1, n \geq 0$

Answer 1

If you want an ordinary formal power series generating function then this will have the form

$G(a_n;x) = \sum_{n=0}^{\infty} a_nx^n$

so

$\frac{G}{x} = \sum_{n=0}^{\infty} a_nx^{n-1} = \frac{a_0}{x} + \sum_{n=0}^{\infty} a_{n+1}x^n$

Since we want to generate the natural numbers starting with $1$, we know that $a_0=1$ and $a_{n+1}=a_n+1$ for $n \ge 0$ so

$\frac{G}{x} = \frac{1}{x} + \sum_{n=0}^{\infty} (a_n+1)x^n = \frac{1}{x} + \frac{1}{1-x} + G$

$\Rightarrow G\left(\frac{1-x}{x}\right) = \frac{1}{x(1-x)}$

From this you can work out an expression for $G$.

Answer 2

You need a starting value, say $a_0$. Now compute the first few terms and you should notice a pattern for $a_n$. You can feed that into the definition of a generating function.