- ベストアンサー
漸化式は、modで循環していますか?
FT56F001の回答
>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をとれば循環します。
関連するQ&A
- 漸化式の問題
先日苦手な漸化式の問題が出され解いてみたのですがどうしてもうまくいきませんでした。どうしても解いてみたいので、回答と解き方を教えてください。 (問)漸化式(*) x_n+2=2x_n+1-2x_n=0 (n=1,2,…)をみたす数列 (x_n)_n=1,2,…全体のなすベクトル空間をVとする。 (1)Vの一組の基底及び次元を求めよ。 (2)α=1+i,β=1-i (i^2=-1)と置くとき、漸化式 (ⅰ) x_n+1=αx_n, (ⅱ) x_n+1=βx_n (n=1,2,…) をみたす数列(x_n)_n=1,2,…全体のなす集合をそれぞれW_1,W_2とする と、これらは共にVの部分空間であることを示せ。 (3)漸化式(ⅰ),(ⅱ)をみたす例でない数列をそれぞれw_1,w_2とするとき、 Λ={w_1,w_2}はVの基底になることを示せ。 (4)Λに関する数列(1,1,…)∈Vの座標を求めよ。 以上です。 こんな簡単な問題も分からないのと思わず優しく教えてください。 お願いします。
- ベストアンサー
- 数学・算数
- 数列 漸化式
A(n+1)=2A(n)+n (初項A(1)=1) という数列があるとします。 この一般項の形を求めるのに、この漸化式を満たす数列{B(n)}=αn+βを設定して、 この漸化式に代入、恒等式から{B(n)=-n-1}がわかります。 この{B(n)}の式が最初の漸化式を満たすわけですから、 A(n+1)=2A(n)+n B(n+1)=2B(n)+nの両辺を引いて A(n+1)-B(n+1)=2(A(n)-B(n))という等比数列が成り立つので、 A(n)=3*(2のn-1乗)-n-1 となると思うのですが、 ここから質問です。 なぜ最初の漸化式を満たした、B(n)=-n-1 と これまた漸化式を満たしている、A(n)=3*(2のn-1乗)-n-1 が異なっているのでしょうか? 回答お願いいたします。
- ベストアンサー
- 数学・算数
- 【数学基礎】漸化式と再帰的定義
漸化式とよばれる式と、再帰的定義とよばれる式の区別ができません。 例えば(ご説明で他の適した例があれば、ご紹介ください)、 フィボナッチ数列でいえば、 F(n)=F(n-1)+F(n-2) (2≦nの場合),F(0)=0 であったり、 階乗であれば、 n!=n×(n-1)! n (n=1,2,3,...の場合) n!=1(n=0の場合) といった式の説明に対して 「これは漸化式である」であったり「これは再帰的定義である」という 記述を散見します。 私のイメージとしては、 ・漸化式は一般式を求める前段階の式 ・再帰的定義は左辺を右辺で定義している式 です(上記認識が誤りであれば、ご指摘くださいませ)。 私が混乱しているのは、 一つの式を「漸化式である」であったり「再帰的定義である」と 表現してみたりする判断基準がわかりません。 「なんとなく」文脈で使い分けているようにも思えるのですが、 曖昧なまま学習を進めることに不安を感じており、質問させて いただきました。 漸化式と再帰的定義についての違いについて教えて下さいませ。 よろしくお願いします。
- ベストアンサー
- 数学・算数
お礼
ようやく理解出来ました。 何度もすみません! 大変助かりました。 alice_44さんもいつもありがとうございます! ありがとうございました!!!