一題遞迴,兩個妙解(筆記)

Posted: 2011 年 11 月 14 日 in 數學

最近被問了一題題目如下:

a^{2}-3a+1=0,求 a^{2^{2007}}+a^{-2^{2007}}

正解: a^{1}+a^{-1}=3, a^{2}+a^{-2}=3^{2}-2=7, a^{4}+a^{-4}=7^{2}-2=7.

a^{2^{n+1}}+a^{-2^{n+1}}=(a^{2^{n}}+a^{-2^{n}})^{2}-2,\, \ldots7.

另解:說起另解,就要說說那天的事。

那天被問了這題之後,那人又補了一句「有算出 a^2 是黃金比」。

就讓寸絲腦中閃過平方的想法,消失了,取而代之的 Fibonacci 數列。

結果是 a 是黃金比的平方。

\lambda_{1}=\frac{1+\sqrt{5}}{2}, \lambda_{2}=\frac{1-\sqrt{5}}{2},則 a=\frac{3+\sqrt{5}}{2}=\lambda_{1}^{2}, a^{-1}=\lambda_{2}^{2}

b_{n}=\lambda_{1}^{n}+\lambda_{2}^{n}, 則 b_{0}=2, b_{1}=1

所求 a^{2^{2007}}+a^{-2^{2007}}=\lambda_{1}^{2\cdot2^{2007}}+\lambda_{2}^{2\cdot2^{2007}}=b_{2^{2008}}

只看個位數 \{b_{n}\mbox{ mod }10\}=\{2,1,3,4,7,1,8,9,7,6,3,9,2,1\}\Rightarrow 12 個環循。

2^{2008}=4^{1004}, 而 4^{2}=4 mod 12

所以 4^{1004}\equiv4^{1003}\equiv\ldots\equiv4 mod 12

所以 b_{2^{2008}} 的個位數和 b_{4} 相同為 7

另解雖然費了一番功夫,但是 指數部分不需要 2 的 冪次,任次正整數都可以用。

花一番功夫,還是有代價的。不過這樣的遞迴數列的循環節也有可能很大(1~100),

像是從另解的也可衍生出 x_{n+2} = 3 x_{n+1} - x_{n} 的遞迴方式,

但是稍微寫了一下,還寫不出循環節,就放棄了…

廣告

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s