Using generating functions to solve a recurrent relation

Question

I have one question on my Discrete Math homework that involves using generating functions, and I'm at a complete loss for how they work. The question asks:

"Use the generating function method to solve the following recurrent relations:

$ S_{n}= S_{n-1} + n$

$A_{0} = 0$ "

Any help would be appreciated!

Answer 1

Let generating function $g(x) = s_0 + s_1 x + s_2 x^2 + ... $ So $$-xg(x) = -s_0 x - s_1 x^2 -s_2x^3+ ... $$ Also $$-x\frac{1}{(1-x)^2} = -1x - 2x^2 - 3x^3 - ... $$ Now $$ g(x) - xg(x) - x\frac{1}{(1-x)^2} = s_0 + (s_1 - s_0 - 1)x + (s_2 - s_1 - 2)x^2 + ... + (s_{n+1} - s_n - (n + 1))x^{n+1} + ... $$ Here $s_0 = A_0 = 0$, and $s_{n + 1} = s_n + (n+1)$. Thereforwe, $$ g(x) - xg(x) - x\frac{1}{(1-x)^2} = 0$$ so $$g(x) = \frac{x}{(1-x)^3} = \sum_{k = 0}^{\infty}\frac{(k+2)(k+1)}{2}x^{k+1} = \sum_{k = 1}^{\infty}\frac{(k+1)k}{2}x^{k}$$ So $$S_k = s_k = \frac{(k+1)k}{2}$$ by equationg terms of $x_k$

Answer 2

First $\displaystyle S_n-S_{n-1}=a_n=n$.

Now, let $\displaystyle F(x)=\sum_{n=0}^{\infty}a_nx^n=\sum_{n=0}^{\infty}nx^n$.

Look at $\displaystyle \sum_{n=0}^{\infty}x^n$. This is a geometric series, hence $\displaystyle \sum_{n=0}^{\infty}x^n=\frac{1}{1-x}\text{ for }|x|<1$.

Deriving term by term (we have uniform convergence) we get $$\sum_{n=1}^{\infty}nx^{n-1}=\frac{1}{(1-x)^2}\Rightarrow \sum_{n=0}^{\infty}(n+1)x^n=\frac{1}{(1-x)^2}$$

Separating the sum $$\sum_{n=0}^{\infty}(n+1)x^n=\sum_{n=0}^{\infty}nx^n+\sum_{n=0}^{\infty}x^n=F(x)+\frac{1}{1-x}=\frac{1}{(1-x)^2}$$ Eventually $$F(x)=\frac{1}{(1-x)^2}-\frac{1}{1-x}=\frac{x}{(1-x)^2}$$

Answer 3

Let's define a function $a(x)$ in terms of the $A_k$ by $$ a(x) = \sum A_n x^n = A_0 + A_1 x + A_2 x^2 + \cdots $$ This is a formal power series, in the sense that we are not going to try to show that it is convergent for any given value or range of values of $x$; this is called the generating function for the sequence $\{A_n\}$.

Now let's look at the formal power series for $$ \frac{a(x)}{1-x} = (A_0 + A_1 x + A_2 x^2 + \cdots)(1+x+x^2+\cdots) = A_0 + (A_0+A_1)x + (A_0+A_1+A_2)x^2 + \cdots $$ (In your proof you should write these using summation so that the hand-waving $\cdots$ are not needed.)

So we see that $$ s(x)= \frac{a(x)}{1-x} = S_0 + S_1x + S_2x^2 + \cdots $$ which is the generating function for $S_n$. You have probably seen this in your book, because the generating function method is valuable because you can remember such tricks.

Now we get to work on this generating function. First off, the generating function $xs(x)$ has as its expansion
$$ 0+S_0x+S_1x^2+S_2x^3+\cdots $$ so this can be used to generate the $S_{n-1}$. Then the generating function for $M_n=n$ is $$ m(x) = x(1-x)^{-2}$$ which is another fact that is easy enough to demonstrate but is useful enough to just remember so that you can use it for many problems.

We can also use the fact that $A_0 = 0$ to say that $a(0)=0$ and $s(0) = \frac{a(0)}{1-0} = 0$. Thus we have $$ S_n = S_{n-1} + n \implies s(x) = xs(x)+ \frac{x}{(1-x)^2} $$ $$ (1-x)s(x) = \frac{1}{(1-x)^2}\\ s(x) = \frac{x}{(1-x)^3} \\ a(x) = (1-x)s(x) = \frac{x}{(1-x)^2} = 0\cdot x^0 + 1\cdot x + 2\cdot x^2 +\cdots = \sum nx^n $$ So finally, we have the answer: $$ A_n = n $$ And you can get the expression for $S_n$ by its generating function: $$ s(x) = \frac{x}{(1-x)^3} =\frac{1}{(1-x)^3}-\frac{1}{(1-x)^2} $$ and finding the Taylor series for $$\frac{1}{(1-x)^3} = \sum \frac{(n+1)(n+2)}{2}x^n\\ \frac{1}{(1-x)^2} = \sum (n+1)x^n $$ to get the result that $$ S_n = \frac{n(n-1)}{2}$$

Obviously this is not meant to seem easier than many other methods, especially if you don't know the "remember this" facts about generating functions. But the problem was meant to give you practice working with generating functions, which are very useful for problems posed later in the chapter and the book and sometimes real life.