【問題】數學競試問題

[KID1412 10]

1.

數列1,2,3,4,5,10,20,40,80....前五項成等差，第五項起為等比

試証所有正整數都可以表成此數列中元素的和。

感謝weiye的回答

2.

費式數列(Fibonacci Numbers):1,2,3,5,8,13,21,34......

試証所有正整數n都可表成不重複的費式數的和。

[weiye 10]

數列1,2,3,4,5,10,20,40,80....前五項成等差，第五項起為等比

試証所有正整數都可以表成此數列中元素的和。

此數列1,2,3,4,5,10,20,40,80....

其實就是 1, 2, 3, 4, ,5*2^0 , 5*2^1, 5*2^2, 5*2^3, 5*2^4, ...

對任意正整數 M ，被 5 除之後，

假設餘數為r，則 r 屬於 {1,2,3,4}，

將商以唯一的二進位表示法寫為 an*2^n + an-1*2^(n-1) + ... + a1*2 + a0

其中 an=1 且 an-1, an-2, ..., a1, a0 屬於 {0,1}

亦即

M = 除數 * 商 + 餘數

　= 5*(an*2^n + an-1*2^(n-1) + ... + a1*2 + a0) + r

　= an*5*2^n + an-1*5*2^(n-1) + ... + a1*5*2 + a0*5 + r

其中 r 為此數列的前四項之中的一個，

若 ai=1 ，則表示有加上 5*2^i (這個數字是此數列中的第 i+4 項)

若 ai=0 ，則表示沒有加上 5*2^i (這個數字是此數列中的第 i+4 項)

[KID1412 10]

thank you

[KID1412 10]

再請教一類似問題

費式數列(Fibonacci Numbers):1,2,3,5,8,13,21,34......

試証所有正整數n都可表成不重複的費式數的和。

但這題似乎不能依樣畫葫蘆

[weiye 10]

再請教一類似問題

費式數列(Fibonacci Numbers):1,2,3,5,8,13,21,34......

試証所有正整數n都可表成不重複的費式數的和。

但這題似乎不能依樣畫葫蘆

費式數列(Fibonacci Numbers):1,2,3,5,8,13,21,34......

把這些數列各分別稱作是　　f1,f2,f3,f4,f5,f6,f7,f8...

先觀察一些現象

觀察一：

對任何 n ≧3, fn=fn-1 + fn-2 ＞fn-1 且 已知 f2＞f1

所以任何 n ≧2, fn ＞fn-1 　

（寫了這麼多廢話只是為了說，這是一個嚴格遞增數列啦）

觀察二：

對任何 n ≧3, 2*fn-1 = fn-1 +fn-1 ＞ fn-1 +fn-2=fn

　　　　　　　　　　　　　(↑不等號的理由是上面的觀察一)

把 2*fn-1 ＞ fn 兩邊同時減 fn-1 可得 fn-1 ＞ fn－fn-1

觀察三：

對任何正整數 n ，如果 n = fi, for some i

那也就直接得証命題啦。

也就是說，我們真正要證的是

當 fi< n <fi+1, for some i ，則 n 可以表示成此 f1,f2,...,fi 中不重複選取之和。

好吧，那就用數學歸納法証明好了。

就從有缺數字的 f3～f4 ( i=3 的時候 )開始好了。

第一步：當 i = 3 的時候，對任意自然數 n 滿足 f3＜n＜ f4，則 3＜n＜ 5，可得 n = 4 ，且 n = 4 = 1+3 = f1+f3 ， n 可以表示成 f1,f2,f3中不重複選取之和。

第二步：假設，對任意自然數 i＝3,...,k ，對任何自然數 n ，當 fi< n <fi+1, for some i ，則 n 可以表示成此 f1,f2,...,fi 中不重複選取之和。

則當 i=k+1 時，對任何自然數 n 滿足 fk+1< n <fk+2，

n=fk+1　+　（n－fk+1）

　　　　　^^^^^^^^∵觀察二及 fk+1< n <fk+2 ，所以（n－fk-1）< fk+1恆成立。

故 （n－fk-1）= fi, for some 1≦i≦k 或是

fi<（n－fk-1）<fi+1, for some i =3,...,k 由歸納法假設，可知 （n－fk-1）可以表示成此 f1,f2,...,fi 中不重複選取之和。

故 n=fk+1　+　（n－fk+1）可以表示成此 f1,f2,...,fk 及fk+1 中不重複選取之和。

由第一步＆第二步，及數學歸納法可知 當 fi< n <fi+1, for some i ，則 n 可以表示成此 f1,f2,...,fi 中不重複選取之和。