漸化式は、modで循環していますか？

質問

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

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

回答No.4

FT56F001 · ベストアンサー

>a_n=a_(n-1) - a_(n-2) n≧２
> 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をとれば循環します。

お礼

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

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

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

回答No.3

FT56F001

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≧２
a_0 = 0, a_1 = 1 と漸化式をおきます。
mod a_n としますと、
どのように循環するのでしょうか？

回答No.2

alice_44

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

回答No.1

FT56F001

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

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

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

補足

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

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