正整数の関数方程式(OMC144-E)
問題のリンクはこちらです。ちなみに、最もお気に入りの自作問題です。それでは、よろしくお願いします。
問題
OMC144-E (改)
正整数値に対して定義され、正整数値をとる関数 \(f\) が任意の正整数 \(n,m\) に対して \[f(m+n+1) = f(m)f(n) + f(m+1)f(n+1)\] を満たす。このとき、\(f\) を求めよ。
正整数での関数方程式です。珍しいですね。
解説
step0.解の予想
適当な数を代入することで、簡単な多項式の形では無さそうなことがわかります。 これだけでも大きな収穫ですが、式の形がフィボナッチ数の加法定理に似ていることから、フィボナッチ数(とその拡張)あたりが解の候補になると予測できればかなり良いですね。
まとめ
・状況の把握と、答えの予測のために実験をしましょう。実験は本当に大切です。