私はプログラミング コンテスト F(n)= F(n-1)-F(n-2); でこのシーケンスに出くわしました。与えられた F0 と F1 で n 番目の項を見つける
( http://codeforces.com/contest/450/problem/B ) (コンテストは終了しました)
この問題の解決策は次のようになります。シーケンスは値 f0、f1、f1-f0、-f0、-f1、f0 - f1、そして再び f0 を取り、シーケンス全体が繰り返されます。
この値が繰り返されていることはわかりましたが、この循環的な順序の理由を見つけることができませんでした。周期的な順序とシーケンスを検索しましたが、周期の理由について実際の感触を与えることができる十分な資料を見つけることができませんでした.
この問題にアプローチする別の方法。F(n) = F(n - 1) - F(n - 2) は F(n) - F(n - 1) + F(n - 2) = 0 と同じであり、線形の差になります。式。このような方程式には基本解 a^n があり、a は多項式の根です。F(n) = a^n とすると、a^n - a^(n - 1) + a^(n - 2) = (a ^2 - a + 1)*a^(n - 2) = 0 なので、a^2 - a + 1 = 0 には、法 1 と引数 pi/3 を持つ 2 つの複素根 (見つけることができます) があります。したがって、それらのべき乗 1、a、a^2、a^3、... は単位円を一周し、2 pi/(pi/3) = 6 ステップ後に 1 に戻ります。
この解析には、対応する微分方程式の解析と同じ欠点があります。特定の種類の解を探す方法をどのように知るのでしょうか? 私はそれに対する答えを持っていません、おそらく他の誰かが持っています。それまでの間、線形差分方程式が表示されるたびに、a^n の形式の解について考えてみてください。