Generating function

できるだけ詳しく教えてください。
投稿者: 御手洗景子 投稿日: 2010 年 6 月 17 日 (木) 18 時 37 分 56 秒

(1) 1/(1-x-x^2) = Σ(n=0～∞)a_n（x^n)に対して, a_0, ..., a_10 を求め, その規則性を見つけよ。 そして, どうしてその規則性が成り立つのか説明せよ。

(2) (2-x)/(1-x-x^2) = Σ(n=0～∞)a_n（x^n) に対して, a_0, ..., a_10 を求め, その規則性を見つけよ。 そして, どうしてその規則性が成り立つのか説明せよ。

(3) (x^2)/(1-x-x^2-x^3) = Σ(n=0～∞)a_n（x^n) に対して, a_0, ..., a_10 を求め, その規則性を見つけよ。 そして, どうしてその規則性が成り立つのか説明せよ。

できるだけ、詳しく教えてください。お願いします

http://mixi.jp/show_friend.pl?id=8351698

---

解答:
(1) Fibonacci 数列で (2) は 2, 1, 3, 4, ... となる Fibonacci 数列の類似。 (3) は Tribonacci を二項ずらしたもの。

(1) の理由は部分分数分解したのと, Fibonacci の一般項 (Binet の公式) を見比べれば分かる。

こっちを見るともっと良く分かる。

(2) は 2 - x を掛けた結果, 新しい a_n が (1) のもので 2a_n - a_(n-1) で表されるから。

(3) で二項ずらしたものであることは x^2 を掛けたものだから直ぐに分かるが, Tribonacci は (1) での母関数の作り方を参照にすること。

数列

数列 2009/10/22 (Thu) 23:48:04 No.10255
※数列です。
a₁ = 3, a_n+1 + a_n = 4n (n = 1, 2, 3, ...) を満たす数列 {a_n} について,
a_n+2 - a_n = (a_2n+1) - (a_2n-1) の値が 4 になるのですが・・何故でしょうか？？；；
あと, a_2n-1 = 4n - 1 となるのですが, 解き方が分かりません・・漸化式っぽいということは分かるのですが、教科書、問題集に類題もなく手がつけられません；；どなたかおしえてください！(-人-)
kitty
証明

---

(七 氏による方法)
a_n+1 + a_n = 4n だから
a_n+2 + a_n+1 = 4(n + 1) でもある。
下から上を引くと
a_n+2 - a_n = 4.
ここで n = 2m - 1 とすれば a_2m+1 - a_2m-1 = 4 を得る。

後半は簡単である。
a_2n+1 - a_2n-1 = 4
が示されているので, それは b_n = a_2n-1 と置くと, この b_n が公差 4 の等差数列であることを示しているので
a_2n-1 = b_n = b₁ + 4(n - 1)
= a₁ + 4n - 4
= 3 + 4n - 4 = 4n - 1.

---

次に漸化式を解いてしまう証明を示す。
ここに従って
a_n+1 + α(n + 1) + β = -(a_n + αn + β)
と置く。 元に戻すと
a_n+1 + a_n = -2αn - (α + 2β)
だが, 元の式と比較すると α = -2, β = 1.
従って
a_n+1 - 2(n + 1) + 1 = -(a_n - 2n + 1).
従って
a_n - 2n + 1 = (-1)^n-1(a₁ - 2 + 1)
　　　　　　　　　　= (-1)^n-1(3 - 2 + 1)
　　　　　　　　　　= 2・(-1)^n-1
∴a_n = 2・(-1)^n-1 + 2n - 1.

さてここで
a_n+2 - a_n
= 2・(-1)ⁿ⁺¹ + 2(n + 2) – 1 - 2・(-1)^n-1 - 2n + 1
= 4.
a_2n+1 - a_2n-1 = 4 の方も同様。
又
a_2n-1
= 2・(-1)^2n-2 + 2(2n - 1) - 1
= 4n - 1.

---

最初の 七 氏の方法は大変 clever.
最初数学的帰納法で示すことを考えたので, その方法も記しておく。
最初に
a_n+1 + a_n = 4n
より
a_n+1 = -a_n + 4n … (a)
であることに注意しておく。
先ず (a) を用いて
a₂ = -a₁ + 4 = -3 + 4 = 1,
a₃ = -a₂ + 8 = -1 + 8 = 7.
従って a₃ - a₁ = 4 で正しい。
[追加:
a₄ = -a₃ + 12 = 5.
従って a₄ - a₂ = 4 で正しい。
]
次に
a_n+3 - a_n+1
= (-a_n+2 + 4(n + 2)) - (-a_n + 4n)
= -a_n+2 + 4n + 8 + a_n - 4n
= -(a_n+2 - a_n) + 8
= -4 + 8 (帰納法の仮定)
= 4.
a_2n+1 - a_2n-1 = 4 の方も同様。
最後のものも,
a₁ = 3 = 4・1 - 1 なので正しい。
a_2n+1 = -a_2n + 4・2n (式 (a) から)
= -(-a_2n-1 + 4(2n - 1)) + 8n
= a_2n-1 + 4
= 4n - 1 + 4 (帰納法の仮定)
= 4(n + 1) - 1.

