Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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