ふとした拍子で、次のような漸化式が出てきてしまいました。

ことの発端はこの問題です。
「n枚の硬貨を1列に並べるとき、表が3枚以上続かない場合の数を求めよ。」

n=1のとき 2通り

n=2のとき 4通り

n=3のとき 7通り(○○○を除く)

n=4のとき
1回目が×だと残りの樹形図はn=3と同じ。
○×××
││└○
│└○×
│ └○
└○××
  └○ さらにこの樹形図が加わるので、全部で13通り

これを眺めていると、
○×で始まるときは残りはn=2のときと同じなので4通り
○○×で始まるときは残りはn=1のときと同じなので2通り。
つまり、4番目は、以前の3つの和であることが推測されます。

これを踏まえたうえでn=5を考えると、
1枚目が×のときは残りの樹形図はn=4のときと同じはず。
○×となったときは残りの樹形図はn=3のときと同じはず。
○○×となったときは残りの樹形図はn=2のときと同じはず。
ですよね。

Q1 まず、この推測が正しいかどうかがわかりません。

正しいと仮定して続けさせていただきます。
n枚の硬貨を並べるとき、表が3枚以上続かない場合の数をA(n)とすると、
A(n+3)=A(n+2)+A(n+1)+A(n) という4項間漸化式が出てきてしまいます。

Q2 3つだったらフィボナッチなのですが、これは何か名前があるのでしょうか?もう、誰かが解いていますか?
一応途中まで頑張っているのですが字数の関係で表現できません。よろしくお願いします。

A 回答 (3件)

綺麗な漸化式ができましたねえ。

2連続と考えればフィボナッチ数列の解釈になる。一般にj連続と考えることで一群の漸化式が出てくる。これだけで素敵な成果じゃないですか。
 数列の一般項を求めても、それが難しい関数や総和を含んでいるようでは、漸化式で計算したほうがましだったりしないとも限りません。
 余談ながら比 x=A(N)/A(N-1)がN→∞において収束するとすれば、
x^3-x^2-x-1=0
という方程式の実数解ですから、
 x=(19/27-√(11/27))^(1/3)+(19/27+√(11/27))^(1/3)-1/3
なんてことになります。

 では、ちょいと観点を変えてみましょう。
A:「裏ばかりの硬貨が一列に並んでいる。その個数(は幾つでも良いがこれ)をMとする。その隙間、あるいは列の先頭や末尾に、適当に表の硬貨を挿入して行く。ただし、各挿入箇所に挿入する表の硬貨の数は0か1か2でなくてはならない。表の硬貨を挿入できる箇所はM+1箇所ある。挿入した表の硬貨の総数をKとすると、N=M+Kが列全体の長さである。Nを固定したとき、場合の数A(N)を求めよ。」これは元もとの問題を別の言い方で表してます。
 Nを固定して考えると、0≦K≦2(M+1)ですから、
(1) 0≦K≦(2N+2)/3
でなくてはなりません。
 さて、NとKが与えられたとします。するとK個の表の硬貨をいかにしてM+1個の挿入箇所に配分するかという問題です。すなわち
B(N,K):「K個の(表の)硬貨をM+1=N-K+1人で分ける。ただし一人最大2個しか貰えない。場合の数を求めよ」
を考えることができる。その解B(N,K)をK=0,1,....,floor[(2N+2)/3] について加えたものがA(N)になります。
A(N) = B(N,0)+ B(N,1) + ...... + B(N,floor[(2N+2)/3] )
この問題B(N,K)は、さらに次の問題に帰着できます。
C(N,K,h):「N-K+1人の中から、硬貨2つを貰えるヒトh人を選ぶ。残りのN-K+1-h人の中から硬貨1つを貰えるヒト(K-2h)人を選ぶ。場合の数を求めよ。ただし2h≦Kである。」
すなわち
B(N,K) = C(N,K,0)+C(N,K,1)+.....+C(N,K,floor[K/2])
ですね。

