【問題】兩個費布納契數列的問題

[曾阿牛 10]

嗯...　應該不用翻成中文了吧

Let m and n be natural numbers, and let f_n denote the nth Fibonacci number.

1. Prove that (f_n)^2 ＋ [f_(n+1)]^2 ＝ f_(2n+1) for each natural number n

2. Prove that if m divides n, then f_m divides f_n.

[00 10]

直接用一般項公式xd，

(f_n)=(a^n-b^n)/sqrt5 其中a=(1+sqrt5)/2, b=(1-sqrt5)/2

a+b=1 且ab=-1

第一題

(f_n)^2 ＋ [f_(n+1)]^2 - f_(2n+1)

=(a^2n+b^2n-2a^nb^n)/5+(a^(2n+2)+b^(2n+2)-2a^(n+1)b^(n+1))/5-(a^(2n+1)-b^(2n+1))/sqrt5

由於ab=-1所以藍色部分對消

=(a^2n+b^2n)/5+(a^(2n+2)+b^(2n+2))/5-(a^(2n+1)-b^(2n+1))/sqrt5

整理得

=(1/5+(a^2)/5-a/sqrt5)a^2n+(1/5+(b^2)/5+b/sqrt5)b^2n

綠色部分帶入a和b的數值就可以算出是0了

第二題

設n=km,k是正整數

(f_km)/(f_m)

=(a^km-b^km)/(a^m-b^m)

令a^m, b^m是A,B

=(A^k-B^k)/(A-B)

=A^(k-1)+A^(k-2)B....+B^(k-1)

由於a+b=1 且ab=-1

AB=a^mb^m明顯是整數

A^t+B^t=a^mt+b^mt=a^s+b^s

t是任意正整數 s=mt

由於a+b=1,a^2+b^2=3是整數

若a^s+b^s是整數可得a^(s+1)+b^(s+1)也是整數

a^(s+1)+b^(s+1)=(a^s+b^s)(a+b)-ab(a^(s-1)+b^(s-1))

數學歸納法可知對於所有正整數s,a^s+b^s是整數

此式A^(k-1)+A^(k-2)B....+B^(k-1)

第x項和倒數第x項配對

不難用AB 和 A^t+B^t表示

所以A^(k-1)+A^(k-2)B....+B^(k-1)是整數，證畢。

[john84 10]

這個好像不是高中的東西

[Smile=*- 10]

這個好像不是高中的東西

我記得高中有講到啊

就是學數列和遞迴那部份==

其實費伯那契數列就是指費氏數列

典型的數列就像以下

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,....

前面兩數和等於之後的數反覆下去

之前高中有應用到爬樓梯和蜂巢問題@_@

應該記得吧

這些就應用到費伯那契數列原理

不過好像只是沒有講很深的樣子

[曾阿牛 10]

Re #2　　嗯嗯　用費式數列的通式來解　真是個爽直的做法

個人最近在複習歸納法　也曾經看過有人用歸納法來解這兩題

其中第一題需要很妙的手法來做　　第二題需要仰賴其他公式　　都不簡單

[00 10]

Re #2　　嗯嗯　用費式數列的通式來解　真是個爽直的做法

個人最近在複習歸納法　也曾經看過有人用歸納法來解這兩題

其中第一題需要很妙的手法來做　　第二題需要仰賴其他公式　　都不簡單

如果找到不用一般式的做法，麻煩樓主貼出來摟，還滿想看的。:)

[曾阿牛 10]

是的　感謝大大的捧場　大大若想看　在下會讓大大看的

但為了增加趣味性　我只先將關鍵的部分點出　

如果大大還是需要完整的過程的話　　可以再知會我

第一題　如果直接證　對於任何 n,　(f_n)^2 ＋ [f_(n+1)]^2 ＝ f_(2n+1).　會遭遇困難的

技巧是　用歸納法 證明　對於任何 n,

(f_n)^2 ＋ [f_(n+1)]^2 ＝ f_(2n+1) 且 2．f_n．f_(n+1) ＋ (f_(n+1))^2 ＝ f_(2n+2)

也就是說　同時證以上的兩個等式　　這樣就可以解了

