Existence of the Limit of Ratios of Consecutive Terms for a Class of Linear Recurrences

Abstract

Let ${\left(F_n\right)}_{n=1}^{\infty }$ be the classical Fibonacci sequence. It is well known that the $lim{F}_{n+1}/F_n$ exists and equals the Golden Mean. If, more generally, ${\left(F_n\right)}_{n=1}^{\infty }$ is an order-k linear recurrence with real constant coefficients, i.e., $F_n={\sum }_{j=1}^k{\lambda }_{k+1-j}{F}_{n-j}$ with $n>k$, ${\lambda }_j\in \mathbb{R}$, $j=1,\dots ,k$, then the existence of the limit of ratios of consecutive terms may fail. In this paper, we show that the limit exists if the first k elements $F_1,F_2,\dots ,F_k$ of ${\left(F_n\right)}_{n=1}^{\infty }$ are positive, ${\lambda }_1,\dots ,{\lambda }_{k-1}$ are all nonnegative, at least one being positive, and $max({\lambda }_1,\dots ,{\lambda }_k)={\lambda }_k\ge k$. The limit is characterized as fixed point, bounded below by ${\lambda }_k$ and bounded above by ${\lambda }_1+{\lambda }_2+\cdots +{\lambda }_k$.

1. Introduction

The Fibonacci sequence ${\left(F_n\right)}_{n=1}^{\infty }$ defined by $F_1=F_2=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n>2$ is ubiquitous in recreational mathematics, architecture, arts, biology, etc., as well as in Discrete Mathematics. History, curiosities, and applications appear repetitively in the scientific literature and on web sites (see, e.g., Knott [1]), and it goes on attracting the interest of mathematicians still today (see, e.g., the very recent paper Berend, Kumar [2]). Just to give few references, we mention the old thesis Stein [3] for an exhaustive account of the subject, which includes a historical timeline starting from the celebrated 1228 book Liber Abaci, the article Jeske [4], the treatises Kelley, Peterson [5], Salinelli, Tomarelli [6], Koshy [7,8], and Traub [9], Andrica, Bagdasar [10] for basic results about linear recurrence relations, and also, Dunlap [11], Meisner [12], and Posamentier et al. [13] for less technical expositions. Among the long list of the fascinating properties, one of the most known is that the limit of the sequence of ratios of consecutive terms ($(n+1)$-th to n-th) of the Fibonacci sequence, called also the Kepler limit (see, e.g., Fiorenza, Vincenzi [14,15], Anatriello, Fiorenza, Vincenzi [16], Berend, Kumar [2], and Matousova and Trojovsky [17]), equals the celebrated Golden Ratio:

$$\underset{n\to \infty }{lim}\frac{F_{n+1}}{F_n}=\mathsf{\Phi }=\frac{1+\sqrt{5}}{2}.$$

(1)

Assuming the existence of the limit, which we may call temporarily x, noticing that it must be greater than or equal to 1, since the sequence is increasing, the well-known proof of (1) is very short: in fact,

$$x=\underset{n\to \infty }{lim}\frac{F_{n+1}}{F_n}=\underset{n\to \infty }{lim}\frac{F_n+F_{n-1}}{F_n}=\underset{n\to \infty }{lim}1+\frac{F_{n-1}}{F_n}=1+\frac{1}{x}$$

(2)

and therefore, x must be nonnegative because the limit of a positive sequence must be the root of the equation $x^2-x-1=0$; the unique nonnegative root is exactly $\mathsf{\Phi }$.

However, the proof of the existence of the limit is somewhat more technical, and it appears more frequently in books whose readers are more specifically mathematicians (starting from the undergraduate level and going up). The proof can be carried out in various ways, but roughly speaking, there are two methods:

$\left(\alpha \right)$ The Fibonacci sequence can be seen as a special linear recurrence sequence of order k, i.e., a sequence defined through a relation of the type

$$F_n=\sum _{j=1}^k{\lambda }_{k+1-j}{F}_{n-j}n>k$$

with fixed ${\lambda }_j\in \mathbb{R}$, $j=1,\dots ,k$. The k first elements $F_1,F_2,\dots ,F_k$ of ${\left(F_n\right)}_{n=1}^{\infty }$ are called initial conditions. The polynomial

$$p\left(x\right)=x^k-\sum _{j=1}^k{\lambda }_{k+1-j}{x}^{k-j}$$

is called the characteristic polynomial of the sequence, and its roots ${\phi }_1,\dots ,{\phi }_h$ (pairwise distinct, hence $1\le h\le k$), which in general are complex numbers, are called characteristic roots. A standard result of the theory is that ${\left(F_n\right)}_{n=1}^{\infty }$ admits the explicit expression

$$F_n=\sum _{i=1}^h{c}_{i,1}{\phi }_i^n+c_{i,2}n{\phi }_i^n+\cdots +c_{i,k_i}{n}^{k_i-1}{\phi }_i^{n}n\in \mathbb{N}$$

where $k_1,\dots ,k_h$ are, respectively, the multiplicity of ${\phi }_1,\dots ,{\phi }_h$, ${\displaystyle \sum _{i=1}^h{k}_i=k}$. For details on recurrence sequences, see, e.g., Everest [18]. Overall, in a few words, “$F_n=F_{n-1}+F_{n-2}$ for $n>2$” can be seen as an equation where the sequence ${\left(F_n\right)}_{n=1}^{\infty }$ is the unknown. The explicit formula for the n-th term becomes, in the case of the Fibonacci sequence,

$$F_n=\frac{1}{\sqrt{5}}{\mathsf{\Phi }}^n-\frac{1}{\sqrt{5}}{(-\frac{1}{\mathsf{\Phi }})}^{n}n\in \mathbb{N}.$$

Such a formula is called Binet’s formula and allows the computation of the Kepler limit in a few lines (see, e.g., Stein [3] (Property 77, p. 87), Chasnov [19] (Lecture 5), [19] (Corollary 8.6, p. 152)); extensions of Binet’s formula are, e.g., in Tanackov, Kovačević, Tepić [20], in Bacani, Rabago [21] for k-nacci-like sequences; in Bagdasar, Hedderwick [22] for the case of complex Horadam sequences.

$\left(\beta \right)$ Without the (explicit or implicit) use of the general theory of linear recurrence sequences, the idea is to look for a recurrence relation satisfied by the sequence of ratios of consecutive terms appearing in the left-hand side of (1); let us call it ${\left(a_n\right)}_{n=1}^{\infty }$. From the definition of the Fibonacci sequence, it is readily seen that

$$a_1=1,a_{n+1}=1+\frac{1}{a_n}n\in \mathbb{N}.$$

It can be seen that this sequence is not monotonic, but it is oscillating, and its regularity can be established considering separately even terms and odd terms, noticing their monotonicity, and applying theorems on monotone sequences (this is quite common in undergraduate texts in Analysis; see, e.g., Crasta, Malusa [23] (pp. 157–158), Pagani, Salsa [24] (pp. 186–187), and Marcellini, Sbordone [25] (n. 70, p. 309). The convergence of ${\left(a_n\right)}_{n=1}^{\infty }$ can be established through fixed-point theorems such as the Contraction Mapping Theorem (see, e.g., Hunter, Nachtergaele [26] (Ch. 3)), used, e.g., in Belding, Mitchell [27] (Example 4.2.3 and Exercise 9) or Barcz [28]; see also Matkowski’s fixed-point theorem, which allows proving the existence of the Kepler limit also for more general second-order linear recurrences (see Barcz [29]), or Edelstein’s fixed-point theorem, used in Barcz [30]. Overall, in a few words, convergence of the ratios is obtained by finding-root methods.

2. The Main Results

At first, in this paper, in Theorem 1, we give a short proof of (1) (in fact, the proof will be shown in a slightly more general setting), which can be considered a modification of the argument in (2) to include also the existence, avoids the use of general theories of linear recurrences or iterative methods and fixed-point theorems, and is basically a modification of $\beta )$, which avoids the checks of monotonicity and the use of results on monotone sequences. The main tools, which will be used also in Theorem 2 to prove the existence of the Kepler limit for a class of higher-order linear positive recurrences, are the notions of the lower limit and upper limit, known from several books in Analysis at the undergraduate level (see, e.g., Hunter [31] (Section 3.6), Rudin [32] (p. 55), Campanato [33] (Def. 9.I and Def. 9.II, p. 116), and the book by the author and Greco [34] (Ch. 4, p. 246)). These tools are, to our knowledge, the novelty of this paper: in fact, both Theorems 1 and 2 fall within an existence result for the Kepler limit proven in Anatriello, Fiorenza, Vincenzi [16] (Proposition 2.2), which uses more technical tools and is part of method $\alpha )$. We recall that in Fiorenza, Vincenzi [14,15], a necessary and sufficient condition for the existence of the limit of consecutive terms was established in the generality of linear recurrences of any order.