整除

質問者: hirono320 無理数の計算
{(3 + √5)^n｝ + ｛(3 - √5)^n｝ (n = 1, 2, 3, ...) は整数になりますが, いつでも 2^n でわりきれます。 このことを証明できるでしょうか? 整数になることは m√5 の項がすべて 0 になることでわかるのですが, なぜ 2^n で割り切れるのかわかりませんでした。 よい方法をご教授ください。
質問投稿日時: 09/10/22 13:16 質問番号: 5387283
証明

---

証明
類題
a_n = (3 + √5)ⁿ + (3 - √5)ⁿ, n = 1, 2, 3, ... と置く。
a₁ = 6, a₂ = 28.
一方, この数列は
a_{n + 2} - 6a_{n + 1} + 4a_n = 0 … (a)
を満たす。
[∵ 左辺 = (3 + √5)ⁿ⁺² + (3 - √5)ⁿ⁺² - 6・(3 + √5)ⁿ⁺¹ - 6・(3 - √5)ⁿ⁺¹ + 14・(3 + √5)ⁿ + 4・(3 - √5)ⁿ
= (3 + √5)ⁿ・((14 + 6√5) - 6・(3 + √5) + 4) + (3 - √5)ⁿ・((14 - 6√5) - 6・(3 - √5) + 14) = 0]

以下, 数学的帰納法 (mathematical induction)。
先ず, n = 1 の時は a₁ = 6 は 2 で割り切れ,
n = 2 の時も a₂ = 28 は 4 = 2² で割り切れる。
又, [数学的帰納法の仮定 induction hypothesis] k < n の時に, a<sub>k = 2^kM_k, M_k ∈ N と置くことが出来ると仮定する。
[Induction step] n > 3 の時 (a) と数学的帰納法の仮定により,
a_n
= 6a_{n - 1} - 4a_{n - 2}
= 6・2^{n - 1}M_{n - 1} - 4・2^{n - 2}M_{n - 2}
= 3・2ⁿM_{n - 1} - 2ⁿM_{n - 2}
= 2ⁿ・(3M_{n - 1} - M_{n - 2}).
従って, 2ⁿ|a_n.

---

最近, この手の問題が流行りなのか?
基本的に回答 No. 1 by Tacosan on 14:15 (JST) at 09/10/22の hint と同じである。
この回答は一寸間違っていて α = 3 + √5, β = 3 - √5 と置かねばならない。
2 で割っているのは誤り。
そうすると α + β = 6, αβ = 4 となって, これが, 上の証明の漸化式の根拠である。

---

追記 on Friday, 23rd October, 2009.
直ぐ上の 「2 で割っているのは誤り」 というのは僕の誤り。
上記の M_k が類題で言っている A_k であり, この M_k 乃至 A_k が整数なのだから, その 2^k 倍である, 上記の a_k は 2^k で割り切れねばならないという論法なのだった。

剰余

初めまして NEW / かえる
大学生です。
家庭教師のアルバイトで教えている高３生徒からの質問が分からず, 助けて頂きたいです。

α = (3 + √5)/2 とする。 数列 {An} を,
　　An = α^n + 1/α^n (n = 1, 2, 3, ...)
と定める。
(1) A1, A2, を求めよ。
(2) An+2 = 3An+1 - An (n = 1, 2, 3, ...)
(3) α^n (n = 1, 2, 3, ...) にもっとも近い整数を 4 で割った余りを求めよ

という問題で, (1) (2) は何とか解けたのですが, (3) が分かりませんでした。
誘導問題だと思いますが, 乗れず。
よろしくお願いします(*_ _)

No.8472 - 2009/10/18 (Sun) 21:25:37

---

解答
以下, 面倒なので, 数列は {a_n} と小文字表記する。
1/α = (3 - √5)/2 である。
(1) a₁ = (3 + √5)/2 + (3 - √5)/2 = 3.
a₂ = (7 + 3√5)/2 + (7 - 3√5)/2 = 7.

(2) 右辺 = 3(αⁿ⁺¹ + 1/αⁿ⁺¹) - (αⁿ + 1/αⁿ)
= (3α - 1)αⁿ + (3/α - 1)/αⁿ
= ((7 + 3√5)/2)αⁿ + ((7 - 3√5)/2)/αⁿ = 左辺。

(3) (2) により
a_n+2 = 3a_n+1 - a_n
≡ -(a_n+1 + a_n) (mod 4)
で,
{a_n (mod 4)} = {3, 3, 2, 3, 3, 2, 3, 3, 2, ...}
一方, 2 < √5 < 3 なので, 0 < 1/α = (3 - √5)/2 < 1/2. だから, α<sup>n に最も近い整数は a_n であるので,
n が 3 の倍数の時 2, それ以外は 3.

---

三項間漸化式としては普通の問題だが, (3) が珍しくて面白い。

確率の漸化式

確率の漸化式 2009/10/18 (Sun) 19:49:42 No. 15911
a[n] - 1 = p*a[n+1] + q*[n-1] (sic)
a[0] = a[N] = 0
n = 1, 2, 3, ..., N - 1
p + q = 1, p > 0 , q > 0
であるとき, a[n] を求めたいのですが, 連続四項間漸化式に変形してみたのですが, うまくいきませんでした。
どなたか解法をご教えください。
よろしくお願いします。
nixon

---

解答
ここに従って
(p + q)a_n - 1 = pa_n+1 + qa_n-1
p(an+1 - a_n) = q(a_n - a_n-1) - 1 … (a)
pa_n+1 - qa_n = pa_n - qa_n-1) - 1 … (b)
b_n = a_n+1 - a_n, n = 0, 1, 2, ... と置く。
すると b₀ = a₁ - a₀ である。

