大学数学基礎解説

あるフィボナッチ数の和の整除性

フィボナッチ数,リュカ数

この記事の内容

kzaukzau様のこちらの記事 Fibonacci数の和の整除性についてのある予想(解決?) について、
大変興味深かったためしばらく考えていたがある程度形になったので記事にしたい。

まず問題は以下の通りのものとなる。

フィボナッチ数の和の整除性

$F_{n}$ をn番目のフィボナッチ数とし、 $s | t$ となる正の偶数 $s, t$ に対して

$\sum_{k = 0}^{n} F_{s k} ∣ \sum_{k = 0}^{n} F_{t k}$

証明自体は引用した記事ですでにつけられており、
本記事をご覧の方はぜひそちらも一読をお勧めする。

こいつはフィボナッチ数列ではない

結論を述べると、この問題を考えるに適切な数列はフィボナッチ数列ではない。
定理1では $s, t$ に偶数の条件が課せられているので
和に現れる項はすべてフィボナッチ数列の偶数番目の項 $F_{2 k}$ だが
奇数番目は $F_{2 k + 1}$ ではないとした方がうまくいく。
では奇数番目にいるのは何なのか。奇数番目のフィボナッチ数の代わりに
奇数番目のリュカ数 $L_{2 k + 1}$ が代わりにいる。
次のような数列を定義する。

数列 $G_{n}$ を次の隣接５項間漸化式で定義する
$G_{n + 4} = 3 G_{n + 2} - G_{n},$
$G_{0} = 0, G_{1} = 1, G_{2} = 1, G_{3} = 4$

漸化式の形から、偶数番目は偶数番目だけで定義され
奇数番目は奇数番目だけで定義されることがわかる。
また、漸化式の形はフィボナッチ数列、あるいはリュカ数列を定義する
有名な漸化式である $F_{n + 1} = F_{n} + F_{n - 1}$ を２項ごとに
とった数列が満たす漸化式と同じ形となっている。
（ここの詳細はこちらの弊記事をご参照いただきたい）
$G_{0} = 0, G_{2} = 1$ はフィボナッチ数列の0項目と2項目に一致し、
$G_{1} = 1, G_{3} = 4$ はリュカ数列の1項目、3項目に一致しているので
この数列 $G_{n}$ は偶数番目がフィボナッチ数列 $F_{2 n}$ と
奇数番目がリュカ数列 $L_{2 n + 1}$ と一致していることがわかる。
以下、この数列 $G_{n}$ の性質を見ることで元の定理を証明する。

$G_{n}$ の満たす漸化式

さて、 $G_{n}$ を上のように定義しておいてなんだが、流石に5項間漸化式は面倒くさい。
もうちょっとまからんか、ということで
フィボナッチ数列とリュカ数列の相互関係から次のような関係が言える。

