Find the closed form from a recurrence relation using generating functions

61 Views Asked by At

I want to find the closed form of $$b_{n}=a_{n} - a_{n-1}, a_{0} = b_{0}$$ in terms of $A(x)$.

Attempt:

I first tried to rewrite as: $b_{n+1}=a_{n+1} - a_{n}$ then I multiplied both sides by $x^{n+1}$ to get: $$\sum_{n\geq0}b_{n+1}x^{n+1}=\sum_{n\geq0}a_{n+1}x^{n+1} - \sum_{n\geq0}a_{n}x^{n+1} $$ then I get: $$B(x)= A(x) -xA(x)$$ I am not sure how to proceed from here to get the closed form.

2

There are 2 best solutions below

0
On

In this case the use of generating functions is not useful. This will be seen by the following demonstration.

Begin with $$b_{n} = a_{n} - a_{n-1}, \hspace{5mm} a_{0} = b_{0}$$ and turn it into $$a_{n} = a_{n-1} + b_{n} \hspace{5mm} a_{0} = b_{0}.$$ For $n=1$: $a_{1} = a_{0} + b_{1} = b_{0} + b_{1}$. Repeating the process leads to $$a_{n} = \sum_{j=0}^{n} b_{j}.$$ It is quickly found that $a_{n} - a_{n-1} = b_{n}$ and that any generating function for $b_{n}$ equals that of $b_{n}$ by the recurrence relation. In a different manor it is determined that: Let $$B(t) = \sum_{n=0}^{\infty} b_{n} \, t^{n},$$ then

\begin{align} \sum_{n=0}^{\infty} a_{n} \, t^{n} &= \sum_{n=0}^{\infty} \sum_{j=0}^{n} b_{j} \, t^{n} = \sum_{n,j=0}^{\infty} b_{j} \, t^{n+j} = \frac{1}{1-t} \, B(t) \\ \sum_{n=0}^{\infty} a_{n-1} \, t^{n} &= \sum_{n=0}^{\infty} \sum_{j=0}^{n-1} b_{j} \, t^{n} = \sum_{n=0}^{\infty} (a_{n} - b_{n}) \, t^{n} = \left(\frac{1}{1-t} - 1\right) \, B(t) = \frac{t}{1-t} \, B(t). \end{align} The recurrence equation $b_{n} = a_{n} - a_{n-1}$ leads to $$B(t) = \frac{1}{1-t} \, B(t) - \frac{t}{1-t} \, B(t) = B(t).$$

0
On

Define generating functions:

$\begin{align*} A(z) &= \sum_{n \ge 0} a_n z^n \\ B(z) &= \sum_{n \ge 0} b_n z^n \end{align*}$

Write your recurrence shifted, multiply by $z^n$ and sum over $n \ge 0$, recognize resulting sums:

$\begin{align*} \sum_{n \ge 0} b_{n +1} z^n &= \sum_{n \ge 0} a_{n +1} z^n - \sum_{n \ge 0} a_n z^n \\ \frac{B(z) - b_0}{z} &= \frac{A(z) - a_0}{z} - A(z) \end{align*}$

Solve for $B(z)$, remembering $b_0 = a_0$:

$\begin{equation*} B(z) = A(z) (1 - z) \end{equation*}$