kadai78

平成２１年７月５日

[流れ星]

　　　　　第２２６回数学的な応募問題解答

　　　　　　＜解答募集期間：６月１４日～７月５日

［ある漸化式］

皆さん、先日大学入試問題を眺めていたら、上智大学の過去問から次のような漸化式を見つけました。チャレンジください。

ＮＯ１「uchinyan」 6/14 14時12分受信更新7/5

第２２６回数学的な応募問題
［ある漸化式］

取り敢えず，順番にやってみます。
以下では，n >= 3 として，
T(n) = Σ[k=2,n-1]T(k)T(n-k+1) = T(2)T(n-1) + T(3)T(n-2) + ... + T(n-2)T(3) + T(n-1)T(2)
T(2) = 1
などと書くことにします。

(1)
T(3) = T(2)T(2) = 1 * 1 = 1
T(4) = T(2)T(3) + T(3)T(2) = 1 * 1 + 1 * 1 = 1 + 1 = 2
T(5) = T(2)T(4) + T(3)T(3) + T(4)T(2) = 1 * 2 + 1 * 1 + 2 * 1 = 2 + 1 + 2 = 5
T(6) = T(2)T(5) + T(3)T(4) + T(4)T(3) + T(5)T(2) = 1 * 5 + 1 * 2 + 2 * 1 + 5 * 1 = 5 + 2 + 2 + 5 = 14
T(7) = T(2)T(6) + T(3)T(5) + T(4)T(4) + T(5)T(3) + T(6)T(2)
= 1 * 14 + 1 * 5 + 2 * 2 + 5 * 1 14 * 1 = 14 + 5 + 4 + 5 + 14 = 42

(2)
S(n) = Σ[k=2,n-1]{(k-1)T(k)T(n-k+1)}, n >= 3
これを書き下すと，
S(n)
= 1 * T(2)T(n-1) + 2 * T(3)T(n-2) + ... + (n-3) * T(n-2)T(3) + (n-2) * T(n-1)T(2)
= T(2)T(n-1) + T(3)T(n-2) + ... + T(n-2)T(3) + T(n-1)T(2)
+ T(3)T(n-2) + ... + T(n-2)T(3) + T(n-1)T(2)
...
+ T(n-2)T(3) + T(n-1)T(2)
+ T(n-1)T(2)
これはまた，
S(n)
= T(n-1)T(2)
+ T(n-2)T(3) + T(n-1)T(2)
...
+ T(3)T(n-2) + ... + T(n-2)T(3) + T(n-1)T(2)
+ T(2)T(n-1) + T(3)T(n-2) + ... + T(n-2)T(3) + T(n-1)T(2)
= T(2)T(n-1)
+ T(3)T(n-2) + T(2)T(n-1)
...
+ T(n-2)T(3) + ... + T(3)T(n-2) + T(2)T(n-1)
+ T(n-1)T(2) + T(n-2)T(3) + ... + T(3)T(n-2) + T(2)T(n-1)
= T(2)T(n-1)
+ T(2)T(n-1) + T(3)T(n-2)
...
+ T(2)T(n-1) + T(3)T(n-2) + ... + T(n-2)T(3)
+ T(2)T(n-1) + T(3)T(n-2) + ... + T(n-2)T(3) + T(n-1)T(2)
とも書けるので，最初の S(n) と最後の S(n) とを辺々加えて，
2 * S(n) = (n-1) * (T(2)T(n-1) + T(3)T(n-2) + ... + T(n-2)T(3) + T(n-1)T(2))
2 * S(n) = (n-1) * T(n)
がいえます。

