Generating functions ( recurrence relations )

Question

Find $a_n$ using Generating Functions : $a_n = -a_{n-1} + 2a_{n−2}$, $n\ge2$ and $a_0 = 1$, $a_1 = 2$.

Approach : So I will form a characteristic equation $ r^2 + r - 2 = 0$ whose roots are $r_1 = -2$, $r_2 = 1$.

So my general solution is $a_n = α_1r_1^n + α_2r_2^n$.

$a_n = α_1(-2)^n + α_2(1)^n$

When $a_0 = 1$, then $1 = α_1(-2)^0 + α_2(1)^0$, then $α_2 = 1 - α_1 $.

When $a_1 = 2$, then $2 = α_1(-2)^1 + α_2(1)^1$, then $-2α_1 + 1 - α_1 = 2$.

$α_1 = -1/3$ and $α_2 = 4/3 $

So $a_n = -1/3r_1^n + 4/3r_2^n$.

Can anyone tell me if it is correct or not and any help will be appreciated :) .

Also, if I have $a_{n+2}=a_{n+1}+2a_n$. Can someone tell me if its char. equation should be like $r^2-r-2 = 0$? Just asking because of the addition symbol rather than subtraction.

Answer 1

The standard generating function approach yields $$GF=\frac{(1+3x)}{1+x-2x^2}$$ which has a denominator which can be factorised $$GF=\frac{1+3x}{(1+2x)(1-x)}$$ Applying the theory of partial fractions gives $$GF=-\frac{1}{3(1+2x)}+\frac{4}{3(1-x)}$$ which are all recognizable contributions to a formula for the $n$th term $$a_n=-\frac{1}{3}(-2)^n+\frac{4}{3}$$ which matches the answer by Cye Waldman

Answer 2

If you really want to use generating functions to get $a_n$. In general with a recurrence relation with initial conditions $a_0$ and $a_1$ and \begin{equation} a_n = r_1a_{n-1}+r_2a_{n-2} \end{equation} you can write the generating function as \begin{equation} G(x) = \frac{-a_0-a_1x+a_0r_1x}{r_2x^2+r_1x-1} \end{equation} so your question will have \begin{equation} G(x) = \frac{1+3x}{1+x-2x^2} = 1 + 2x +0x^2 + 4x^3 -4x^4 + \cdots \end{equation} where the coefficients of the expansion are the sequence $a_n$. To extract the coefficients we can see that \begin{equation} \frac{1}{n!}\frac{d^nG(x)}{dx^n}\bigg|_{x=0} =a_n \end{equation} however working out the $n^{th}$ derivative if a function can be tricky.

Answer 3

I understand that you are seeking a solution with generating functions, but I find the approach to these Fibonacci-type problems to be much more direct with a generalized Binet formula.

Here is a formal derivation of your result. The sequence you have found is a generalization of the Fibonacci sequence.

There have been many extensions of the sequence with adjustable (integer) coefficients and different (integer) initial conditions, e.g., $f_n=af_{n-1}+bf_{n-2}$. (You can look up Pell, Jacobsthal, Lucas, Pell-Lucas, and Jacobsthal-Lucas sequences.) Maynard has extended the analysis to $a,b\in\mathbb{R}$, (Ref: Maynard, P. (2008), “Generalised Binet Formulae,” $Applied \ Probability \ Trust$; available at http://ms.appliedprobability.org/data/files/Articles%2040/40-3-2.pdf.)

We have extended Maynard's analysis to include arbitrary $f_0,f_1\in\mathbb{R}$. It is relatively straightforward to show that

$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{f_0}{2} (\alpha^n+\beta^n) $$

where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$.

The result is written in this form to underscore that it is the sum of a Fibonacci-type and Lucas-type Binet-like terms. It will also reduce to the standard Fibonacci and Lucas sequences for $a=b=1$, $f_1=1$, and $f_0=0 \text{ or }2$, respectively.

So, specializing to your case, we can say

$$ \alpha,\beta=(a\pm\sqrt{a^2+4b})/2=(-1\pm\sqrt{1+8})/2=1,-2 $$

Then we readily derive the desired result

$$ a_n=\frac{4}{3}-\frac{1}{3}(-2)^n$$

This proves the OP's assertion. Moreover, it applies to all such problems.

Disclosure: this post is derived largely from a previous one: Decimal Fibonacci Number?

Answer 4

Define the generating function:

$\begin{equation*} A(z) = \sum_{k \ge 0} a_k z^k \end{equation*}$

Write the recurrence with no subtraction in indices, multiply by $z^n$, sum over $n \ge 0$:

$\begin{equation*} \sum_{n \ge 0} a_{n + 2} z^n = - \sum_{n \ge 0} a_{n + 1} z^n + 2 \sum_{n \ge 0} a_n z^n \end{equation*}$

Recognize the sums at hand:

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

Using the initial values given:

$\begin{equation*} \frac{A(z) - 1 - 2 z}{z^2} = - \frac{A(z) - 1}{z} + 2 A(z) \end{equation*}$

A bit of algebra gives, as partial fractions:

$\begin{align*} A(z) &= \frac{1 + 3 z}{1 - z - 2 z^2} \\ &= \frac{5}{3} \cdot \frac{1}{1- 2 z} - \frac{2}{3} \cdot \frac{1}{1 + z} \end{align*}$

The terms are geometric series, can read off the coefficients:

$\begin{equation*} a_n = \frac{5}{3} \cdot 2^n - \frac{2}{3} \cdot (-1)^n \end{equation*}$