Solving two-parameter linear recurrence with different initial values 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:


*

*$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$.

*(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.
 A: 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
$$