ここで、問題c(n,j):「n人のうちからj人を選ぶ場合の数を求めよ」
を考えますと、ご承知の通り、
・j>nの場合にはc(n,j)=0
・0≦j≦nの場合にはc(n,j)= n! / (n-j)!/j!
ということになる。だから
C(N,K,h) = c(N-K+1,h)c(N-K+1-h,(K-2h))
である。
かくて、二重の総和を使って無理矢理ながら元の問題の解が表せることまでは分かりました。それが具体的に綺麗な式に整理できるかどうかがポイントですが.....
これで、おしまい。無責任だなあ。
    • good
    • 0
この回答へのお礼

ありがとうございます。なんとなくですが、見えてきました。

確率として考えれば、ご教授いただいたものに収束しそうですね。

ちなみにですが、元の漸化式を途中まで解いてみたところ、

A(n+2)+xA(n+1)+(1+x-xx)A(n) は公比1-xの等比数列です。
xは、xxx+2xx-2=0 の解で、うち実数であるものは-1<x<-3/4
なので、どうやら発散しそうです。

でも、なんだか見えてきました。残りは何とか頑張ります。ありがとうございました。

お礼日時:2001/06/04 10:31

ごめんなさい私が理解していないようでした。


masuo_kunさんがご指摘のように
> ですが、○×だけではなく、××も加えないといけないですよね。
に関して、私の理解がまちがっていたようで、
その1つ前の樹形図に含まれるのですね。

私の計算の漸化式から(両辺に2^nを掛けて)
 a(n)=2*a(n-1)-a(n-4)
つまり、
 a(n)-a(n-1)=a(n-1)-a(n-4)
となり確かにmasuo_kunさんのものと一致しますね
(チェックしていませんでした。ごめんなさい)。
(p=1/2の場合のkが一般の場合は、
 a(n)=2*a(n-1)-a(n-k-1)
 a(n)-a(n-1) =a(n-1)-a(n-k-1)
 でこれもmasuo_kunさんのものに一致しますね。
)。
これの一般項は求められるかというのが問題意識なのでしょうか?
う~ん。難しいですね。考えてみます。

式の中の符号もひとつ間違っていました。
P(n,k)=P(n-1,k)+(1-P(n-k-1,k))*(1-p)*p^k
でした。

以上、とりあえずお詫びでした。
    • good
    • 0
この回答へのお礼

こんな難問のためにお時間頂いてしまって恐縮です。
本当にお手数おかけいたします。・・・

Q1については、一致したようで、私の考えに誤りはないことが確認できました。
ありがとうございます。

この漸化式、もしかしたら角の3等分線をコンパスと定規で作るのと同じような、
解けないものの一種ではないかとも思い始めているので、
「解けない」ということならそれでも構わないのです。
これを「4連続」と差し替えると、
A(n+5)=A(n+4)+A(n+3)+A(n+2)+A(n+1)+A(n)
という5項間漸化式になるらしいので、
始まるときりがないんですよ。この話・・・

お礼日時:2001/06/03 14:42

Q1について、一般的漸化式を示します。


n個並べたときに、1回あたりの出現確率が p の「あるもの」が
k個以上連続している確率 P(n,k)をもとめます。
n-1個並べたときに「あるもの」が k 個以上連続している場合と、
そうでない場合いに n 個目に「あるもの」を1つ付け加えて初めて
k 個連続したものができる場合の和で表されると思います。
前者は
(0) n 個目につけ加えるものはなんでもいいので P(n-k,k-1)、
後者は
(1) 最初の n-k-1 個には n 個以上連続したものがなく(1-P(n-k-1,k))、かつ
(2) n-k個目は「あるもの」ではなく(1-p)、かつ
(3) 残りの k 個はすべて「あるもの」(p^k)
となるので、
 P(n,k)=P(n-1,k)-(1-P(n-k-1,k))*(1-p)*p^k (但し、n>k+1)。
結局、求めるk個以上続かない確率Q(n,k)はQ(n,k)=1-P(n,k)として
 Q(n,k)=Q(n-1,k)-Q(n-k-1,k)*(1-p)*p^k (但し、n>k+1)
となるのではないでしょうか?
したがって、これに全体の場合の数をかければ
求める場合の数が得られるはずです。(いまの場合、p=1/2, k=3)