(1) p = q = 1/2 の時。
(a) より b_n = b_n-1 - 2 (A.P. 等差数列)
[ここで b₁ = b₀ - 2,
b₂ = b₀ - 4,
b₃ = b₀ - 6,
......
に注意して]
b_n = b₀ - 2n.
故に a_n+1 - a_n = a₁ - a₀ - 2n. (階差数列)
ここで n ≧ 1 の時
a_n = a₀ + Σ_{k = 0}^{n – 1} (a₁ - a₀ - 2k)
= a₀ + (a₁ - a₀)n - 2・(1/2)n(n - 1)
= a₀ + (a₁ - a₀)n - n(n - 1)
= a₁n - n(n - 1).
(この式は n = 0 の場合を含んでいる。)
さて, n = N の時
a_N = a₁N - N(N - 1) = N(a₁ - (N - 1)) = 0.
従って, a₁ = N - 1.
よって
a_n = (N - 1) - n(n - 1) = n(N - 1 - n + 1) = n(N - n).

(2) p ≠ q の時。
(a) より pb_n = qb_n-1 - 1
p(b_n + 1/(p - q)) = q(b_n-1 + 1/(p - q))
b_n + 1/(p - q) = (q/p)(b_n-1 + 1/(p - q)) (G.P. 等比数列)
b_n + 1/(p - q) = (q/p)ⁿ(b₀ + 1/(p - q))
an+1 - a_n = (q/p)ⁿ(a1 - a₀ + 1/(p - q)) - 1/(p - q) … (c)
さて一方 c_n = pa_n+1 - qa_n, n = 0, 1, 2, ... と置く。
すると c₀ = pa₁ - qa₀ であって, (b) より
c_n = c_n-1 - 1 (A.P.)
c_n = c₀ - n
pa_n+1 - qa_n = pa₁ - qa₀ - n … (d)
ここで p(c) - (d) を計算すると
-(p - q)a_n = p(q/p)ⁿ(a₁ - a₀ + 1/(p - q)) - p/(p - q) - pa₁ + qa₀ + n
従って
a_n = (-1/(p - q))(p(q/p)ⁿ(a₁ - a₀ + 1/(p - q)) - p/(p - q) - pa₁ + qa₀ + n) … (e).
ここで n = N とすると
a_N = (-1/(p - q))(p(q/p)^N(a₁ - a₀ + 1/(p - q)) - p/(p - q) - pa₁ + qa₀ + N) = 0
であるから
p((q/p)^N - 1)a₁ = p(q/p)^N(a₀ - 1/(p - q)) + p/(p - q) - qa₀ - N)
これから a₁ について解いて (e) に代入すればいいのだが, 式が簡単になりそうにないので, ここまでにしておく。

---

因みに p + q = 1, p > 0 , q > 0 という辺りが確率っぽいが, 別に確率と関係ないとして解ける。