一個鴿籠原理的簡單應用：模n的斐波那契數列是循環數列

    好久沒寫部落格文章了，前幾天被幾個學生嫌，她們覺得我「墮落了」，那就寫一篇關於最近在準備數論培訓課程裡用到的一個小小題目和有趣的延伸！

    我們校內的培訓講義裡有一道題：

    求證：對任意整數n，存在n的一個倍數，它是僅由數字2與0組成的。

    要解答這問題並不太難，只要考慮集合{2, 22, 222, 2222, ...}，在mod n的時候，至少會有兩個元素同餘，把這兩個數相減的差，就是由2和0所構成，且會被n整除。

    前幾天跟一個科裡的老師在聊，斐波那契數列(Fibonacci sequence: Fn+1 = Fn + Fn-1，F1 = F2 = 1)在mod n (這裡n > 2)的時候的表現，其中有一個直覺上存在的性質，就它會循環。當然我們這裡定義的循環指的是：存在一個正整數p，使得對於任意正整數i，都滿足Fp+i ≡ Fi (mod n)，而滿足這個同餘式最小的p，稱為斐波那契數列在模n時的最小週期。

    要證明「斐波那契數列在模n時會循環」的這個性質，基本上跟上面這培訓講義裡的題目用的方法差不多：

    數列的遞迴關係已經告訴我們，只要知道數列中相鄰的兩數，就能決定下一數為何，而這相鄰兩數在mod n時頂多只有n²種可能，所以考慮集合{(Fi, Fi+1) ∣ 1 ≦ i ≦ n²+1}的元素，在mod n時，必至少有兩組同餘，即Fi ≡ Fj，Fi+1 ≡ Fj+1 (mod n)，因此Fi+2 ≡ Fj+2 (mod n)，以此類推，可得Fi+3 ≡ Fj+3，Fi+4 ≡ Fj+4，…(mod n)，而且遞迴式也可以逆推回去，得Fi-1 ≡ Fj-1，Fi-2 ≡ Fj-2，…(mod n)，一直推回到斐波那契數列的首項，因此若i < j，則j – i就是其循環週期(但不一定是最小循環週期)。故斐波那契數列在模n時從第一項就開始循環，而且最小循環週期必小於n²。

    其實，上面這個證明，並不只適用在斐波那契數列，用同樣的方法，也可以得到任意的二階遞迴關係式，甚至三階、四階、…遞迴關係式，在模n時都會循環，只是並不能保證是否都是由首項就開始循環。

斐波那契數的矩陣表示法及兩個相關公式

斐波那契數列(Fibonacci Sequence)的遞迴式是f₀=0，f₁=1，f_k+1=f­_k+f_k-1，其中k為任意的自然數。可以利用

(1)                      

的關係，以及的特徵值(eigenvalues)為、，以及相對應的特徵向量(eigenvectors)分別為、，得到

                   

 ，對應(1)的矩陣中的元，即可得

。

(以上的內容，亦可參考前一篇：The general term of the Fibonacci Sequence)

 利用(1)，取行列式值，即可得

(2)                                                              。

 同樣由(1)，取k=m+n，因為

計算矩陣的第(2,2)的元，可以得到

(3)                                                            。

當然，也可以利用數學歸納法得到(2)和(3)的結果。

觀察下面的圖形，其中∠B為直角，，的長度分別為f_2n、f_2n+1、f_2n+2，很容易推得的長度分別為f_2n-1和f_2n+1。

取(2)中的k=2n，移項後得f_2n-1f_2n+1＝1+ f_2n ²，即，若且唯若，故由SAS相似性質知，三角形ACD～三角形ECA，故∠CAD＝∠AEC＝α，所以三角形ACD的外角θ＝α+β，即 

。

The general term of the Fibonacci Sequence

The Fibonacci sequence <F_n> :0, 1, 1, 2, 3, 5, 8, 13, 21,… which satisfies F₀=0, F₁=1, and F_k+2=F_k+1+F_k. The goal of this article is to find the general form of the k^th term  F_k of  the Fibonacci sequence.

Let .

Consider , that is u_k+1= Au_k , where .

Because the characteristic polynomial of A is, the eigenvalues of A areand, and the corresponding eigenvectors are and . Of course {x₁, x₂} are linearly independent and generate u_k.

Write u₀=c₁x₁+c₂x₂, that is, and it’s easy to solve the coefficients and  . Hence

u₁=c₁Ax₁+c₂Ax₂= c₁λ₁x₁+c₂λ₂x₂ ,

 … ,

u_k=c₁A^kx₁+c₂A^kx₂= c₁λ₁^kx₁+c₂λ₂^kx₂
 .

Thus

.