(3)
・n = 3 の場合
左辺 = T(3) = 1
右辺 = (4 * 3 - 10)/(3 - 1) * T(2) = T(2) = 1
で，成立。
・n-1 までで成立すると仮定して n の場合
まず，
T(k) = (4k-10)/(k-1) * T(k-1), k = 3, ..., n-1
を仮定します。また，ヒントと思われる(？ (^^;) (2) を使って S(n) の関係を調べてみます。
S(n) = Σ[k=2,n-1]{(k-1)T(k)T(n-k+1)}
S(n-1)
= Σ[k=2,n-2]{(k-1)T(k)T(n-k)}
k -> k-1 と置き換えて
= Σ[k=3,n-1]{(k-2)T(k-1)T(n-k+1)}
k = 3, ..., n-1 なので，帰納法の仮定を使って，
= Σ[k=3,n-1]{(k-2) * (k-1)/(4k-10) * T(k)T(n-k+1)}
= Σ[k=3,n-1]{(k-1)(k-2)/(4k-10) * T(k)T(n-k+1)}
ここで，S(n) - 4 * S(n-1) を考えると，
S(n) - 4 * S(n-1)
= Σ[k=2,n-1]{(k-1)T(k)T(n-k+1)} - 4 * Σ[k=3,n-1]{(k-1)(k-2)/(4k-10) * T(k)T(n-k+1)}
= T(2)T(n-1) + Σ[k=3,n-1]{((k-1) - 4(k-1)(k-2)/(4k-10)) * T(k)T(n-k+1)}
= T(n-1) + Σ[k=3,n-1]{(k-1)((4k-10) - 4(k-2))/(4k-10) * T(k)T(n-k+1)}
= T(n-1) + Σ[k=3,n-1]{(-2)(k-1)/(4k-10) * T(k)T(n-k+1)}
= T(n-1) - 2 * Σ[k=3,n-1]{(k-1)/(4k-10) * T(k)T(n-k+1)}
ここで，
T(n-1) = Σ[k=2,n-2]T(k)T(n-k) = Σ[k=3,n-1]T(k-1)T(n-k+1)
k = 3, ..., n-1 なので，帰納法の仮定を使って，
T(n-1) = Σ[k=3,n-1]{(k-1)/(4k-10) * T(k)T(n-k+1)}
と書けるので，
S(n) - 4 * S(n-1) = T(n-1) - 2 * T(n-1) = - T(n-1)
S(n) = 4 * S(n-1) - T(n-1)
これを (2) を使って T の式にすると，
(n-1)/2 * T(n) = 4 * (n-2)/2 * T(n-1) - T(n-1)
T(n) = (4n-10)/(n-1) * T(n-1)
となり，n でも成立することが証明できました。

(4)
T(n) = (4n-10)/(n-1) * T(n-1), n >= 3
より，
T(n) = 2(2n-5)/(n-1) * T(n-1)
= 2^2 * (2n-5)(2n-7)/(n-1)(n-2) * T(n-2)
= ...
= 2^(n-2) * {(2n-5) * (2n-7) * ... * 3 * 1}/{(n-1) * (n-2) * 3 * 2} * T(2)
= 2^(n-2) * (2n-5)!/{(2n-6) * (2n-8) * ... * 4 * 2} * 1/(n-1)!
= 2^(n-2) * (2n-5)!/{2^(n-3) * (n-3)!} * 1/(n-1)!
= 2 * (2n-5)!/(n-1)!(n-3)!
= 2 * (2n-4)!/(n-1)!(n-3)! * 1/(2n-4)
= (2n-4)!/(n-2)!(n-2)! * 1/(n-1)
= (2n-4)C(n-2)/(n-1)
これは，カタラン数列ですね。例えば，
http://aozoragakuen.sakura.ne.jp/taiwa/taiwaNch04/node21.html
などをご覧ください。
なお，カタラン数としては (2n)C(n)/(n+1) の形がよく知られていますが，
今回の問題は，n -> n-2 だけずれているようです。

(感想)
上で示したサイトで，カタラン数の漸化式のことは知っていたので，
問題を見た途端に「カタラン数だな。」とは分かりました。
しかし，漸化式をじっくりと解いたのは初めてだったので，大変勉強になりました。
ありがとうございます。

ＮＯ２「kashiwagi」 6/30 07時51分受信更新7/5

226回解答

（1）ｋ＝2、n＝2の場合がT3であるから、定義の式に代入して、T3＝T2T2＝1

他も全く同様な計算をして、

T4＝T2T3+T3T2＝2T2T3＝1+1＝2

T5＝5、T6＝14、T7＝42、T8＝132　となる。

（2）ｎが偶数の時は項の数が偶数で対称であるから、

Tn＝T2Tn-1＋T3Tn-2＋・・・・・・・・・・・・・・・・・・・・・・・・・+Tn/2T（n/2）+1

　　　Tn-1T2+Tn-2T3+・・・・・・・・・・・・・・・・・・・・・・・・・・・+ T（n/2）+1 Tn/2

　　＝2（T2Tn-1＋T3Tn-2＋・・・・・・・・・・・・・・・・・・・・・・・・・+Tn/2T（n/2）+1）

また、題意より

Sn＝（2-1）T2Tn-1＋（3-1）T3Tn-2＋・・・・・・・・・・・・・・・・・・+（（ｎ/2）-1）Tn/2T（n/2）+1

　　　（ｎ-2）Tn-1 T2＋（ｎ-3）Tn-2 T3＋・・・・・・・・・・・・・・・+（（（ｎ/2）+1）-1）T（n/2）+1 Tn/2

　　＝（ｎ-1）（T2Tn-1＋T3Tn-2＋・・・・・・・・・・・・・・・・・・・・・・・・・+Tn/2T（n/2）+1）

　　＝（（ｎ-1）Tn）/2

因って、2Sn＝（ｎ-1）Tnである。ｎが奇数の場合も全く同様の手法で証明される。

（3）ｎ=3を代入すると、左辺はT3＝1、右辺は2T2/2＝1で成立する。

　ｎ＝ｋの場合、成立すると仮定すると、Tk＝（4ｋ-10）Tk-1/（ｋ-1）　・・・・・①

ここで、（2）の解より　2Sｋ＝（ｋ-1）Tk　・・・・・・・・・②

①を変形し、（ｋ-1）Tk＝（4ｋ-10）Tk-1

即ち、②より　2Sｋ＝（ｋ-1）Tk＝（4ｋ-10）Tk-1・・・・・・・③

また、（2）の解より　2Sｋ+1＝ｋTk+1　・・・・・・・・・④

ここで③よりの（ｋ-1）Tk＝（4ｋ-10）Tk-1を使い④を変形すると、

　2Sｋ+1＝ｋTk+1＝（4（ｋ+1）-10）Tk　　となる。

即ち、ｋTk+1＝（4（ｋ+1）-10）Tk　であるから、Tk+1＝＝（4（ｋ+1）-10）Tk　/（（ｋ+1）-1）

因って、ｎ＝ｋ+1の場合も成立する。これで証明できた。

（4）Tn＝（4ｎ-10）Tn-1/（ｎ-1）で右辺のｎを減少させていくと、

　　　　＝（（4ｎ-10）（4ｎ-14）（4ｎ-18）・・・・・・・6・2）T2/（ｎ-1）（ｎ-2）（ｎ-3）・・・・・3・2

ここで、T2＝1であるから、上の式を変形して、

　　　　＝2^ｎ-2（2ｎ-5）（2ｎ-7）・・・・（2ｎ-（2ｎ-1））×2^ｎ-1/（2ｎ-2）（2ｎ-4）・・・・4・2

　　　　＝（2ｎ-4）（2ｎ-5）（2ｎ-6）・・・・・2/（2ｎ-2）（2ｎ-4）²（2ｎ-6）²・・・・4²・2²

　　　　＝（2ｎ-4）！/（（ｎ-1）！（ｎ-2）！）

これが求める数列である。　Tn＝（2ｎ-4）！/（（ｎ-1）！（ｎ-2）！）

数列の名前は分かりません。

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。