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

Your Answer


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

Browse other questions tagged or ask your own question.