等比数列は漸化式
と初項により決定される数列であった。実際 a_0=d ならば a_n=dr^n となる。
これを一般化して、漸化式
と、最初の ''m'' 項により決定される数列が考えられる。これを ''m'' 階の線形回帰数列あるいは線形循環数列という。
イタリアの数学者フィボナッチは、次の問題を考えた。産まれたばかりの1つがいの兎がいるとする。1つがいの兎は、産まれて1ヶ月後には兎を産むことはないが、2ヶ月後から毎月1つがいずつの兎を産む。産まれてきた1つがいの兎もまた同様、産まれて2ヶ月後から毎月1つがいずつの兎を産み、以下産まれてきた1つがいの兎も同様とする。兎が死ぬことはないとして、産まれたばかりの1つがいの兎は1年の間に何つがいの兎にまで増えるだろうか？
''n'' ヶ月目に a_n つがいの兎がいるとすると、これらの兎のつがい達は、その2ヶ月後、つまり n+2 ヶ月目には1つがいずつの兎を産む。一方 n+1 ヶ月目に産まれた兎は n+2 ヶ月目には兎を産まない。つまり n+2 ヶ月目には a_n つがいの兎が新しく産まれる。よって
が成り立つ。一方、1ヶ月目には1つがいの兎がおり、2ヶ月目には兎を産むことはないので a_1=a_2=1 である。つまり a_n は
により定まるので、2階の線形回帰数列である。
そこで、これにより定まる数列をフィボナッチ数列といい、最初の数項は (0, )1, 1, 2, 3, 5, 8, 13, ... で与えられる。計算していくと a_{12}=144, a_{13}=233 となり、1年後には144つがいの兎がいることになるが、ちょうど1年後に89つがいの兎が産まれるのとあわせれば、233つがいの兎がいることになる。
a_{n+2}=Aa_1+Ba_0 で与えられる2階の線形回帰数列の最初の数項は
\begin{align}
a_2 = & Aa_1+Ba_0, \\
a_3 = & (A^2+B)a_1+ABa_0, \\
a_4 = & (A^3+2AB)a_1+(A^2B+B^2)a_0, \\
a_5 = & (A^4+3A^2B+B^2)a_1+(A^3B+2AB^2)a_0, \\
a_6 = & (A^5+4A^3B+3AB^2)a_1+(A^4B+3A^2B^2+B^3)a_0
\end{align}
により与えられる。
まず、等比数列自身が上記の漸化式 (1) を満足する。実際 \alpha を方程式
の解とすると
を \alpha^n 倍し、
を得る。よって数列 a_n=k\alpha^n は漸化式 (1) を満足する。
このことから \alpha_1, \alpha_2, \ldots, \alpha_r を方程式 (2) の解とすると
も漸化式 (1) を満足する。
ここで、方程式 (2) がちょうど
''m'' 個の相異なる複素数解 \alpha_1, \alpha_2, \ldots, \alpha_m を持つとする（代数学の基本定理より、
''m'' 次方程式は重解を持たなければちょうど ''m'' 個の相異なる解を持つ）。
このとき漸化式 (1) を満足する数列が (4) の形のものしかないことを確かめる。
実際 b_1, b_2, \ldots, b_m を連立方程式
\begin{cases}
b_1+b_2+\cdots b_m & = a_0, \\
b_1\alpha_1+b_2\alpha_2+\cdots b_m\alpha_m & = a_1, \\
\ldots \\
b_1\alpha_1^{m-1}+b_2\alpha_2^{m-1}+\cdots b_m\alpha_m^{m-1} & = a_{m-1} \\
\end{cases}
\cdots (5)
の解とする。これはヴァンデルモンドの行列式に対応するので
\alpha_1, \alpha_2, \ldots, \alpha_m が相異なるときこの連立方程式は必ず解を持つ。
このとき
が k=0, 1, \ldots, m-1 について成り立つ。そうすると (3) と数学的帰納法より
任意の ''k'' について (6) が成り立つ。よって a_n は (4) の形で与えられる。
つまり、次の定理が成り立つ。
方程式 (2) がちょうど ''m'' 個の相異なる複素数解 \alpha_1, \alpha_2, \ldots, \alpha_m を持つとする。
このとき (6) の形の数列はすべて漸化式 (1) を満足し初項は (5) によって与えられる。
逆に (1) の漸化式を満足する数列は連立方程式 (5) の解 b_1, b_2, \ldots, b_m により、(6) の形で与えられる。
{2} に対し、
であらわされる。