Let us fix some notation. $\mathbb{N}$ is the set of natural numbers $\{1,2,\dots \}$; we simplify the symbols such as ${\left(a_n\right)}_{n=1}^{\infty }$ denoting sequences writing simply $\left(a_n\right)$. Symbols for the lower limit and the upper limit of a sequence $\left(a_n\right)$ will follow Campanato [35] (Def. 9.I and Def. 9.II, p. 116) and the book by the author and Greco [34] (Ch. 4, p. 246); namely, we will write $lim{}^{\prime }{a}_n$ and $lim{}^{″}{a}_n$, respectively. Note that we omit “$n\to \infty$” below the symbols $lim{}^{\prime }$ and $lim{}^{″}$, and the same convention will be always adopted for the lim symbol, so that, for instance, it makes sense to write

$$lim{a}_n=lim{a}_{n+h},lim{}^{\prime }{a}_n=lim{}^{\prime }{a}_{n+h},lim{}^{″}{a}_n=lim{}^{″}{a}_{n+h},h\in \mathbb{N}.$$

(3)

We recall the following properties (known from Analysis at the undergraduate level): the first one asserts that the equality among the upper and lower limit is equivalent to the existence of the limit (finite or infinite) and

$$lim{}^{\prime }{a}_n=lim{}^{″}{a}_n\Rightarrow lim{a}_n=lim{}^{\prime }{a}_n=lim{}^{″}{a}_n$$

(4)

see, e.g., Hunter [31] (Thm 3.42, p. 52).

Moreover,

$$a_n>\lambda ,a_n<\lambda \mathrm{definitively}\Rightarrow lim{}^{\prime }{a}_n\ge \lambda ,lim{}^{″}{a}_n\le \lambda \mathrm{respectively},$$

(5)

the last ones being special cases, for instance, of Rudin [32] (Thm 3.19, p. 57). Finally, we recall also the next ones, which will be used for sequences $\left(a_n\right)$, $\left(a_n^{\left(i\right)}\right)$ bounded below and above by positive constants:

$$lim{}^{\prime }\frac{1}{a_n}=\frac{1}{lim{}^{″}{a}_n},lim{}^{″}\frac{1}{a_n}=\frac{1}{lim{}^{\prime }{a}_n}$$

(6)

see Giusti [36] (p. 79) and Campanato [35] (Es.4, p. 107)

$$lim{}^{\prime }\prod _{i=1}^j{a}_n^{\left(i\right)}\ge \prod _{i=1}^{j}lim{}^{\prime }{a}_n^{\left(i\right)}lim{}^{″}\prod _{i=1}^j{a}_n^{\left(i\right)}\le \prod _{i=1}^{j}lim{}^{″}{a}_n^{\left(i\right)}$$

(7)

the last ones appearing, e.g., on the web site [37]. Properties (7) can be proven also directly from the superadditivity of $lim{}^{\prime }$ and subadditivity of $lim{}^{″}$, respectively, i.e., by

$$lim{}^{\prime }\sum _{i=1}^j{a}_n^{\left(i\right)}\ge \sum _{i=1}^{j}lim{}^{\prime }{a}_n^{\left(i\right)}lim{}^{″}\sum _{i=1}^j{a}_n^{\left(i\right)}\le \sum _{i=1}^{j}lim{}^{″}{a}_n^{\left(i\right)}.$$

(8)

3. Proofs of the Main Results

Let $k\in \mathbb{N}$, $k\ge 2$, and let $\left(F_n\right)$ be a sequence satisfying

$$F_n={\lambda }_1{F}_{n-k}+{\lambda }_2{F}_{n-k+1}+\cdots +{\lambda }_k{F}_{n-1}=\sum _{j=1}^k{\lambda }_{k+1-j}{F}_{n-j}n>k,$$

(9)

where

