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

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在 WordPress.com 建立免費網站或網誌.

%d 位部落客按了讚: