題目：
若 Rn=21an+bn ，其中 a=3+22b=3−22 ，且 n=0123。試問 R12345 的個位數為何？


解答：

因為 a+b=6 且 ab=1，所以 ab 為 x2−6x+1=0 的兩根，

a2−6a+1=0 且 b2−6b+1=0

an+2−6an+1+an=0 且 bn+2−6bn+1+bn=0n=0123

an+2+bn+2−6an+1+bn+1+an+bn=0n=0123 

21an+2+bn+2−621an+1+bn+1+21an+bn=0n=0123 

Rn+2−6Rn+1+Rn=0n=0123

Rn+2=6Rn+1−Rnn=0123

且由 R0=1R1=3，就可以開始條列，如下

n	0	1	2	3	4	5	6	7
Rn 除以10的餘數	1	3	7	9	7	3	1	3

列到開始有兩位數字跟前面一樣，就可以停止了（因為由遞迴關係式可知，每一項只與前兩項有關，故若前兩項相同，後面的結果亦相同）

由上表可以知道 Rn 除以 10 的餘數每六個數字一循環，而 12345 除以 6 的餘數為 3，

故，R12345 除以 10 的餘數=R3 除以 10 的餘數=9

補上出處，96和美高中
這類題目的遞迴式我都是這樣寫的
21(an+1+bn+1)=(a+b)21(an+bn)−(ab)21(an−1+bn−1)
得到Rn+1=6Rn−Rn−1

[ 本帖最後由 bugmens 於 2009-6-25 06:42 AM 編輯 ]

想請教我的做法哪裡錯了?感謝~
a3+b3=198a3b3=1
2R_n=(a^3)^n+(b^3)^n
2R_1=a^3+b^3=198
2R_2=a^6+b^6=198^2-2==>2
2R_3=a^9+b^9==>198*2-1*198==>8
so, R為2循環:4,1,4,1,... 所求為n=4115時,所以答案為4

[ 本帖最後由 idontnow90 於 2013-6-3 12:00 AM 編輯 ]

遞迴關係式可知，每一項只與前兩項有關，故若前兩項相同，後面的結果才會相同

因此不能只看一項出現，必須要看連續兩個出現與前面重複，才可以保證重複。



另外， 2\times\mbox{某數}\equiv 8\pmod{10}，並不保證 \mbox{某數}\equiv4\pmod{10}

例如：2\times9\equiv8\pmod{10}，但是 「9 並不同餘 4\pmod{10}」

這是因為 2 與 10 並不互質，因此在 \pmod{10} 的剩餘系統中，並不存在 2\pmod{10} 的乘法反元素，

即「不存在整數 a，使得 a\times 2\equiv1\pmod{10}」，

因此無法在左右都是偶數的同餘式中～以左右同乘 a\pmod{10} 來消掉 2\pmod{10}。

另解：

因為 \left(3\pm2\sqrt{2}\right)^3=99\pm70\sqrt{2}



所以 \displaystyle\frac{1}{2}\left(\left(3+2\sqrt{2}\right)^{12345}+\left(3-2\sqrt{2}\right)^{12345}\right)

　　　\displaystyle=\frac{1}{2}\left(\left(99+70\sqrt{2}\right)^{4115}+\left(99-70\sqrt{2}\right)^{4115}\right)

　　　　（將上式以二項式定理展開後合併，偶數項都會對消掉，
　　　　　奇數項都會有兩倍與最外面的 \frac{1}{2} 相消，
　　　　　消掉兩倍之後的奇數項～除第一項以外～其餘都是 10 的倍數，）

　　　\equiv 99^{4115}\pmod{10}

　　　\equiv\left(-1\right)^{4115}\pmod{10}

　　　\equiv-1\pmod{10}

　　　\equiv9\pmod{10}

那這樣想再請教一下我下面這兩題這樣做會對..純粹是巧合嗎??謝謝

請教這個會對也是巧合嗎?
便利貼上寫得是這個做法..白紙上寫得是原本的做法

[ 本帖最後由 idontnow90 於 2013-6-3 09:37 PM 編輯 ]

這樣寫會對沒錯呀，

但是最好多檢查到餘數是 0,8,0,2,0,8

發現有兩數字 0,8 開始重複了，

就可以確定餘數是以 0,8,0,2 的方式循環。

否則你可以想看何以判斷餘數是「四個」一循還？還是「兩個」一循環？還是「三個」一循環？還是「多少個」一循環呢？

由 a_n=10a_{n-1}-a_{n-2} 可以知道要檢查到有兩個連續的餘數開始重複出現，才能確定開始循環了。

或是再加上簡單說明 a_n=10a_{n-1}-a_{n-2}\Rightarrow a_{n}\equiv-a_{n-2}\pmod{10}\Rightarrow a_{n}\equiv-a_{n-2}\equiv a_{n-4}\pmod{10}

因此，可知 a_n\pmod{10} 會四個一循環。

引用:

原帖由 weiye 於 2013-6-3 09:50 PM 發表

發現有兩數字 0,8 開始重複了，

就可以確定餘數是以 0,8,0,2 的方式循環。

.

那這樣我有點搞混了ㄟ..
如果說剛剛那題目(我們先撇開那個2倍的錯誤不看..)
是S_n=(a^3)^n+(b^3)^n, S_1=8, S_2=2,  S_3=8, S_4=2,他也是連續兩數字 8,2 重複

但是現在這題a_n=(p^2)^n+(q^2)^n, a_1=0,a_2=8,a_3=0,a_4=2他也是連續兩數字 0,8 重複

為什麼一題會對一題會錯??他們得遞迴式都是跟前兩項有關阿??

抱歉..搞不太清楚.還請賜教.感謝~

你後來手寫回覆的這一題不是連續兩個數字 0,8 重複呀，

你看看你手寫的內容，明明就是 0,8,0,2 連續四個數字的重複呀。

還有你第一次回文的 2R_n\pmod{10} 是兩個數字重複沒錯，但是 R_n\pmod{10} 並不見得就會是兩個數字重複呀！

（2R_n\pmod{10} 我只是點出你並沒有充分的檢查～並不是說循環長度有誤！）