ながめも

競技プログラミングについて

2015年度東大理系数学第4問(3) 解説

(1), (2)は他の方の解説に譲るとして、(3)を考えます。

(2)までの結果をまとめると、


p_1 = 1,  p_2 = 1\\
p_{n+1} + p_{n-1} = 3p_{n} \\

ということでした。つまり、ある項はその前後の項を足して3で割った数であるということです。

これと、フィボナッチ数列の奇数番目が等しいことを証明せよというのが今回の問題です。

簡単に言えば、以下の図が書ければ終わりです。

f:id:coonevo:20210305041237j:plain

あとはこの図を用いながら帰納法で示せるかと思います。

多くの解説が数式でゴリ押していますが、漸化式でわざわざ n-1を使っているあたり、問題作成者はある項とその前後の関係が〜という思想があったんだろうと感じました。

(実は本番に解いているのですが、(1)の証明ができなくて(2)のみを解いて終わりにした記憶があります。。。)