Evolton

北海道大学 2019年度 前期日程 第2次学力試験文系数学 第3問

nを自然数とする。
数列2，1，2，1，1のように各項が1または2の有限数列（項の個数が有限である数列）を考える。
各項が1または2の有限数列のうちすべての項の和がnとなるものの個数をsnとする。
例えば，n=1のときは，1項からなる数列1のみである。したがって，s1=1となる。
n=2のときは，1項からなる数列2と2項からなる数列1，1の2つである。したがって，s2=2となる。

(1) s3を求めよ。

(2) n≧3のとき，snをsn−1とsn−2を用いて表せ。

(3) 3以上のすべてのnの対してsn−αsn−1=β(sn−1−αsn−2)が
成り立つような実数α，βの組(α, β)を1組求めよ。

(4) snを求めよ。

難易度5/ 10計算量4/ 10目安14分

数列、場合の数　漸化式の変形、特性方程式、和の計算

方針

和が n になる数列を最後の項で分類する。最後が1なら直前までの和は n−1、最後が2なら直前までの和は n−2 なので、フィボナッチ型の漸化式が得られる。(3)は sn=sn−1+sn−2 を指定の形に因数分解するため、1−α=β、−αβ=1 を満たす組を選ぶ。最後は初期値 s1=1,s2=2 から一般項を決める。

解答

(1)
和が3となる数列は (1,1,1),(1,2),(2,1) の3つである。したがって s3=3 である。

(2) n≧3 とする。和が n となる数列を、最後の項が1であるものと2であるものに分ける。

最後の項が1であるなら、それを取り除いた残りの和は n−1 である。したがってその個数は sn−1 である。最後の項が2であるなら、それを取り除いた残りの和は n−2 であり、その個数は sn−2 である。この2種類は重ならないので sn=sn−1+sn−2(n≧3) である。

(3)
(2)より sn−αsn−1=(1−α)sn−1+sn−2 である。これが β(sn−1−αsn−2)=βsn−1−αβsn−2 と一致すればよい。したがって 1−α=β,1=−αβ を満たす α,β を取ればよい。これは α+β=1,αβ=−1 と同値である。例えば α=1+52,β=1−52 はこの条件を満たす。

(4) α=1+52,β=1−52 とする。この2数は r2=r+1 の2解である。漸化式 sn=sn−1+sn−2 の形から sn=Aαn+Bβn とおける。初期値 s1=1,s2=2 を用いると Aα+Bβ=1,Aα2+Bβ2=2 である。これを解くと、同値に sn=αn+1−βn+1α−β となる。α−β=5 だからsn=15{(1+52)n+1−(1−52)n+1}である。

別解

解法2（与えられた一次漸化式を反復する）

方針

最後の項による分類で漸化式を作った後、(3)で得た因数分解型の漸化式をそのまま反復する。特性方程式の一般論に頼らず、α,β の2通りの関係を連立して一般項を決める。

解答

(1)

(1,1,1),(1,2),(2,1) の3通りなのでs3=3.(2)

最後の項が1なら、それを除いた部分の和は n−1、最後の項が2なら和は n−2 である。よってsn=sn−1+sn−2(n≧3).(3)α=1+52,β=1−52とすれば α+β=1, αβ=−1 だから、sn−αsn−1=β(sn−1−αsn−2)が成り立つ。

(4)

上式を反復するとsn−αsn−1=βn−2(s2−αs1)=βn−2(2−α).2−α=β2 よりsn−αsn−1=βn.α,β を入れ替えて同様にsn−βsn−1=αn.2式の差を取れば(α−β)sn−1=αn−βnだからsn=αn+1−βn+1α−β=15{(1+52)n+1−(1−52)n+1}.なお、2を k 個含む場合の並べ方を数えるとsn=∑k=0⌊n/2⌋n−kCkとも表せ、一般項の独立な確認になる。

総評

難度5、目安時間14分。最後の項による分類で漸化式を作るところが本体で、以後はフィボナッチ型数列の処理である。(3)は特性方程式を知っていればすぐだが、答案では 1−α=β、1=−αβ の係数比較を明示すると説得力がある。一般項では指数が n ではなく n+1 になる点を初期値で確認したい。数列を列挙する(1)でも、(1,2) と (2,1) を別物として数えることが前提である。

冊子PDFで見る北大の数列の問題で問題集を作る

出典: 北海道大学 2019年度 前期 数学（大学公式の問題PDF）。問題文はHTML表示のために再入力・数式組版しています。