Quod Erat Demonstrandum

2012/12/31

費波那契數之和

Filed under: Pure Mathematics — johnmayhk @ 4:33 下午
Tags:

以下是費波那契數列(Fibonacci sequence):

F_1=1
F_2=1
F_3=F_2+F_1=2
F_4=F_3+F_2=3
F_5=F_4+F_3=5
F_6=F_5+F_4=8

… …

原來「任何正整數皆可寫成若干不同的(distinct)費波那契數之和」,

比如

4=1+3=F_1+F_4
6=1+2+3=F_1+F_3+F_4
7=2+5=F_3+F_5

… …

用強 M.I.(strong mathematical induction)證之。

設命題為 P(n):「正整數 n 可寫成若干不同的費波那契數之和」。

1=F_1

P(1) 成立。

假設對任意正整數 m < kP(m) 成立。

F_i 為最大的費波那契數使 F_i < k

由 M.I. 假設,知

k-F_i 可「寫成若干不同的費波那契數之和」。

F_i 的定義,知 k\le F_{i+1},所以

k-F_i\le F_{i+1}-F_i=F_{i-1}

即是說,k-F_i 最大可能都是 F_{i-1}

由於

k=F_i+(k-F_i)

所以 k 可表成若干不同的費波那契數之和。亦即任何正整數皆可寫成若干不同的費波那契數之和。

廣告

2 則迴響 »

  1. 須個別展示 n=2 嗎?

    迴響 由 Peter Wong — 2013/01/01 @ 12:00 上午 | 回應


RSS feed for comments on this post. TrackBack URI

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: