MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does anyone know where I would be able to get information on analyzing a class of polynomial recurrence relations of a form like this?

$\begin{align*} f_{n,k}(x) & =a(x)f_{n-1,k}(x)+b(x)f_{n-2,k}(x) & n\equiv1\,\mbox{(mod k)}\\ & =f_{n-1,k}(x)+a(x)b(x)f_{n-2,k}(x) & n\equiv2\,\mbox{(mod k)}\\ & =f_{n-1,k}(x)+b(x)f_{n-2,k}(x) & \mbox{o.w.}\end{align*}$

My preliminary work suggests that for all $k$, it should collapse down into a single second-order recurrence relation:

$\begin{align*} f_{n,k} & =a_k(x)f_{n-k,k}+b_k(x)f_{n-2k,k}(x)\end{align*}$

with the original recurrence divided into $k$ separate solutions each defined by initial conditions $f_{j,k}(x)$ and $f_{j+k,k}(x)$, $0\leq j < k$, where the functions $a_k(x)$ and $b_k(x)$ are themselves defined by a specific pair of recurrence relations in $k$. But the modular structure's giving me troubles in proving either the collapse or, given the collapse, the validity of the recurrences potentially defining $a_k(x)$ and $b_k(x)$ through any sort of inductive approach, and I haven't had any luck digging up any references to a recurrence structure of even a vaguely similar form. Even just something similar in nature could give me a lead into pinning this down.

share|cite|improve this question
I have no idea, but at least I can verify a tiny bit. If $u_n$ is given by $au_{n-1}+bu_{n-2}$, $u_{n-1}+abu_{n-2}$, or $u_{n-1}+bu_{n-2}$ according as $n$ is 1, 2, or 0 modulo 3, then (at least for $n\equiv1\pmod3$) we get $u_n=(2ab+a+b)u_{n-3}+ab^3u_{n-6}$, which agrees with your suggested form. But perhaps this was already found in your "preliminary work". – Gerry Myerson Dec 6 '11 at 21:56
It was, yes, though I appreciate it anyway; so far I've verified it by hand for $k$ from 2 to 5. – Justin Hilyard Dec 7 '11 at 4:58

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.