> これを踏まえたうえでn=5を考えると、
> 1枚目が×のときは残りの樹形図はn=4のときと同じはず。
> ○×となったときは残りの樹形図はn=3のときと同じはず。
>         :
ですが、○×だけではなく、××も加えないといけないですよね。
そして、どんどんnが大きくなったとき、たとえばn=6
○○○???
のような場合ははずさないといけないですよね。
というわけで、ちょっとややこしい漸化式になってしまうと思います。
    • good
    • 0
この回答へのお礼

ご丁寧な回答、ありがとうございます。

Q(n,k)=Q(n-1,k)-Q(n-k-1,k)*(1-p)*p^k

これも考えました!でも、結局k=3で具体的に解くとなると、
A(n)=A(n-1)-A(n-3)*(1-p)*p^3 となるのですよね。
nをずらすと、
A(n+3)=A(n+2)-A(n)*(1-p)*p^3
結局4項間漸化式のような気がします・・・
この形を強引に解くでも良いのですが。。。。

あと、一番最後のことですが、きっと私の表現が悪かったのだと思います。
「○×となったとき」というのは、「○×で始まる場合」
「○○×となったとき」というのは、「○○×で始まる場合」
という意味でした。表現に誤解を招く部分があり申し訳ありません。
樹形図を実際に書いてみると、私の意図は伝わると思います。
この方法なら○○○で始まる場合はもちろん条件を満たさないので数えていません。

なお、私の方法では、3枚ではなくk枚のときは、
a(n)=2^n (1≦n≦k-1)
a(k)=2^k-1 という初期条件で、n≧1+kのときは
a(n)=S(n-1)-S(n-k-1) ただし、S(n)は初項から第n項までの和で、S(0)=0
という漸化式に従いそうなんです。
ここまでは分かっているのですが、字数上限に阻まれてしまいました(笑)

そもそも、この問題,漸化式を解くことには意味がないのでしょうか・・・
Q1は分からないけどQ2は知っているという方のご意見もお待ちしています。
(このままやると変な3次方程式が出てきて、計算が爆発します)

お礼日時:2001/06/03 10:01

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

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q多項間漸化式

数学の授業で3項間漸化式をやったとき
ふと4項間漸化式の一般項が知りたくなりました。
しかしいろいろ試しましたが分かりません。
質問No.84673の「4項間漸化式」も見させていただきましたが、
結局、漸化式の問題ではないという感じで終わっていてよく分かりません。