第二題可以利用　 f_(n+k) ＝ f_k．f_(n+1) ＋ f_(k-1)．f_n　來證明

其中　第一題為什麼會冒出那樣的等式出來　其實也是有跡可循的　

如果大大需要完整的過程的話　到時再一併說明　... 就先這樣囉

[夢境的行旅 10]

搶頭香啊!!!!

==================================================

(正文)

其實在版主的提示下解答就昭然若揭了

證明使用的是一種 很特別的數學歸納法

簡單扼要的說就是樓主指出的兩個式子

有這樣互相依附的關係

只要兩式相加就可以證明下一個等式

證明過程:

Step 1 驗證對於n=1 (或0) 兩式皆成立

Step 2 把上圖的遞迴關係，計算過程寫清楚。只要利用費氏數列的定義式展開即可。

Step 3 去刻一個印章

「由數學歸納法得證，對於所有　　　　　　原式　　　　　　　　　　恆真」

Step 4 以本題為例兩個空格分別填上

「由數學歸納法得證，對於所有　自然數n　原式　 Fn^2+Fn+1^2=F2n+1 　恆真」

原子筆水是很珍貴的......節能減碳救地球

[夢境的行旅 10]

　想想，這個技巧還蠻不可思議的

　這個恆等式就像一個　壓縮自解檔，從原本欲證的恆等式就可以(偷偷) 推出另一個式子

　然後兩個式子立刻可以　彼此證明，什麼軟硬體需求、驅動程式、作業系統相容性都不相關了

[夢境的行旅 10]

不知道這個式子的人......束手無策。但版主貼出來之後就萬事OK

(1-1) 這個等式的形式蠻複雜的 我剛剛是用 類似微分公式「前微後不微」來記的

但是一個是加1，另一個減1，因此有兩種可能。

(1-2) 等式的證明　　兩式相加等於第三式似乎就是 「費氏數列專用數學歸納法」的意思。

先驗證上面的兩式對於 n=1 , k=1 時成立

(補充 根據定義 F0 = 0)

然後把上面用過的印章拿出來，以下步驟你知道了......:E (是n、k「二維」的歸納法)

(1-3)用來證明原命題

設n=km 然後套用公式會是這樣，右邊第一項是Fm的倍數

，然後第二項因為有F(k-1)m 可以繼續代入公式，因此遞降到最後必定是Fm的倍數

或者把步驟倒過來，再度使用數學歸納法 －－你看，叫你去刻個印章是多明智的建議啊！:p

這個命題的逆命題對不對？ 樓下請解答。

[howt 10]

提供一些組合上的想法證明較為廣義的式子

考慮一個 2×n 的長方區塊，若用1×2的長方形去拼，有幾種方法?

若令方法有G(n)種，很容易可以導出 G(n+1)=G(n)+G(n-1)，且G(n)=F(n+1)

那麼再考慮G(m+k)，很容易也可導出 G(m+k)=G(m)G(k)+G(m-1)G(k-1) .........(1)

在(1)式中令 k = n-1 ，即得到 G(m+n-1)=G(m)G(n-1)+G(m-1)G(n-2)

=> F(m+n) = F(m+1)F(n)+F(m)F(n-1)即為所求

若在 (1)式中令 m=m-1、k=n-1，則類似步驟可得

F(m+n-1)=F(m)F(n)+F(m-1)F(n-1)

第一個式子在這問題中，代表的是長2n的長方形鋪法，可以從中分割，共兩種分法

另外補充樓上，反命題成立

證明如下

pF(n) = F(m) = F[ (m-n) + n] = F(m-n+1)F(n) + F(m-n)F(n-1)

=> F(n) | F(m-n)F(n-1) ，但F(n-1)與F(n)互質(這用輾轉相除即可證之)，因此F(n) | F(m-n)

同理可推得 F(n) | F(m-kn)，倘若 m = qn+r ，0< r <n，會得到 F(n) | F® ，矛盾 !

[夢境的行旅 10]

樓上的證明補充，因為

F(n-1)與F(n)互質

所以同理原命題要扣除掉F(n) | F(m) 但n 是1 或 2 的情形。F(1)=F(2)=1 !!!