3
$\begingroup$

I'm looking for a method to solve the well-known recurrence ralation with different initial values. The one-parameter linear recurrence is easier. Let's take a peek:

  1. $a_0 = \alpha$; $a_1 = \beta$; $a_{n+2} = a_{n+1} + a_n$ whenever $n \in \mathbb Z$. We can use the repertoire method to solve it. Supposing that $a_n = A(n)\alpha + B(n)\beta$, well, let's plug $a_n = F_n$ into the recurrence, where $F_n$ is the Fibonocci sequence. We derive $F_n = B(n)$. Now, let's plug $a_n = F_{n+1}$ into it. we get $A(n) + B(n) = F_{n+1}$. So $A(n) = F_{n-1}$, $B(n) = F_n$.
  2. (Concrete Mathematics EXERCISE 5.73) $X_0 = \alpha$; $X_1 = \beta$; $X_n = (n-1)(X_{n-1}+X_{n-2})$. The repertoire method also works. We can plug the factorial function $n!$ and the subfactorial function $n! \sum_{k \le n} \frac{(-1)^k}{k!}$ into the recurrence.

Well, let's take a breather, and go on the main topic. I wonder how to solve two-parameter recurrence whose relation is well-known but with different initial values. Take an example from Concrete Mathematics:

(Concrete Mathematics EXERCISE 5.74, modified) $f(n,k)$ is defined when $1 \le k \le n$, and $f(n,1) = f(n,n) = n$, $f(n,k) = f(n-1,k) + f(n-1,k-1)$ for $1 < k < n$.

It is related to the binomial coefficients, because the recurrence relation is same. It can be solved with generating function, but the next one might not:

(Concrete Mathematics EXERCISE 6.16) $A_{n,0} = a_n [n \ge 0]$; $A_{0,k} = 0$, if $k > 0$; $A_{n,k} = kA_{n-1,k} + A_{n-1,k-1}$, integers $k,n$,

The recurrence relation is same as Stirling numbers of the second kind but the initial values.

The more general problem arises: solve the recurrence $X_{n,k} = \alpha(n,k)X_{n-1,k} + \beta(n,k)X_{n-1,k-1}$, when we know that $A_{n,k}$ is a (non-degenerate) solution with special initial values.

The problem is more difficult than one-parameter recurrence because there're infinity initial values in the recurrence, so the repertoire method might not work well.

Thanks for help.

1 Answers 1

0

Use generating functions. Consider:

$ a_{n + 2} = a_{n + 1} + a_n \qquad a_0, a_1 \text{ given} $

Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize some sums to get:

$ \frac{A(z) - a_0 - a_1 z}{z^2} = \frac{A(z) - a_0}{z} + A(z) $

Solve for $A(z)$:

$ A(z) = \frac{a_0 + (a_1 - a_0) z}{1 - z - z^2} $

This gets messy, as the denominator factors as $(1 - \tau z) (1 - \overline{\tau} z)$, where

$ \tau = \frac{1 + \sqrt{5}}{2} \\ \overline{\tau} = \frac{1 - \sqrt{5}}{2} $

A way out is to remember that the Fibonacci numbers satisfy the recurrence, with $F_0 = 0$, $F_1 = 1$, and have generating function:

$ F(z) = \frac{z}{1 - z - z^2} $

By Binet's formula:

$ F_n = \frac{1}{\sqrt{5}} \left( \tau^n - \overline{\tau}^n \right) $

while the Lucas numbers also satisfy it, with $L_0 = 2$, $L_1 = 1$, which from the above has generating function:

$ L(z) = \frac{2 - z}{1 - z - z^2} $

which gives:

$ L_n = \tau^n + \overline{\tau}^n $

Either from the above, or by recognizing:

$ \frac{1}{1 - z - z^2} = \frac{F(z) - F_0}{z} $

which is the generating function of the sequence $\langle F_{n + 1}\rangle$, you see that:

$ \frac{a_0 + (a_1 - a_0) z}{1 - z - z^2} = a_0 \frac{F(z) - F_0}{z} + (a_1 - a_0) F(z) $

which gives:

$ a_n = a_0 F_{n + 1} + (a_1 - a_0) F_n $

In terms of Lucas and Fibonacci numbers:

$ A(z) = \frac{a_0}{2} (L(z) + F(z)) - (a_1 - a_0) F(z) = \frac{a_0}{2} L(z) - a_1 F(z) - \frac{a_0}{2} F(z) $

so that:

$ a_n = \frac{a_0}{2} L_n + \frac{2 a_1 - a_0}{2} F_n $