4
$\begingroup$

I'm trying to solve the recurrence relation below by using generating function:

\begin{equation} a_n=\begin{cases} 0, & \text{if $n<0$}\\ 2, & \text{if $n=0$}\\ 1, & \text{if $n=1$}\\ 3a_{n-1} + a_{n-2}, & \text{otherwise}. \end{cases} \end{equation}

The first thing I did was make the recurrence relation valid for all $n$ by using a kronecker delta:

$a_0 = 3.(0) + 0 + 2.(\delta_{n,0}) = 2$

$a_1 = 3.(2) + 0 - 5.(\delta_{n,1}) = 1$

The result I got was:

$$a_n = 3a_{n-1} + a_{n-2} + 2\delta_{n,0} - 5\delta_{n,1}$$

Multiplying by $x^n$:

$$a_n . x^n = 3a_{n-1} . x^n + a_{n-2} . x^n + 2\delta_{n,0} . x^n - 5\delta_{n,1} . x^n$$

Summing up both sides:

$$\sum_{n\geq0} a_n . x^n = \sum_{n\geq0}3a_{n-1} . x^n + \sum_{n\geq0}a_{n-2} . x^n + \sum_{n\geq0}2\delta_{n,0} . x^n - \sum_{n\geq0}5\delta_{n,1} . x^n$$

And making $F(x) = \sum_{n\geq0} a_n . x^n$, I got:

$$F(x) = 3xF(x) + x^2F(x) + 2 - 5x$$

which is:

$$F(x) = \frac{2 - 5x}{1-3x-x^2}$$

So far so good but from here on I can't find a way to calculate the $a_n$

I've heard it has something to do with partials fractions but I'm a newbie in this subject and I have no idea how to follow through.

Does anyone can help me to finish the calculation?

Thanks in advance.

$\endgroup$
6
$\begingroup$

I'm going to rewrite the problem as $$a_{n+2} = 3a_{n+1} + a_n; \; a_0 = 2,\; a_1=1.$$ Multiply by $x^n$, sum, and let $A(x) = \sum_{n\ge 0}a_nx^n$. So, $$\sum_{n\ge 0}a_{n+2}x^n = 3\sum_{n\ge 0}a_{n+1}x^n + \sum_{n\ge 0}a_n x^n,$$ and we can see that $\sum_{n\ge 0}a_{n+2}x^n = a_2 + a_3x + \cdots = (1/x^2)(A(x)-a_0-a_1x)$ and similarly $\sum_{n\ge 0}a_{n+1}x^n = a_1 + a_2x + \cdots = (1/x)(A(x)-a_0)$, so we obtain $$\frac{1}{x^2}(A(x) - a_0 - a_1x) = \frac{3}{x} (A(x)-a_0 ) + A(x).$$

Substituting for $a_0$ and $a_1$ and solving for $A(x)$ yields your $F(x)$, ie $$A(x) = \frac{2-5x}{1-3x-x^2}.$$

Now the for the partial fraction decomposition, which is not so ugly if we keep our heads straight. Note that $1-3x-x^2$ has roots $\alpha_1 = -\frac{3}{2} - \frac{\sqrt{13}}{2}$ and $\alpha_2 = -\frac{3}{2} + \frac{\sqrt{13}}{2}$ and we want $$\frac{1}{1-3x-x^2} = \frac{1}{(x-\alpha_1)(x-\alpha_2)} = \frac{A}{(x-\alpha_1)} + \frac{B}{(x-\alpha_2)}.$$ Using this equation and solving for $A$ and $B$ yields \begin{align} \frac{1}{1-3x-x^2} &= \frac{1}{(\alpha_1-\alpha_2)(x-\alpha_1)} + \frac{1}{(\alpha_2-\alpha_1)(x-\alpha_2)}\\ &=\frac{1}{-\sqrt{13}(x-\alpha_1)} + \frac{1}{\sqrt{13}(x-\alpha_2)} \end{align}

So we have

\begin{align} A(x) &= (2-5x)\left(\frac{1}{-\sqrt{13}(x-\alpha_1)} + \frac{1}{\sqrt{13}(x-\alpha_2)} \right)\\ &=(2-5x) \left( \frac{1}{\alpha_1\sqrt{13}} \cdot \frac{1}{1-(x/\alpha_1)} + \frac{1}{-\alpha_2\sqrt{13}} \cdot \frac{1}{1-(x/\alpha_2)} \right)\\ &= (2-5x) \left( \frac{1}{\alpha_1\sqrt{13}} \sum_{n\ge 0} \left(\frac{1}{\alpha_1} \right)^n x^n + \frac{1}{-\alpha_2\sqrt{13}} \sum_{n\ge 0} \left(\frac{1}{\alpha_2} \right)^n x^n \right)\\ &= \frac{(2-5x)}{\sqrt{13}} \left(\sum_{n\ge 0} \left[ \left(\frac{1}{\alpha_1} \right)^{n+1} - \left(\frac{1}{\alpha_2} \right)^{n+1}\right] x^n \right) \end{align}

Can you take it from here?

$\endgroup$
  • $\begingroup$ You beat me to it... (+1) $\endgroup$ – clathratus Oct 19 at 2:58
2
$\begingroup$

By using another method I got the closed-form as follows:

$$a_n = \left( 1 - \frac{2}{\sqrt{13}}\right)\left( \frac{3+\sqrt{13}}{2}\right)^n + \left( 1 + \frac{2}{\sqrt{13}}\right)\left( \frac{3-\sqrt{13}}{2}\right)^n$$

However I need to find $a_n$ by using the generating function $F(x)$ as described earlier.

$\endgroup$
1
$\begingroup$

The Lucas polynomials are defined by \begin{align} L_{n}(x) = \begin{cases} 2 & n=0 \\ 1 & n=1 \\ x \, L_{n-1}(x) + L_{n-2}(x) & n \geq 2\end{cases}. \end{align} From this it easy to see that $a_{n} = L_{n}(3)$.

By the generating function: \begin{align} \sum_{n=0}^{\infty} L_{n+2}(x) \, t^n &= x \, \sum_{n=0}^{\infty} L_{n+1}(x) \, t^n + \sum_{n=0}^{\infty} L_{n}(x) \, t^n \\ \frac{1}{t^2} \, \sum_{n=2}^{\infty} L_{n}(x) \, t^n &= \frac{x}{t} \, \sum_{n=1}^{\infty} L_{n}(x) \, t^n + \sum_{n=0}^{\infty} L_{n}(x) \, t^n \\ \frac{1}{t^2} \, \left(F - L_{0}(x) - L_{1}(x) \, t \right) &= \frac{x}{t} \, (F - L_{0}(x)) + F \hspace{15mm} F = \sum_{n=0}^{\infty} L_{n}(x) \, t^n \\ (1 - x \, t - t^2) \, F &= L_{0}(x) + (L_{1}(x) - x \, L_{0}(x) ) \, t \\ \sum_{n=0}^{\infty} L_{n}(x) \, t^n &= \frac{L_{0}(x) + (L_{1}(x) - x \, L_{0}(x)) \, t}{1- x \, t - t^2} \end{align} This can also be seen as $$\sum_{n=0}^{\infty} L_{n}(x) \, t^n = \frac{2 + (1-2 x) \, t}{1 - x \, t - t^2}.$$ Letting $x=3$ gives the desired result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.