- ベストアンサー
漸化式は、modで循環していますか?
FT56F001の回答
- FT56F001
- ベストアンサー率59% (355/599)
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(何かしらの数字)で」 という言葉の意味を取り違えていたらごめんなさい。
関連する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の場合) といった式の説明に対して 「これは漸化式である」であったり「これは再帰的定義である」という 記述を散見します。 私のイメージとしては、 ・漸化式は一般式を求める前段階の式 ・再帰的定義は左辺を右辺で定義している式 です(上記認識が誤りであれば、ご指摘くださいませ)。 私が混乱しているのは、 一つの式を「漸化式である」であったり「再帰的定義である」と 表現してみたりする判断基準がわかりません。 「なんとなく」文脈で使い分けているようにも思えるのですが、 曖昧なまま学習を進めることに不安を感じており、質問させて いただきました。 漸化式と再帰的定義についての違いについて教えて下さいませ。 よろしくお願いします。
- ベストアンサー
- 数学・算数
補足
回答ありがとうございます。 例えば、a_n=a_(n-1) - a_(n-2) n≧2 a_0 = 0, a_1 = 1 と漸化式をおきます。 mod a_n としますと、 どのように循環するのでしょうか?