253 名前：１３２人目の素数さん[sage] 投稿日：2005/08/31(水) 02:22:32
数列{f(n)}はf(0)＝0，f(1)＝1，f(n＋1)＝f(n)＋f(n－1) (n＝1，2，3…)を満たす。
A＝{f(i)｜i＝0，1，2，…}とおく。以下の問いに答えよ。
(1)B＝{Σ[i＝1～∞]f(xi)｜自然数列{xn}は有限項を除いて0}＝Σ[i＝1～∞]Aとおく。B＝N∪{0}を示せ。
(2)C＝{Σ[i＝1～∞]f(xi)｜自然数列{xn}は有限項を除いて0であり、xi＝xjならばxi＝xj＝0}
＝(Aの異なる元を有限個足した数全体の集合)⊂Bとおく。C＝N∪{0}を示せ。
(3)自然数mに対して、Bm＝{Σ[i＝1～∞]f(xi)｜自然数列{xn}は、第m＋1項目から全て0}
＝Σ[i＝1～m]A ⊂B とおく。集合系{Bm}には極限集合が存在し、lim[m→∞]Bm＝B と
なることを示せ。また、Bm＝N∪{0}を満たす自然数mは存在するか？
255 名前：253[sage] 投稿日：2005/08/31(水) 12:19:00
ちょっと表現に不都合が…
>>253に出てくる「自然数列{xn}」は、全て「非負整数列{xn}」に置き換えて下さい。
解答
256 名前：１３２人目の素数さん[] 投稿日：2005/09/01(木) 19:12:17
>>253
(1) 1をいっぱいつかっていいので簡単
(2) 任意の自然数(正の整数とする)が異なるフィボナッチ数列内の数の和で表示できるという
意味と解してa≦xnなる自然数aは可能であることをnに関する帰納法でしめす。
(I)n=0のときa≦x0=0なる自然数aは存在しないゆえ成立。
(II)n=1のときa≦x1=1ならa=1ゆえ成立。
(III)n≧2に対しn未満まで正しいとしてa≦xnをとる。a≦x(n-1)なら帰納法の
仮定からよい。x(n-1)＜a≦xnのときは0＜a-x(n-1)≦xn-x(n-1)=x(n-2)ゆえ
a-x(n-1)=∑y(i)、y(i)は相異なるフィボナッチ数列内の数がとれる。a-x(n-1)≦x(n-2)
ゆえy(i)の中にx(n-1)は入らない。よってaも相異なるフィボナッチ数列内の数の和で表示可能。
(I)～(III)で示された。
(3)F={x(i)|i≧1}とおく。n≧3にたいして単調増大有限列y1<y2<･･･<ykが
∑yi=-1+xn、yi∈Fをみたすときk≧[(n-1)/2]をみたすことを示す。
(I)n=3,4なら[(n-1)/2]=1ゆえ明らか。(∵yiの項数は1以上。)
(II)n≧5にたいしてn未満についての主張を仮定する。単調増大有限列y1<y2<･･･<ykが
∑yi=xn-1、yi∈Fをみたすと仮定する。yk<x(n-1)のとき∑[1≦i≦n-2]x(i)=-1+xnにより
k=n-2、y(i)=x(i)でなければならない。このときk=n-2＞(n-1)/2≧[(n-1)/2]ゆえ成立。
yk=x(n-1)のときは∑[i<k]y(i)=-1+xn-x(n-1)=-1+x(n-2)。よって帰納法の仮定よりk-1≧[(n-3)/2]。
よってk≧[(n-1)/2]。
(I),(II)で示された。
287 名前：名無しさん＠そうだ選挙に行こう[] 投稿日：2005/09/11(日) 16:02:00
>>277
>>253
こんな解答ができた。
(3)問題を次によみかえる。
＠＠＠＠ 問題 ＠＠＠＠
x(i)をフィボナッチ数列、つまりx(1)=1,x(2)=1,x(n+2)=x(n+1)+x(n) (n≧0)とする。
有限個をのぞいて全部0である非負整数列の集合をCとする。J(c)を∑c(i)でさだめ
n∈Nに対してE(n)をmin{J(c) | ∑c(i)x(i)=n}でさだめる。{E(n)}は有界でないことをしめせ。
＠＠＠＠ 解答 ＠＠＠＠
c∈Cに対してJ’(c)をJ(c)-(1/2)#{i | c(i)=1}でさだめ、n∈Nに対しE’(n)を
min{J’(c) | ∑c(i)x(i)=n}で定める。次は綺麗な証明が見つからないのでみとめる。
補題 任意のnとn=∑c(i)x(i)であるc∈Cにたいしてc’∈Cで
n=∑c(i)x(i)、J’(c’)≦J’(c)、c’(i)≦1 (∀i)なるc’がとれる。
これをみとめる。F(n)をmin{#I | ∑[i∈I]x(i)=n}でさだめる。すると
(1/2)F(n)≦E’(n)≦E(n)が成立する。実際補題よりE’(n)=J’(c)、c(i)≦1である
c(i)がみつかる。このとき∑c(i)x(i)=∑[c(i)=1]x(i)より∑c(i)≧F(n)。さらにJ’(c)の定義と
c(i)≦1より∑c(i)=2J’(c)。∴(1/2)F(n)≦E’(n)。一方でJ’(c)≦J(c)からE’(n)≦E(n)は明らか。
さて>>256によりF(x(n)-1)≧[(n-1)/2]である。（ちなみに“＝”になる。）
よってE(x(n)-1)≧(1/2)[(n-1)/2]であるからE(n)は有界でない。
補題の証明なんだけど結構ながい。書く気にならん。どうしたもんだろ。
289 名前：253[] 投稿日：2005/09/11(日) 23:04:43
>>256
(1)，(2)大正解です。
>>287
うおお…合ってそうだが俺には判断できぬ。
一応、考えていた(3)の解答を書いておきます(概要のみ)。
m∈Nを、Bm＝N∪{0}が成り立つ自然数とする。このとき、V＝Σ[a∈Bm－{0}]1/aは発散する
ことになる(Σ[a∈N]1/aは発散するので)。ところが、
V≦Σ[ki＝0～∞ (i＝1，…，m)，(k1，k2，…，km)≠0]1/{f(k1)＋f(k2)＋…＋f(km)}
及びf(n)～α^n (α＝(1＋√5)/2)及び相加相乗平均の不等式などにより、Vは収束することが
分かり、矛盾。
余談ですが、Vが収束することから、lim[n→∞]#(Bm∩[1，n])/n＝0となることも分かります。
N全体に占めるBmの割合はゼロであって、実は かなりスカスカの集合になっている感じ。f(n)の
オーダーが指数関数だから、高々m個足したところで、Nのほんの一部しか表せない、ということかな。
290 名前：名無しさん＠そうだ選挙に行こう[sage] 投稿日：2005/09/11(日) 23:18:23
>>287
長い証明上等。読んでみたいから気合いいれて書いてちょ。
296 名前：287[sage] 投稿日：2005/09/12(月) 23:06:58
清書してみたらもっと綺麗な解答がみつかった。
再度用語の整理。x[i] (i≧1)はフィボナッチ数列。Cは有限個をのぞいて0の非負整数列の集合。
このとき次が成立。
補題 c∈Cにたいしてc’∈Cを∑c[i]x[i]=∑c’[i]x[i]、∑c’[i]≦∑c[i]、c’[i]≦1を
みたすものがとれる。
証明 Z×Zの元とみなしてここにに辞書式順序をいれる。
(u,v)=(∑c[i]^2,min{i|c[i]≧2)をZ×Zの元とみなしてこの順序に関する帰納法。
u=0ならあきらか。(u,v)<(U,V)まで成立するとして
(u,v)=(U,V)と仮定する。∀i c[i]≦1ならc’=cとすればよい。∃i c[i]≧2と仮定する。
CaseI)∃i c[i],c[i+1]>0のき。このときはiをc[i],c[i+1]>0、c[i+2]=0となるiがとれる。
d∈Cをd[i]=c[i]-1、d[i+1]=c[i+1]-1、d[i+2]=c[i+2]+1、d[j]=c[j] (j≠i,i+1,i+2)
で定める。このとき∑d[i]x[i]=∑c[i]x[i]、∑d[i]＜∑c[i]、∑d[i]^2＜∑c[i]^2
であるから帰納法の仮定より題意をみたすc’が存在する。
CaseII) CaseIでなくc[1]≧2 or c[2]≧2のとき。
このときc[1]=0 or c[2]=0である。
d∈Cをd[1]=c[1]+c[2]-1、c[1]=1、d[j]=c[j] (j≠1,2)
で定める。このとき∑d[i]x[i]=∑c[i]x[i]、∑d[i]=∑c[i]、∑d[i]^2＜∑c[i]^2
であるから帰納法の仮定より題意をみたすc’が存在する。
CaseIII) CaseI,IIでないとき。
i=min{i|c[i]≧2}とおく。このときi≧3でありc[i-1]=c[i+1]=0。
d∈Cをd[i-2]=c[i-2]+1、d[i-1]=0、d[i]=c[i]-2、d[i+1]=1
で定める。このとき∑d[i]x[i]=∑c[i]x[i]、∑d[i]=∑c[i]、∑d[i]^2≦∑c[i]^2
であり、最後の不等号の等号成立は(c[i-2]、c[i-1]、c[i]、c[i+1])=(1,0,2,0)
のときのみである。このときは(d[i-2]、d[i-1]、d[i]、d[i+1])=(2,0,0,1)。
よっていづれにせよ(∑d[i]^2,min{i|d[i]≧2)＜(∑c[i]^2,min{i|c[i]≧2)であるから
帰納法の仮定より題意をみたすc’が存在する。□
（続く）
297 名前：１３２人目の素数さん[] 投稿日：2005/09/12(月) 23:08:19
（続き）
主張 E(n)=min{∑c[i]|∑c[i]x[i]=n}、F(n)=min{∑c[i]|∑c[i]x[i]=n、c[i]≦1}で
さだめるときE(n)=F(n)。
証明 E(n)≦F(n)はあきらか。F(n)=∑c[i]、∑c[i]x[i]=nをみたすものをとるとき
c’を∑c[i]’≦∑c[i]、∑c’[i]x[i]=nをみたすものがとれるゆえF(n)≦E(n)。□
定理 {E(n)}は非有界。
証明 >>256よりF(x[n]-1)≧[(n-1)/2]なのであきらか。□