$${\lambda }_{\mathrm{j}}\ge 0 \mathrm{for} \mathrm{all} \mathrm{j}=1,\dots ,\mathrm{k},{\lambda }_1+{\lambda }_2+\cdots +{\lambda }_{\mathrm{k}-1}>0,{\lambda }_k\ge 1$$

(10)

and such that the first k elements $F_1,F_2,\dots ,F_k$ of $\left(F_n\right)$ are positive. Note that by (9) and (10), the sequence $\left(F_n\right)$ is definitively increasing:

$$F_n>{\lambda }_k{F}_{n-1}\ge F_{n-1}n>k.$$

(11)

In this section, we prove the existence of ${\displaystyle lim{a}_n}$, where

$$a_n=\frac{F_{n+1}}{F_n}n\in \mathbb{N};$$

(12)

for later use, we note that by (9)

$$\begin{array}{cc}\hfill a_n& =\frac{F_{n+1}}{F_n}={\lambda }_1\frac{F_{n-k+1}}{F_n}+{\lambda }_2\frac{F_{n-k+2}}{F_n}+\cdots +{\lambda }_{k-1}\frac{F_{n-1}}{F_n}+{\lambda }_k\hfill \\ \hfill & =\sum _{j=1}^k{\lambda }_{k+1-j}\frac{F_{n-j+1}}{F_n}n\ge k.\hfill \end{array}$$

(13)

As a preliminary remark, we can easily obtain a lower bound for $lim{}^{\prime }{a}_n$ and an upper bound for $lim{}^{″}{a}_n$; in fact, by (11), we have

$$0<\frac{F_{n-j}}{F_n}<1j=1,\dots ,k-1,n\ge k$$

and therefore

$${\lambda }_k<{\lambda }_1\frac{F_{n-k+1}}{F_n}+{\lambda }_2\frac{F_{n-k+2}}{F_n}+\cdots +{\lambda }_{k-1}\frac{F_{n-1}}{F_n}+{\lambda }_k<{\lambda }_1+{\lambda }_2+\cdots +{\lambda }_{k}n\ge k$$

i.e., by (13)

$${\lambda }_k<a_n<{\lambda }_1+{\lambda }_2+\cdots +{\lambda }_{k}n\ge k$$

and by (5)

$${\lambda }_k\le lim{}^{\prime }{a}_n\le lim{}^{″}{a}_n\le {\lambda }_1+{\lambda }_2+\cdots +{\lambda }_k.$$

(14)

Our first result establishes the existence of ${\displaystyle lim{a}_n}$ in the case $k=2$. For the sake of completeness, we included in the statement the (absolutely standard, one-line) proof that the limit is the root of the characteristic equation.

Theorem 1.

If $\left(F_n\right)$ is a positive sequence satisfying

$$F_n={\lambda }_1{F}_{n-2}+{\lambda }_2{F}_{n-1},n\ge 2,$$

(15)

where ${\lambda }_1>0$, ${\lambda }_2\ge 1$, then the sequence $\left(a_n\right)$ defined in (12) is convergent, and its limit is the unique positive root of the equation $x^2={\lambda }_1+{\lambda }_{2}x$.

Proof. 

By (15), we have

$$a_n=\frac{F_{n+1}}{F_n}={\lambda }_1\frac{F_{n-1}}{F_n}+{\lambda }_2=\frac{{\lambda }_1}{a_{n-1}}+{\lambda }_{2}n\ge 2.$$

Note that our assumptions on ${\lambda }_1$ and ${\lambda }_2$ agree with (10) in the case $k=2$; hence, we are allowed to use (14). Setting $\ell =lim{}^{\prime }{a}_n$, $L=lim{}^{″}{a}_n$, we have

$$\ell =lim{}^{\prime }{a}_n=lim{}^{\prime }\frac{{\lambda }_1}{a_{n-1}}+{\lambda }_2\stackrel{\left(6\right)}{=}\frac{{\lambda }_1}{lim{}^{″}{a}_{n-1}}+{\lambda }_2\stackrel{\left(3\right)}{=}\frac{{\lambda }_1}{L}+{\lambda }_2$$

from which

$$\ell L={\lambda }_1+{\lambda }_{2}L;$$

(16)

Similarly,

$$\ell L={\lambda }_1+{\lambda }_2\ell ,$$

(17)

and from (16) and (17), computing the difference, we obtain $0={\lambda }_2(L-\ell )$. Since ${\lambda }_2\ne 0$, we deduce $L=\ell$, i.e., by (4), the convergence of $\left(a_n\right)$. Finally, from (17), setting $\rho =L=\ell$, we have $\rho ={\lambda }_1/\rho +{\lambda }_2$, from which we obtain that $\rho$ is a root of $x^2-{\lambda }_{2}x-{\lambda }_1=0$. Since this equation has two real roots and only one is positive, the proof is over. □

We now deal with the case of recurrences of greater order, and we prove the following:

Theorem 2.

Let $k>2$. If $\left(F_n\right)$ is a positive sequence satisfying (9), (10), and

$$max({\lambda }_1,\dots ,{\lambda }_k)={\lambda }_k\ge k$$

(18)

then the sequence $\left(a_n\right)$ defined in (12) is convergent. Its limit belongs to the interval $[{\lambda }_k,{\lambda }_1+{\lambda }_2+\cdots +{\lambda }_k]$ and is the unique root of the equation

$$x^k={\lambda }_1+{\lambda }_{2}x+\cdots +{\lambda }_{k-1}{x}^{k-2}+{\lambda }_k{x}^{k-1}.$$

(19)

in the interval $[{\lambda }_k,+\infty ]$.

We remark that the last part of the statement is equivalent to stating that the limit is a fixed point; see (25).

Proof. 

For every $n\ge k$, by (13), we have

$$\begin{array}{cc}\hfill a_n& =\sum _{j=1}^k{\lambda }_{k+1-j}\frac{F_{n-j+1}}{F_n}={\lambda }_k+\sum _{j=1}^{k-1}{\lambda }_{k-j}\frac{F_{n-j}}{F_n}\hfill \\ \hfill & ={\lambda }_k+\sum _{j=1}^{k-1}{\lambda }_{k-j}\prod _{i=1}^j\frac{F_{n-i}}{F_{n-i+1}}={\lambda }_k+\sum _{j=1}^{k-1}{\lambda }_{k-j}\prod _{i=1}^j\frac{1}{a_{n-i}}.\hfill \end{array}$$

(20)

Setting as before $\ell =lim{}^{\prime }{a}_n$, $L=lim{}^{″}{a}_n$, we have

$$lim{}^{″}\prod _{i=1}^j\frac{1}{a_{n-i}}\stackrel{\left(7\right)}{\le }\prod _{i=1}^{j}lim{}^{″}\frac{1}{a_{n-i}}\stackrel{\left(6\right)}{=}\prod _{i=1}^j\frac{1}{lim{}^{\prime }{a}_{n-i}}\stackrel{\left(3\right)}{=}\prod _{i=1}^j\frac{1}{\ell }=\frac{1}{{\ell }^j}$$

and therefore, computing the upper limit in (20),

$$\begin{array}{cc}\hfill L& ={\lambda }_k+lim{}^{″}\sum _{j=1}^{k-1}{\lambda }_{k-j}\prod _{i=1}^j\frac{1}{a_{n-i}}\stackrel{\left(8\right)}{\le }{\lambda }_k+\sum _{j=1}^{k-1}{\lambda }_{k-j}lim{}^{″}\prod _{i=1}^j\frac{1}{a_{n-i}}\hfill \\ \hfill & \stackrel{\left(7\right)}{\le }{\lambda }_k+\sum _{j=1}^{k-1}{\lambda }_{k-j}\prod _{i=1}^{j}lim{}^{″}\frac{1}{a_{n-i}}\stackrel{\left(6\right)}{=}{\lambda }_k+\sum _{j=1}^{k-1}\frac{{\lambda }_{k-j}}{{\ell }^j}:=f_{{\lambda }_1,\dots ,{\lambda }_k}(\ell )\hfill \end{array}$$

(21)

Analogously, we obtain $\ell \ge f_{{\lambda }_1,\dots ,{\lambda }_k}\left(L\right)$, so that $f_{{\lambda }_1,\dots ,{\lambda }_k}\left(L\right)\le \ell \le L\le f_{{\lambda }_1,\dots ,{\lambda }_k}(\ell )$, from which

$$L-\ell \le f_{{\lambda }_1,\dots ,{\lambda }_k}(\ell )-f_{{\lambda }_1,\dots ,{\lambda }_k}\left(L\right).$$

