題 序列 定義為

分析 這個(gè)數(shù)列的遞推關(guān)系有兩種選擇，因此可能的序列有很多。我們先寫出一些項(xiàng)，因?yàn)檫@是二階遞推數(shù)列，所以至少要保留相鄰兩項(xiàng)才能算出下一項(xiàng)。

從 開(kāi)始，接下來(lái) 或 ， 給出 ， 給出 或 ，發(fā)現(xiàn) 重復(fù)。接下來(lái) 給出 或 , 給出 或 ， 給出 或 ， 和 重復(fù)。把重復(fù)出現(xiàn)的合并，把可以成為相鄰項(xiàng)的連邊，可以得到下面的圖。

從圖中左下角開(kāi)始，向右或向上走出的路徑都給出滿足題目條件的序列。觀察最下面一行可以寫成 ，倒數(shù)第二行可以寫成 ，因此猜測(cè)圖中位于 位置的項(xiàng)是 ?？梢詺w納證明這一點(diǎn)，從而得到題目的證明。

證明 我們歸納證明存在非負(fù)整數(shù)序列 ，使得 ，并且 ，，。當(dāng) 時(shí)，，，命題成立?，F(xiàn)在假設(shè)

并且 和 一個(gè)為1，另一個(gè)為0。

如果 ，取 ，命題成立。

如果 ，根據(jù) ，，可知 ，， 是水平或者豎直的三個(gè)連續(xù)整點(diǎn)，命題依然成立。

因此數(shù)列中的每一項(xiàng)都是 的形式。若 ，，不妨設(shè) 。必然有 ，于是 ，矛盾。

因此數(shù)列的項(xiàng)不會(huì)出現(xiàn)在 中。

換種方式想一想，二階遞推數(shù)列把相鄰的兩項(xiàng)組合成向量，則下一個(gè)向量和這一個(gè)的關(guān)系是線性關(guān)系。兩種不同的遞推方式意味著乘以兩個(gè)不同的矩陣。也就是說(shuō)，如果 ，那么

如果這兩個(gè)矩陣分別記為 ，則 是 任選 的序列左乘 次的結(jié)果。現(xiàn)在讓這個(gè)題目變得可以不太復(fù)雜地解決的關(guān)鍵是 滿足的乘法關(guān)系，具體是 ，。前者顯然，后者可以驗(yàn)證如下

因此 的任何乘積序列可以把 的偶次冪提出變成 （是數(shù)量矩陣，和所有矩陣乘法交換）， 提出一個(gè) 去掉兩個(gè) ，最后得到 或者 的形式，再把 寫回 ，于是得到 的形式。

也就是說(shuō)， 總是可以從 開(kāi)始，經(jīng)過(guò) 步 的迭代，然后經(jīng)過(guò) 步 的迭代得到。