たとえば3項間ならば特性方程式と二次方程式の解の公式から
a(n+2)-(α+β)*a(n+1)+αβ*a(n)=0 となるα,βを求め(α≠β)
(

Aベストアンサー

>ところで、guiterさんの出してくださった
>a(n) = [a(2)sin{(n-1)θ} - r*a(1)sin{(n-2)θ}] * r^(n-2) / sinθ は
>a(n)が整数であることの証明になるのでしょうか。
少し言葉足らずでした。
式変形に困っておられるのだと思い、
極形式での結果を書いただけですので、これだけで整数とは言えません。
少し考えてみましたが一般項から直接証明というのは難しそうですね。

やはり、masuo_kun さんも書かれておられるように
 (1) n=1,2 で成り立つ。
 (2) n=k,k+1 で成り立つとき n=k+2 で成り立つ。
というように素直に帰納法で証明するのが良さそうです。

Qa[1]=3,4a[n+1]=12a[n]-2×{3^(n-1)}×n

a[1]=3,4a[n+1]=12a[n]-2×{3^(n-1)}×n+3^(n-1)
で、
Σa[k](k=1~n)を最大にするnの最小を求めよ。

まず、一般項a[n]=-3^(n-2){n^2-2n-3)/4 を求めました。
このあとΣの値を求められません。
よろしくお願いします。

Aベストアンサー

a[n] が正だったら,足せば合計は大きくなります.
a[n] の符号変化を見て,負になる前まで足せば,
そこが合計が最大になる場所の候補です.

Q大学入試 数学「解けない漸化式の極限」について

 いつも大変お世話になっております。
 以下の内容についてアドバイスいただけると助かります。
 大学の入試問題で「解けない漸化式の極限」などのテーマで参考書や問題集にある問題についてなのですが、私が確認したいのは、ある漸化式を見たときに、それが「解けないのだ」と判断する基準です。確かに、問題の流れ(誘導形式になっている)から、これは解けない漸化式のパターンだなと判断することもできますし、また、自分の知っている「解ける漸化式の型」になければ、それは解けないのではと考えることもできると思いますが、漸化式そのものの特徴から、これは解けないと疑う基準があれば教えていただけないでしょうか。
 お忙しいところ大変もうしわけございませんがよろしくお願いします。

Aベストアンサー

参考書や問題集にある「解けない漸化式の極限」の解法パターンを使うにあたって、
その漸化式が本当に「解けない」かどうかを突き詰めて考える必要は全くありません。
解がよく知られた簡単な式になる以外の漸化式には、その技法が使えるかも知れない
…と考えてみればよいと思います。たとえ解が解析的に表示できたとしても、それが
相当複雑な式であれば、極限を求めるときに又ひと仕事ですよね? そこを迂回して、
一般項の表示をしないまま極限を求める解法があれば、役に立つ場合はある訳です。
解いてみたほうが簡単かどうかは、慣れからくる現場の勘で判断するしかないでしょう。

Q数列{a_n}、{b_n}が、a_n=s^n, b_n=r^n(n=1

数列{a_n}、{b_n}が、a_n=s^n, b_n=r^n(n=1,2,3,,) 0<s<r<1 で与えられている時、
Σ∞_(n=1) a_(n)b_(n) = 1/3 , Σ∞_(n=1) a_(n)/b_(n) = 3
を満たすとする。この時、s+rの値を求めよ

Aベストアンサー

  a[n] = s^n
  b[n] = r^n
より、
  a[n]*b[n] = (s*r)^n
  a[n]/b[n] = (s/r)^n
もまた等比数列となる。

等比数列の和の極限は公式により求められるから、
  Σ[n=1~∞]{a[n]*b[n]} = 1/3
より
  s*r = 1/2
が分かり、
同様に
  Σ[n=1~∞]{a[n]/b[n]} = 3
より
  s/r = 3/4
が分かる。

二つの未知数s,rに対して、二式
  s*r = 1/2
  s/r = 3/4
が得られたから、あとはs<rという条件を加え、連立方程式を解くことでs,rの値が求まる。

Q漸化式

漸化式てそもそもどう言う意味なんでしょうか?問題とかは普通に解けるのですが、漸化式の意味そのものが、いまだによく分かりません。

Aベストアンサー

漸というのは辞書によると「物事が徐々に進むこと」とあります。
数列は各項が徐々に変化するが、どのように変化するのかを示すのが漸化式ということだと思います。項比がマイナスの等比数列などは徐々に変化とは言い難いかも知れませんけど。

参考URL:http://dictionary.goo.ne.jp/search.php?MT=%C1%B2&kind=jn&mode=0&type=stick

Qベクトルの発展問題です。不等式│2a→+3b→│≦2│a→│+3│b→

ベクトルの発展問題です。不等式│2a→+3b→│≦2│a→│+3│b→│を証明せよ。

この問題について、ヒントまたは解説をお願いします><

Aベストアンサー

以下を頭に入れておくこと。
「x,yをn次ベクトルすると
       |x+y|≦|x|+|y|         が成立する。」

これが理解できているならx=2a→,y=3b→
をつっこんでおしまい。

Q受検戦略 慶應薬学部 漸化式

漸化式の問題にどう対応しようか迷っています

第一志望は慶應薬学部
1 全体的な傾向としては 大問4~5 計算量多め 難問少な目 
2 漸化式は頻出 公式そのままで解ける問題以外にも
  確率と絡めた問題など高度な部分まで出題されています


取り得る戦略として
1 漸化式 → 一般項 の受検で問われやすいパターン全て暗記
2 漸化式 → 一般項 の基本的なパターンだけ暗記し、あとは導出できるようにする
3 漸化式 → 一般項 の受検で問われやすいパターンをすべて導出できるようにする

※導出法としてはhttp://www.geisya.or.jp/~mwm48961/koukou/sazen01.htm
にある「定型問題は等比数列に持ち込む」「非定型問題は推定+数学的帰納法」でいこうと
考えています

があると思うのですが、どれを採用するべきですかね?
自分はいままで数学は極力暗記に頼らない方法をとってきましたし
慶應薬学部は応用的な漸化式の問題も出てきますので3でいきたいような気もするのですが
漸化式は暗記に頼る方法を採用する人も多く迷っています

どうするべきでしょうか?
ご意見よろしくお願いします
(ご自身が、受検時に合格された大学も書いていただけると非常に参考になります
 できればあわせてお書きください)

漸化式の問題にどう対応しようか迷っています

第一志望は慶應薬学部
1 全体的な傾向としては 大問4~5 計算量多め 難問少な目 
2 漸化式は頻出 公式そのままで解ける問題以外にも
  確率と絡めた問題など高度な部分まで出題されています


取り得る戦略として
1 漸化式 → 一般項 の受検で問われやすいパターン全て暗記
2 漸化式 → 一般項 の基本的なパターンだけ暗記し、あとは導出できるようにする
3 漸化式 → 一般項 の受検で問われやすいパターンをすべて導出できるようにする

※導出法...続きを読む

Aベストアンサー

・どの本でも準公式としては扱ってない
・導出するにせよ、1分くらいでできる。
漸化式によっては2分くらいかかるかも。
・そもそも正確に覚えていられない
・数列のその「特定の形の漸化式の一般項を求める問題」に
入試で出くわす確率が非常に低い

こんなことあたりが理由で、
覚える人はほとんどいないと思います。

ただ、容易に覚えられて
しかも忘れずに正確に記憶していられる自信があるなら、
覚えてもいいんじゃないでしょうか。

QΣ[n=1..∞]a_n (a_n>0)は収束する。Σ[n=1..∞]a_n/n^pが収束するようにpの全ての値を求めよ

[問]Σ[n=1..∞]a_n (a_n>0)は収束する。Σ[n=1..∞]a_n/n^pが収束するようにpの全ての値を求めよ。
[解]
(i) p>0の時,
1/1^p≧1/2^p≧…≧0且つlim[n→∞]1/n^p=0
よって定理「Σ[n=1..∞]a_n∈Rで{b_k}は単調且つlim[n→∞]b_n=0⇒Σ[n=1..∞]a_kb_kも収束」より
Σ[n=1..∞]a_n/n^p∈R
(ii) p=1の時
Σ[n=1..∞]a_n/n^p=Σ[n=1..∞]a_nで収束(∵仮定)
(iii) p<0の時
が分かりません。
どのようにして判定すればいいのでしょうか?

Aベストアンサー

簡単な判定方法はありません。
Σ[n=1..∞]a_n/n^p
のタイプの級数をディリクレ級数といいます。冪級数の収束半径のようなものがあり、pの実部がσより大きいと収束し、pの実部がσより小さいと発散するような実数σが存在します。pの実部がσのときは収束することもあれば発散することもあります。
この問題の場合σが負または0であること以上のことはわかりません。a_nによってσは異ります。

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

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

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

Aベストアンサー

>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をとれば循環します。

>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から決ま...続きを読む

Qx^n+y^n=1以外でn=2のとき円を表す関数の種類

x^n+y^n=1 以外にも(x+y)^n+(x-y)^n=1や (x+y)^n+(y-x)^n=1はnが2のときに円を表しますが、それ以外の数ではグラフの形が違うようです(回転している?)。このようにnが2のときに円を表す関数というのは他にも無数に作れるのでしょうか。

Aベストアンサー

> x-yと y-xを入れ替えると回転の角度が変わるようですが,
> これは同じ系列というべきですか。
時計回りに π/4 回転するか,反時計回りに π/4 回転するかの違いです.


> 私は2乗以外の場合に違った図形になれば
> 違った系列にならないのかなと思ったのですが・・・
一般の n で
 (x+y)^n+(y-x)^n=1
という図形は
 x^n + y^n = 1
を π/4 回転,2^{n/2} 倍拡大したものになっています.
円の場合対称性から数式が一致するだけです.

それらを別の系列と考えるかどうかというのは
2次方程式の重解をどうとらえるか同じようなものだと思います.


人気Q&Aランキング