$G_{n + 1} = h (n) G_{n} - G_{n - 1},$
$h (n) = \begin{array}{r} {\begin{cases} 1 \dots n : 奇数 \\ 5 \dots n : 偶数 \end{cases} \end{array}, G_{0} = 0, G_{1} = 1$

このとき $G_{2} = h (1) g_{1} - g_{0} = 1 \cdot 1 - 0 = 1$
$G_{3} = h (2) g_{2} - g_{1} = 5 \cdot 1 - 1 = 4$
となり、定義1の2項目、3項目と一致し、また
$G_{n + 1} = h (n) G_{n} - G_{n - 1}$ から
$h (n + 1) G_{n + 1} = G_{n + 2} + G_{n}$
$h (n - 1) G_{n - 1} = G_{n} + G_{n - 2}$
をもとの式に代入すると
$G_{n + 2} + G_{n} = h (n + 1) h (n) G_{n} - (G_{n} + G_{n - 2})$
$G_{n + 2} = (h (n + 1) h (n) - 2 ） G_{n} - G_{n - 2}$
を得る。（ $h (n + 1) = h (n - 1)$ を用いている）
$h (n + 1) h (n) = 5$ が $n$ によらず成り立つので
$G_{n + 2} = 3 G_{n} - G_{n - 2}$ となり定義2から
定義1が導ける。よって今後は定義2を用いる。

$G_{n}$ の性質（1）整除性

$G_{n}$ は以下の性質を持つ

G_{n}

の項番についての整除性

自然数 $n, m$ について $n | m$ のとき $G_{n} | G_{m}$

偶数番目はフィボナッチ数列だし、リュカ数にしても奇数番目同士なら整除性はある。
偶奇が混ざっても $F_{2 n} = F_{n} L_{n}$ なので割れるように出来ているのであるが
他でも使うあてがあるので、次の式の成立をもって整除性を示す。

k項ごと数列の満たす漸化式

$G_{n + k} = j_{n, k} G_{n} - G_{n - k}$
$j_{n, k + 1} = h (n + k) j_{n, k} - j_{n, k - 1} j_{n, 1} = h (n), j_{n, 2} = 3$

補題3の証明

定義2から

G_{n + 1} = h (n) G_{n} - G_{n - 1}

なので

k = 1 の と き j_{n, 1} = h (n) と し て 確 か に 成 り 立 つ 。

定義２から定義1を得る計算の際に示した通り

G_{n + 2} = 3 G_{n} - G_{n - 2}

なので

k = 2 の と き j_{n, 2} = 3 と し て 確 か に 成 り 立 つ 。

k = m - 1, k = m

で成り立つと仮定する。このとき

G_{n + m - 1} = j_{n, m - 1} G_{n} - G_{n - m + 1} \dots (1)

G_{n + m} = j_{n, m} G_{n} - G_{n - m} \dots (2)

h (n + m) \cdot (2) - (1)

を計算すると

G_{n + m + 1} = (h (n + m) j_{n, m} - j_{n, m - 1} ） G_{n} - h (n + m) G_{n - m} + G_{n - m + 1}

G_{n + m + 1} = (h (n + m) j_{n, m} - j_{n, m - 1} ） G_{n} - h (n - m + 2 m) G_{n - m} + G_{n - m + 1}

G_{n + m + 1} = (h (n + m) j_{n, m} - j_{n, m - 1} ） G_{n} - h (n - m) G_{n - m} + G_{n - m + 1}

G_{n + m + 1} = (h (n + m) j_{n, m} - j_{n, m - 1} ） G_{n} - G_{n - m - 1}

となるので

j_{n, m + 1} = h (n + m) j_{n, m} - j_{n, m - 1}

とすれば
数学的帰納法より補題3が成り立つことがわかる

この補題から整除性は直ちに従う

定理2の証明

任意の自然数kについて $G_{n} | G_{k n}$ を示す
$k$ についての数学的帰納法で示す。
$k = 1$ のときあきらか
$k \leq m$ のとき成り立つと仮定すると
$G_{n} | G_{(m - 1) n}, G_{n} | G_{m n}$ なので
$G_{(m + 1) n} = j_{m n, m} G_{n m} - G_{(m - 1) n}$
より $G_{n} | G_{(m + 1) n}$ で $k = m + 1$ でも成り立つ。
よって任意の自然数kについて $G_{n} | G_{k n}$ は示された。

$j_{n, k}$ の計算

定理2の証明では用いなかったが、あとで使うことになるため
補題3の $j_{n, k}$ が何者であるかを明らかにしておく。

j_{n, k}

の計算

この数列は

n, k

いずれにも依存するが

n

への依存は漸化式からわかる通り

h (n + k)

の部分に限られ、

h (n + k)

は

n + k

の偶奇しか影響しないので

n

について考える必要があるのはその偶奇だけということがわかる。
ゆえ、

j_{n, k}

について、特に

n

が偶数の場合を

j_{0, k}

、

n

が奇数の場合を

j_{1, k}

と書くことにする。

n

が偶数の場合

h (n + k) = h (k)

なので漸化式は

j_{0, k + 1} = h (k) j_{0, k} - j_{0, k - 1}, j_{0, 1} = h (0) = 5, j_{0, 2} = 3

となる。初項、2項目が違うだけで

G_{n}

と同じ漸化式であることがわかった。
何項か計算すると

j_{0, 3} = h (2) j_{0, 2} - j_{0, 1} = 5 \cdot 3 - 5 = 10

j_{0, 4} = h (3) j_{0, 3} - j_{0, 2} = 10 - 3 = 7

j_{0, 1} = 5, j_{0, 3} = 10 = 5 \cdot 2

で

j_{0, k + 1} = h (k) j_{0, k} - j_{0, k - 1}

なので

j_{0, 2 k + 1} = 5 \cdot F_{2 k + 1}

とわかる。同様に

j_{0, 2} = 3, j_{0, 4} = 7

なので

j_{0, 2 k} = L_{2 k}

とわかる。
概ね

G_{n}

をひっくり返したような数列になっている。

n

が奇数の場合

h (n + k) = h (k + 1)

なので漸化式は

j_{1, k + 1} = h (k + 1) j_{1, k} - j_{1, k - 1}, j_{1, 1} = h (1) = 1, j_{1, 2} = 3

続く2項は

j_{1, 3} = h (3) j_{1, 2} - j_{1, 1} = 3 - 1 = 2

j_{1, 4} = h (4) j_{1, 3} - j_{1, 2} = 5 \cdot 2 - 3 = 7

j_{1, k + 1} = h (k + 1) j_{1, k} - j_{1, k - 1}

についても
2項ごとの漸化式に変形するとやはり

j_{1, k + 2} = 3 j_{1, k} - j_{1, k - 2}

が得られるので、

j_{1, 2 k + 1} = F_{2 k + 1}, j_{1, 2 k} = L_{2 k}

以上から

j_{n, 2 k + 1} = h (n) F_{2 k + 1}, j_{n, 2 k} = L_{2 k}

とまとめられることがわかる。

$G_{n}$ の性質（2）最大公約数

$G_{n}$ は以下の性質を持つ

G_{n}

の項間の最大公約数

自然数 $n, m$ について $GCD (G_{n}, G_{m}) = G_{GCD (n, m)}$

フィボナッチ数でよく見るやつである。
これについても偶数番目はフィボナッチ数列だし、リュカ数にしても奇数番目同士なら成り立っている。
偶奇が混ざると整除性よりはおそらく若干面倒になる。
（ $F_{2 n} = F_{n} L_{n}$ で行けそうだけど、 $F_{n} と L_{n}$ は $3 | n$ で共通因数 $2$ を持つので考えることがある）
こちらも他のついでがあるので、まず次の補題を示す。

G_{n}

の加法定理(拡張版)

$G_{s} G_{s (n + m)} = h (s (m + 1) n + 1) G_{s m} G_{s (n + 1)} - h (s m (n - 1) + 1) G_{s (m - 1)} G_{s n}$

係数の $h$ がややこしいことになっているが、要は $m, n$ の偶奇で決まるんだ、ぐらいのことしか言っていない。
証明の方法は数列 $G_{n}$ にかえて $G_{n}^{'} = G_{s n} / G_{s}$ について考える。
補題3から $G_{n}^{'}$ の漸化式がわかる。
$j_{n, k}$ についての計算結果から
$s$ が偶数の時 $G_{n}^{'}$ は係数に $h (n)$ などを含まない線形漸化式で
一般リュカ数列 $U_{n}$ になるので加法定理の計算は
一般リュカ数列のそれになる。
その場合の証明はこちらの弊記事参照。
以下では $s$ が奇数の場合について進める。
このとき $G_{n}^{'}$ の満たす漸化式は
$G_{n + 1}^{'} = j_{n s, s} G_{n}^{'} - G_{n - 1}^{'}$
$j_{n s, s} = h (n s) F_{s} = h (n) F_{s} ∵ s : o d d$
$G_{n + 1}^{'} = F_{s} h (n) G_{n}^{'} - G_{n - 1}^{'}$
とし、以下を示す。
$G_{n + m}^{'} = h ((m + 1) n + 1) G_{m}^{'} G_{n + 1}^{'} - h (m (n - 1) + 1) G_{m - 1}^{'} G_{n}^{'}$
(両辺に $G_{s}^{2}$ をかけると補題の形に戻る)

補題5の証明

補題5(

G_{n}

の拡張加法定理)の証明

数学的帰納法で示す。

m = 1

のとき

h (2 n + 1) G_{1}^{'} G_{n + 1}^{'} - h ((n - 1) + 1) G_{0}^{'} G_{n}^{'}

= h (1) \cdot 1 \cdot G_{n + 1}^{'} - h (n) \cdot 0 \cdot G_{n}^{'}

= G_{n + 1}^{'}

より正しい。

m = 2

のとき

h (n + 1) G_{2}^{'} G_{n + 1}^{'} - h (1) G_{1}^{'} G_{n}^{'}

= h (n + 1) \cdot G_{2}^{'} \cdot G_{n}^{'} - 1 \cdot 1 \cdot G_{n}^{'}

= h (n + 1) F_{s} G_{n + 1}^{'} - G_{n}^{'}

G_{n + 2}^{'}

より正しい

m \leq k

で正しいと仮定する。このとき

G_{n + (k - 1)}^{'} = h (k n + 1) G_{k - 1}^{'} G_{n + 1}^{'} - h ((k - 1) (n - 1) + 1) G_{(k - 2)}^{'} G_{n}^{'} \dots (1)

G_{n + k}^{'} = h ((k + 1) n + 1) G_{k}^{'} G_{n + 1}^{'} - h (k (n - 1) + 1) G_{k - 1}^{'} G_{n}^{'} \dots (2)

F_{s} h (n + k) \cdot (2) - (1)

を計算すると左辺は

G_{n + k + 1}^{'}

、右辺は
長くなるので

- G_{n}^{'}

でくくった係数だけ見ると

F_{s} h (n + k) h (k (n - 1) + 1) G_{k - 1}^{'} - h ((k - 1) (n - 1) + 1) G_{(k - 2)}^{'}

h ((k + 1) (n - 1) + 1) = h ((k - 1) (n - 1) + 1)

をくくりだすと

h ((k + 1) (n - 1) + 1) {F_{s} h (n + k) h (k (n - 1) + 1) / h ((k + 1) (n - 1) + 1) G_{k - 1}^{'} - G_{k - 2}^{'}}

G_{k - 1}^{'}

の係数の因子である

h (n + k) h (k (n - 1) + 1) / h ((k + 1) (n - 1) + 1)

について

n

を偶数とすると

h (n + k) h (k (n - 1) + 1) / h ((k + 1) (n - 1) + 1)

= h (k) h (k + 1) / h (k + 1 + 1)

= h (k + 1)

n

を奇数とすると

h (n + k) h (k (n - 1) + 1) / h ((k + 1) (n - 1) + 1)

= h (1 + k) h (1) / h (1)

= h (k + 1)

よって

n

の偶奇によらず

h (n + k) h (k (n - 1) + 1) / h ((k + 1) (n - 1) + 1) = h (k + 1) = h (k - 1)

ゆえ

h ((k + 1) (n - 1) + 1) {F_{s} h (n + k) h (k (n - 1) + 1) / h ((k + 1) (n - 1) + 1) G_{k - 1}^{'} - G_{(k - 2)}^{'}}

= h ((k + 1) (n - 1) + 1) (F_{s} h (k - 1) G_{k - 1}^{'} - G_{k - 2}^{'})

= h ((k + 1) (n - 1) + 1) G_{k}^{'}

F_{s} h (n + k) \cdot (2) - (1)

の

G_{n + 1}^{'}

でくくった係数を見ると

F_{s} h (n + k) h ((k + 1) n + 1) G_{k}^{'} - h (k n + 1) G_{k - 1}^{'}

h ((k + 2) n + 1) = h (k n + 1)

をくくりだすと

h (k n + 1) {F_{s} h (n + k) h ((k + 1) n + 1) / h (k n + 1) G_{k}^{'} - G_{k - 1}^{'}}

h (n + k) h ((k + 1) n + 1) / h (k n + 1)

は先ほど同様に

n

の偶奇によらず

h (k)

となることがわかるので

F_{s} h (n + k) h ((k + 1) n + 1) G_{k}^{'} - h (k n + 1) G_{k - 1}^{'}

= h (k n + 1) {F_{s} h (k) G_{k}^{'} - G_{k - 1}^{'}}

= h (k n + 1) G_{k + 1}^{'}

以上から

G_{n + k + 1}^{'} = h (k n + 1) G_{k + 1}^{'} G_{n + 1}^{'} - h ((k + 1) (n - 1) + 1) G_{k}^{'} G_{n}^{'}

となり

m = k + 1

の時も成り立ち、任意の自然数

m

で成り立つことが示せる。

準備が整ったので本題の定理４の証明に進む

定理４

定理４(

G_{n}

の最大公約数)の証明

補題3と補題5より一般に自然数

x, y (x > y)

について

j_{x, y} G_{x} - G_{x - y} = h ((y + 1) x + 1) G_{y} G_{x + 1} - h (y (x - 1) + 1) G_{y - 1} G_{x}

ゆえ

G_{x - y} = {h (y (x - 1) + 1) G_{y - 1} + j_{x, y}} G_{x} - h ((y + 1) x + 1) G_{y} G_{x + 1}

が成り立つ。

GCD (n, m) = l

と書くことにするとき
ベズーの等式より

a n + b m = l

となる整数

a, b

が存在する。

n, m, l

全て正の数で

l \leq n, l \leq m

より

a, b

のいずれかは非正。
適当に文字を置きなおして

a n - b m = l a, b \geq 0

としてよい。

G_{a n - b m} = {h ((a n - 1) b m + 1) G_{b m + 1} + j_{a n, b m}} G_{a n} - h ((b m + 1) a n + 1) G_{a n + 1} G_{b m}

左辺は

G_{l}

となる。
右辺について

G_{n} | G_{a n}, G_{m} | G_{b m}

より

G_{a n} = A G_{n}, G_{b m} ＝ B G_{m}, A, B は 整 数

と書くことにすると

G_{l} = {h ((a n - 1) b m + 1) G_{b m + 1} + j_{a n, b m}} A G_{n} - h ((b m + 1) a n + 1) G_{a n + 1} B G_{m}

と表せるので、ベズーの等式より

GCD (G_{n}, G_{m}) | G_{l}

また

GCD (n, m) = l

より

l | n, l | m

なので

G_{l} | G_{n}, G_{l} | G_{m}

よって

G_{l} | GCD (G_{n}, G_{m})

以上から

GCD (G_{n}, G_{m}) = G_{GCD (n, m)}

$G_{n}$ の和の計算

$G_{n}$ の和の計算のため補題5を利用する。
補題5で $m = n$ とすると
$G_{s} G_{2 s n} = h (s (n + 1) n + 1) G_{s n} G_{s (n + 1)} - h (s n (n - 1) + 1) G_{s (n - 1)} G_{s n}$
$n (n + 1)$ は偶数なので
$G_{s} G_{2 s n} = h (1) G_{s n} G_{s (n + 1)} - h (1) G_{s (n - 1)} G_{s n}$
$G_{s} G_{2 s n} = G_{s (n + 1)} G_{s n} - G_{s n} G_{s (n - 1)}$
$s$ は任意の自然数、 $G_{2 s n} = F_{2 s n}$ なので
$\sum_{k = 0}^{n} F_{2 s k} = \frac{1}{G_{s}} \sum_{k = 0}^{n} （ G_{s (k + 1)} G_{s k} - G_{s k} G_{s (k - 1)})$
$\sum_{k = 0}^{n} F_{2 s k} = \frac{G_{s (n + 1)} G_{s n} - G_{s \cdot 1} G_{s \cdot 0}}{G_{s}} = \frac{G_{s (n + 1)} G_{s n}}{G_{s}}$

$\sum_{k = 0}^{n} F_{2 s k}$ の整除性

$\sum_{k = 0}^{n} F_{2 s k} = \frac{G_{s (n + 1)} G_{s n}}{G_{s}}$
について $GCD (G_{s (n + 1)}, G_{s n}) = G_{s}$ なので
$\sum_{k = 0}^{n} F_{2 s k} = \frac{G_{s (n + 1)} G_{s n}}{GCD (G_{s (n + 1)}, G_{s n})} = LCM (G_{s (n + 1)}, G_{s n})$
ここで $LCM$ は2項の最小公倍数を表す。
これより $s | t$ なる自然数 $s, t$ について

$\sum_{k = 0}^{n} F_{2 s k} = LCM (G_{s (n + 1)}, G_{s n}), \sum_{k = 0}^{n} F_{2 t k} = LCM (G_{t (n + 1)}, G_{t n})$
（係数 $2$ を外出ししているので $s, t$ が $2$ の倍数である必要はない。）
$s | t$ と $G_{n}$ の整除性により $G_{s n} | G_{t n}, G_{s (n + 1)} | G_{t (n + 1)}$ であるので
$LCM (G_{t (n + 1)}, G_{t n})$ は $G_{s n}, G_{s (n + 1)}$ の公倍数であることがわかる。
よって、最小公倍数の性質から
$LCM (G_{s (n + 1)}, G_{s n}) | LCM (G_{t (n + 1)}, G_{t n})$
即ち
$\sum_{k = 0}^{n} F_{2 s k} | \sum_{k = 0}^{n} F_{2 t k}$
が言えた。

投稿日：2023年8月9日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

TKSS

5569

他の人のコメント

コメントはありません。

読み込み中

TKSS

あるフィボナッチ数の和の整除性

この記事の内容
こいつはフィボナッチ数列ではない
$G_n$の満たす漸化式
$G_n$の性質（1）整除性
$G_n$の性質（2）最大公約数
$G_n$の和の計算
$\sum_{k=0}^{n}F_{2sk}$の整除性

あるフィボナッチ数の和の整除性

この記事の内容

こいつはフィボナッチ数列ではない

Gnの満たす漸化式

Gnの性質（1）整除性

jn,kの計算

Gnの性質（2）最大公約数

Gnの和の計算

∑k=0nF2skの整除性

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

$G_{n}$ の満たす漸化式

$G_{n}$ の性質（1）整除性

$j_{n, k}$ の計算

$G_{n}$ の性質（2）最大公約数

$G_{n}$ の和の計算

$\sum_{k = 0}^{n} F_{2 s k}$ の整除性