(22)

On the other hand, computing the derivative of $f_{{\lambda }_1,\dots ,{\lambda }_k}$, by (10) and (18), we can estimate

$$\begin{array}{cc}\hfill -f_{{\lambda }_1,\dots ,{\lambda }_k}^{\prime }\left(x\right)& =\sum _{j=1}^{k-1}\frac{j{\lambda }_{k-j}}{x^{j+1}}\le \sum _{j=1}^{k-1}\frac{j{\lambda }_{k-j}}{x^j{\lambda }_k}\le \sum _{j=1}^{k-1}\frac{j}{x^j}\hfill \\ \hfill & \le \frac{k-1}{k}\sum _{j=1}^{k-1}\frac{1}{k^{j-1}}=\left(1-\frac{1}{k}\right)\sum _{j=1}^{k-1}\frac{1}{k^{j-1}}\hfill \\ \hfill & =1-\frac{1}{k^{k-1}}<1x\in [{\lambda }_k,+\infty [\hfill \end{array}$$

(23)

We can now deduce that $\ell =L$; if, on the contrary, we would have $\ell <L$, then we could apply Lagrange’s theorem to the interval $[\ell ,L]$ (which by (14) is contained in $[{\lambda }_k,+\infty ]$) and obtain, using (22) and (23),

$$L-\ell \le f_{{\lambda }_1,\dots ,{\lambda }_k}(\ell )-f_{{\lambda }_1,\dots ,{\lambda }_k}\left(L\right)<L-\ell ,$$

(24)

which is absurd. The existence of the limit is therefore proven.

As for the last part of the statement, by (5) and (10), we obtain that $\rho :=lim{a}_n$ belongs to the interval $[{\lambda }_k,{\lambda }_1+{\lambda }_2+\cdots +{\lambda }_k]$, and setting $\ell =L=\rho$ in (21), we have

$$\rho =f_{{\lambda }_1,\dots ,{\lambda }_k}\left(\rho \right)={\lambda }_k+\sum _{j=1}^{k-1}\frac{{\lambda }_{k-j}}{{\rho }^j},$$

(25)

from which, multiplying both sides by ${\rho }^{k-1}$, we obtain that $\rho$ is the root of the Equation (19). We remark that since all the $\lambda$’s are positive and $\rho \ge {\lambda }_k\ge k>1$, we have also

$${\lambda }_k<{\lambda }_k+\sum _{j=1}^{k-1}\frac{{\lambda }_{k-j}}{{\rho }^j}<{\lambda }_1+{\lambda }_2+\cdots +{\lambda }_k,$$

and therefore, from (25) we obtain that $\rho$ belongs to the open interval $[{\lambda }_k,{\lambda }_1+{\lambda }_2+\cdots +{\lambda }_k]$. Finally, setting $\ell ={\rho }_1,L={\rho }_2$ in the left wing inequality of (24), we obtain the unicity of the root of the Equation (19). □

We remark that the roots of (19) are zeros of the polynomial

$$x^k-{\lambda }_k{x}^{k-1}-{\lambda }_{k-1}{x}^{k-2}-\cdots -{\lambda }_{2}x-{\lambda }_1$$

which deserves attention in the literature. We mention Kalantari [38] (Thm 4), where, however, ${\lambda }_k\in \mathbb{N}$ and all other $\lambda$’s equal 1; see also Wu, Zhang [39] (Lemma 1), where $1\le {\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_k$ and all $\lambda$’s are positive integers. Both references arrive at the same conclusion, namely that there exists only one positive real zero in the interval $]{\lambda }_k,{\lambda }_k+1[$ and all other roots have moduli less than unity. Our situation does not fit in these results because our coefficients are not necessarily integers, and we do not need, for our purposes, a so complete study of the polynomial. Interested readers should consult, however, Anatriello, Fiorenza, Vincenzi [16] (Section 2.2).

4. Conclusions

In this paper, we show a method to establish the existence of the limit of the ratios of consecutive terms for a class of order-k linear recurrences of real numbers, studied in the well-developed theory of equations in finite difference/increments. The method, based on the notions of the upper limit and lower limit, is particularly direct and can be used either for educational purposes or for stimulating research on more general order-k recurrences (for instance, nonlinear order-k recurrences).