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.

Consider the recurrence equation $u_n = f(u_{n-1},\ldots, u_{n-k})\;,$ defined for $n=0,1,2\ldots$.

If this is a linear recurrence and the coefficient function on $u_{n-k}$ is nonzero in $\mathbb{Z}$, then I can solve my recurrence for $u_{n-k}$ and, keeping the same set of initial conditions, define a recursion heading through the negative integers. Is there a name for the operation I have just constructed?

Example: Consider the Fibonacci numbers, starting with $F_0=0,\, F_1=1$, etc. We have $F_{n-2}=F_{n-1} - F_{n}$, and a reindexing gives the sequence $G_n = - G_{n} + G_{n-2}$, defined on $\mathbb{Z}^+$ with initial conditions $G_0 = 0$ and $G_1=1$. Here, a closed form is given by $G_n = (-1)^n F_n$. (It is not difficult to come up with an example in which the connection is non-obvious.)

Are any nice properties preserved under this operation? In particular, I have been looking at holonomic recurrences (in which coefficients of $f$ are rational functions).

share|improve this question
I'm not sure what you mean by "properties." –  Qiaochu Yuan Jul 12 '11 at 2:34
@QiaochuYuan One of the questions asked about a given holonomic recurrence is whether the sequence produced is integral, given integral initial conditions. For example, the recurrence (n+1)^2u_{n+1}=(2n+1)^2 u_n +(13n^2+2)u_{n-1} +(9n^2-9n+3)u_{n-2}+(n-1)^2 u_{n-3} is integral, with initial conditions u_{-3} = u_{-2} = u_{-1} = 0 and u_0=1 [this is not normal]. Perhaps coincidentally, if we take initial conditions u_3=u_2=u_1=0 and u_0 =1 and use the recurrence to consider negative values, the sequence appears integral [of this I have no proof]. –  A Walker Jul 12 '11 at 6:39
add comment

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.