イントロダクション
フィボナッチ数列を
で定めます。
最初の方をいくつか見てみると次のようになっています。
では問題です。
フィボナッチ数列の1個飛ばし数列を
で定めます。フィボナッチ数列のときと同様の漸化式をに対して探してください。
いきなり答えを書くと
です。
たとえば上の表を見るとなのででは成り立っています。一般に成り立つことは数学的帰納法で示すことができます。
では、これはどう導出すればいいのか?1個飛ばしではなくて、任意に固定したについての倍数番目を取りだした数列だとどうか?一般の定数係数で斉次の線形漸化式で定義される数列に対して適用できる方法はあるのでしょうか?
こういったことを今から議論していきます。
導出
シフト演算というものを定義します。これは数列を受け取って数列を返す関数で
と定義されます。つまり初項を捨てて、あとの項は1個左にずらすという写像です。
このシフト演算を使うとフィボナッチ数列の漸化式は次のように表現できます。
ここで左辺のは二つの合成、は恒等変換、右辺のは常にな数列を表すことにします。
この式の両辺に左側からを作用させます。
左辺を計算してみると
で
となります。
さて、これをもとの漸化式のような形で書き直すとどうなるでしょうか。次のようになります:
ここのにを代入すればほしい式そのものですね。これで導出できました。
考察と一般化
上の導出ではというものを天下りに与えて、計算するとうまくいっていました。これは何をやっているのでしょうか?
と多項式を定義したときにですが、このときという別の多項式を与えたら、と偶数次数の元だけ残ったことがポイントです。
つまり、多項式について多項式であって
となることを見つけられたのがよかったのです。
このことを一般に述べると次です。
自然数を固定しましょう。定数係数で斉次の線形漸化式
が与えられます。今は定数でとします。多項式を
で定めるとシフト演算を使って漸化式は
と書けます。
ここに多項式であって
なるものが見つけられたとしたら
となるので
となり、多項式の係数で数列の漸化式が得られます。
多項式の存在
さて、問題は与えられた多項式に対して
となる多項式を求めることに帰着しました。これはいつでも存在するでしょうか。
考えている係数体が標数という仮定のもとでYesです。
を標数の体とする。を多項式とする。を以上の自然数とする。
このときがあって
かつ
となる。
1の原始乗根の一つをとおき、を添加した体で考える。を次で定める。
とおく。
のときの因子を含んでいるので明らかにである。
を示す。が標数なのでは分離拡大である。またの上共役な元は1の原始乗根なのでに入っている。よっては正規拡大。したがってガロアの基本定理よりの任意の元で不変なの元全体の集合はに等しい。
今多項式にの元を作用させると、はをある (はと互いに素な整数)に写すものなので、にを作用させた多項式を考えると
となり不変。よって、である。
また、任意のの乗根について
なことからはの倍数の次数の項しかないことが分かる (標数なことを再び使った)。
そこでとなる多項式がある。なのでである。
を考えると、が分かる。
フィボナッチ数列の2項飛ばし、3項飛ばし, etc
2項飛ばし
さて一般的な方法が分かったのでフィボナッチ数列の2項飛ばしや3項飛ばしなどに応用してみましょう。
まずは2項飛ばし ()です。
に対して
を計算しましょう。ここではの原始乗根です。
.........
と出ました。
よって
で
です!
3項飛ばし
次は3項飛ばし ()です。
を計算しましょう。
.........
と出ました。
よって
で、
です。
4項飛ばし
次は4項飛ばし ()です。しんどいのでMathematicaにやってもらいました。
で、
です。
5項飛ばし
次は5項飛ばし ()です。同じくMathematicaで。
で、
です。
を動かしたときに何か係数に規則性があるのか…?という疑いも生じてきますが、この辺で終わりにします。
まとめ
定数係数で斉次の線形漸化式を満たす数列 (こういうのをC-finite sequenceというそうです)の固定した自然数の倍数番目の項を取り出した数列の漸化式を与える方法を紹介しました。それをフィボナッチ数列に応用してみました。
この話は参考文献のThe Concrete Tetrahedronの定理4.2がもとになっています。C-finite sequenceの固定した自然数の倍数番目の項を取り出した数列もまたC-finite sequenceとなることが書かれているんですが、証明は読者の演習問題となっています。そこで考えてみたという次第です。
まだ読んでいる途中なのですが、なかなか面白い本です。
追記 (2021/7/4)
以上を見ると
ですね。規則性が気になります。最後の項はでしょうね。真ん中の項の係数はどうでしょうか。OEISに投げてみました。
OEIS
なんと、真ん中の項の係数はリュカ数列の模様です!つまり、次の式ということです。
これの証明はたとえば以下のようにすればいいでしょう。
方程式の解をとします。解と係数の関係よりです。多項式がを満たすことを言えばよいでしょう。そのためにはを言えばいいです。これは言えて、実際、たとえばの方は
なのでOKです。ここにリュカ数列の一般項を使いました。
追記2 (2021/7/10) 正標数の場合
定理1は標数の場合を扱いましたが、実は正標数でも成り立ちます。この節は
@waidotto
さんの助言をもとに執筆しました。
を体とする。を多項式とする。を以上の自然数とする。
このときがあって
かつ
となる。
標数の場合は証明したので、標数の場合を示す。ではと互いに素とする。
と表したときに、
とおく。すると、フロベニウス写像の準同型性より、
が分かる。
今、原始乗根を考えて、とおく。とが互いに素なのでこれは考えることができる。定理1の証明と同様にを考えよう。
は分離拡大である。なぜなら、多項式はその微分と互いに素だから分離多項式である。よってその約元であるの最小多項式も分離多項式であるからである。よって定理1の証明と同様にが導かれる。
となるがあることも同様にわかる。ただしこの証明ではで割る操作が必要になるのだが、とが互いに素なおかげで可能なことに注意しておく。
したがって、かつとなり証明が終わる。
実際、である。