プロが教えるわが家の防犯対策術!

漸化式は、前後の数から成り立つ数列と定義される。
なので、漸化式からなる数列{a_n}は、mod v(何かしらの数字)で
purely periodic(循環連分数)である。

と本に書かれているのですが本当でしょうか?

A 回答 (4件)

>a_n=a_(n-1) - a_(n-2) n≧2


> a_0 = 0, a_1 = 1 と漸化式をおきます。
> mod a_n としますと、
>どのように循環するのでしょうか?
このケースでは,modを取るまでもなく,
a2=1,a3=0,a4=-1,a5=-1,a6=0,a7=1,a8=1,a9=0,a10=-1,a11=-1,a12=0
となり,1,1,0,-1,-1,0,1,1,0,-1-1,0の形で周期6で循環しています。
(一般項は,a_n=2*sin(nπ/3)/√3と書けます。)

一般に,
a_n=C1*a_(n-1)-C2*a_(n-2)で漸化式を作ると,
一般項は
a_n=D1*(λ1)^n+D2*(λ2)^n,
λ1,λ2は二次方程式λ^2=C1*λ-C2の根,
D1,D2はa1,a0から決まる定数,
の形に書けます。
C1,C2を整数係数にして,初期値a1,a0に整数値を与えると
数列a_nは整数値をとりますが,
任意のvに対してmod vをとれば循環します。

有名な例ですが,フィボナッチ数列
a_n=a_(n-1) + a_(n-2)
a_0 = 1, a_1 = 1 と漸化式をおくと,
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,
121393,196418,317811,・・・
となり,発散します。
これを例えばmod 5で分類すると,
1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,4,1,0,1,1,2,3,0,・・・となり,
周期19で繰り返すことが分かります。

一般に,整数係数の多項式で漸化式を作れば,任意のvに対してmod vをとれば循環します。
    • good
    • 0
この回答へのお礼

ようやく理解出来ました。
何度もすみません!
大変助かりました。

alice_44さんもいつもありがとうございます!


ありがとうございました!!!

お礼日時:2011/10/20 21:14

mod vの演算を先にやるため0からv-1の値しか出てこないタイプの漸化式,


あるいは
mod vの値によって次項のmod vの値が確定するタイプの漸化式ならば,
alice先生がおっしゃるように,0,1,2,・・・,v-1の有限個の組み合わせしかないので循環します。

しかし,整数から整数への関数の中には,
x1≡x2 (mod v)でも,f(x1)≡f(x2) (mod v)とならない関数もあります。

例えばmod 5に対して,
f(x)=x+1+int(x/5) (int(x)はxを超えない最大の整数)
です。
単調増加する整数列をx[n+1]=f(x[n])で作って
1,2,3,4,5,7,9,11,14,17,21,26,32,39,47,57,69,・・・
これをmod 5で分類しても,循環しません。

「整数から整数を作る漸化式」「mod v(何かしらの数字)で」
という言葉の意味を取り違えていたらごめんなさい。

この回答への補足

回答ありがとうございます。

例えば、a_n=a_(n-1) - a_(n-2) n≧2
a_0 = 0, a_1 = 1 と漸化式をおきます。
mod a_n としますと、
どのように循環するのでしょうか?

補足日時:2011/10/20 13:57
    • good
    • 0

mod v だと、数が v 種類しかありませんから、


m 項間漸化式で a[n] が m-1 個の a[k] から決まるとすれば、
漸化式へ代入する値の組合せは、v^(m-1) 種類以下しかありません。
順に項を見ていって、v^(m-1) 項先までには同じパターンが
出て来ざるをえないので、数列は循環するのです。
    • good
    • 0

漸化式の条件が何かついているはずです。



二項間の漸化式だとすると,
カオス数列が出てくる漸化式,
a[n+1]=C*a[n]*(1-a[n])
だってあります。
mod vで純粋に周期的(purely periodic)にはならないです。

整数から整数をつくる漸化式に限定しているのでしょうか?

この回答への補足

整数から整数を作る漸化式に限定しています!

それだけではまだ足りないでしょうか?
回答ありがとうございます!!

補足日時:2011/10/19 16:18
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!