シングマスターの無限族とフィボナッチ数

はじめに

二項係数とフィボナッチ数の面白い関係を紹介します。

最初に結論を提示し、後半で証明します。
そのあと、パスカルの三角形との関係などを確かめます。
お急ぎの方は、結論部分だけでもみていただければと思います。

この記事では $F_n$ でフィボナッチ数を表し、$L_n$　でリュカ数を表します。

$\{F_n\}=\{0,1,1,2,3,5,8,13,21,34,55,89,\cdots \}(n\ge 0)$

$\{L_n\}=\{2,1,3,4,7,11,18,29,47,76,123,199,\cdots \}(n\ge 0)$

フィボナッチ数・リュカ数は次のように漸化式で定義できます。

また、記号 $\phi$ で黄金比を表します。すなわち

${\displaystyle \phi =\frac{1+\sqrt{5}}{2}}$

二項係数とフィボナッチ数の不思議な関係

シングマスターの無限族

まずは、次の式をご覧ください。

${\displaystyle {}_x{C}_y+{}_x{C}_{y+1}={}_x{C}_{y+2}}$

(余談ですが、まるでフィボナッチ数やリュカ数の漸化式みたいな式ですね。)

この式が成り立つ整数 $x,y$ について考えます。

たとえば、

$({}_{14}{C}_4,{}_{14}{C}_5,{}_{14}{C}_6)=(1001,2002,3003)$

について

${}_{14}{C}_4+{}_{14}{C}_5={}_{14}{C}_6$

となりますので、$(x,y)=(14,4)$ は解の一つとなります。

このような $x,y$ は他にもあるのでしょうか?

実は、この問題には既に答えが出ています。

この式により、フィボナッチ数を使って無数の$x,y$の組み合わせが得られます。シングマスターが1975年に発表した定理だそうです。

参考: パスカルの三角形にたくさん出てくる数: 3003

黄金比との関係、3項の比とフィボナッチ数の関係

さらに今日、次のような関係もあることに気が付きました!

まとめるとこうなります。

実に美しい関係だと思いませんか?

具体例

$x,y$の具体的な値は次のようになります。

証明の方針

では、ここから上記の式を証明していきます。
証明すべきことを3つに分けます。

証明すべきこと(その1)の証明

まずは、１つめの証明です。

これを証明します。

$x,y$ は二項係数の添字ですから、

$x\ge y+2\ge 2$

であることに注意します。

${\displaystyle {}_x{C}_y+{}_x{C}_{y+1}={}_x{C}_{y+2}}$

を展開して整理していきます。

${\displaystyle \frac{x!}{(x-y)!y!}+\frac{x!}{(x-y-1)!(y+1)!}=\frac{x!}{(x-y-2)!(y-2)!}}$

分母を払うと

${\displaystyle (y+2)(y+1)+(x-y)(y+2)=(x-y)(x-y-1)}$

展開して整理すると

$y^2-3xy+x^2-3x-2=0$

ぺル型方程式(あとで説明します。)の形にしたいので、両辺を $20$ 倍してから平方完成します。

$20y^2-60xy+20x^2-60x-40=0$

$5(3x-2y{)}^2-(5x+6{)}^2=4$

ここで

$$\begin{array}{r}\{\begin{array}{l}X=3x-2y\\ Y=5x+6\end{array}\end{array}$$

とおくと、$X,Y$ は自然数で、

の関係にあることがわかります。

ペル型方程式 $5X^2-Y^2=4$ の解

この形は「ペル型方程式」と呼ばれており、無限個の自然数解を持ちます。
ペル型方程式の中でも、$5X^2-Y^2=4$のすべての自然数解は次のように奇数番目のフィボナッチ数とリュカ数で表すことができることが知られています。

証明はこの記事では省略しますが、気になる方はこちらの記事をご覧ください。

Arithmetica算術ノート:フィボナッチ数の判定式（1） 二次体の整数の整除と単数

これで、$X,Y$ の候補をしぼることができます。

$$\begin{array}{r}\{\begin{array}{l}X=F_{2n+1}\\ Y=L_{2n+1}\end{array}\end{array}$$

(不適な解も含んでいることに注意してください。)

$5$ を法として考えると

$Y=5x+6\equiv 1\mathrm{mod}5$

となります。リュカ数は

$\{2,1,3,4,7,11,18,29,47,\cdots \}\equiv \{2,1,3,4,2,1,3,4,2,\cdots \}\mathrm{mod}5$

と周期的に変化します(証明略)から、

　$Y=L_{4n+1}$

の場合のみ$x=\frac{L_{4n+1}-6}{5}$ が整数になることがわかります。

次に $y$ について考えます。$x=\frac{L_{4n+1}-6}{5},X=F_{4n+1}$ を代入すると

${\displaystyle \begin{array}{rl}y& =\frac{3x-X}{2}\\ & =\frac{3\cdot \frac{L_{4n+1}-6}{5}-F_{4n+1}}{2}\\ & =\frac{1}{10}(3L_{4n+1}-5F_{4n+1}-18)\end{array}}$

ここで次の公式を使います。

${\displaystyle \begin{array}{rl}y& =\frac{1}{10}(3L_{4n+1}-5F_{4n+1}-18)\\ & =\frac{1}{10}(3L_{4n+1}-L_{4n+2}-L_{4n}-18)\\ & =\frac{1}{10}(3L_{4n+1}-(L_{4n+1}+L_{4n})-L_{4n}-18)\\ & =\frac{1}{10}(2L_{4n+1}-2L_{4n}-18)\\ & =\frac{1}{10}(2L_{4n-1}-18)\\ & =\frac{L_{4n-1}-9}{5}\end{array}}$

ここで
　$L_{4n-1}\equiv 4\mathrm{mod}5$

ですから、
$$\begin{array}{r}\{\begin{array}{l}X=F_{4n+1}\\ Y=L_{4n+1}\end{array}\end{array}$$
のときは $y$ は必ず整数になることがわかります。

$x\ge y+2\ge 2$

に注意して、添字を見やすいように4ずらして得られた式を整理すると次のようになります。

さらに次の公式を使って変形しましょう。

公式2で　$j=2n,k=2n+3$ とすれば

$5F_{2n}{F}_{2n+3}=L_{4n+3}-4$

となりますから、先ほどの式に代入して

${\displaystyle \begin{array}{rl}y& =\frac{L_{4n+3}-9}{5}\\ & =\frac{(5F_{2n}{F}_{2n+3}+4)-9}{5}\\ & =F_{2n}{F}_{2n+3}-1\end{array}}$

同様に、公式2で　$j=2n+2,k=2n+3$ とすれば

$5F_{2n+2}{F}_{2n+3}=L_{4n+5}-1$

となりますから、先ほどの式に代入して

${\displaystyle \begin{array}{rl}x& =\frac{L_{4n+5}-6}{5}\\ & =\frac{(5F_{2n+2}{F}_{2n+3}+1)-6}{5}\\ & =5F_{2n+2}{F}_{2n+3}-1\end{array}}$

以上より、$x,y$　は次のとおりとなります。

証明すべきこと(その2)の証明

次に、2つめの証明です。

これを証明します。

この式から始めます。
まず、リュカ数は黄金比を使って次のように表現できます(証明略)。

$L_n={\phi }^n+{(-\frac{1}{\phi })}^n$

これを代入すると、

次のように変形します。

両辺の床関数をとると

ここで $|-\frac{1}{\varphi }|<1$ ですから、

これで証明できました!

証明すべきこと(その3)の証明

最後に、3つめの証明です。

これを証明します。
$\Leftarrow$ は自明ですから、$\Rightarrow$について以下証明します。

これに

${\displaystyle \begin{array}{r}\{\begin{array}{l}x=F_{2n+2}{F}_{2n+3}-1\\ y=F_{2n}{F}_{2n+3}-1\end{array}\end{array}}$

を代入します。

ここで

${\displaystyle \begin{array}{rl}{F}_{2n+2}{F}_{2n+3}-F_{2n}{F}_{2n+3}& =(F_{2n+2}-F_{2n})F_{2n+3}\\ & =F_{2n+1}{F}_{2n+3}\end{array}}$

なので、

ここで次の公式を使います。

公式３で
$i=2n,j=1,k=2$ とすれば、

$F_{2n+1}{F}_{2n+2}-F_{2n}{F}_{2n+3}=1$

$\therefore F_{2n}{F}_{2n+3}+1=F_{2n+1}{F}_{2n+2}$

公式３で
$i=2n+1,j=1,k=1$ とすれば、
$F_{2n+2}{F}_{2n+2}-F_{2n+1}{F}_{2n+3}=-1$

$\therefore F_{2n+1}{F}_{2n+3}-1=F_{2n+2}{F}_{2n+2}$

これらの式を使うと

これで証明の完成です!

黄金比やパスカルの三角形との関係

さて、得られた関係式を改めてみてみましょう。

3つめの式では、　$x,y$ を床関数と黄金比で表しています。

${\displaystyle \begin{array}{r}\{\begin{array}{l}x=\lfloor \frac{{\phi }^{4n+5}}{5}\rfloor -1\\ y=\lfloor \frac{{\phi }^{4n+3}}{5}\rfloor -1\end{array}\end{array}}$

この式をみると、シングマスターの無限族に含まれる数字がパスカルの三角形のどのあたりに出てくるかわかります。

パスカルの三角形とは、次のように二項係数を三角形にならべたものでした。

まず、$x,y$ は $n$ が $1$ 増えるごとに約 ${\phi }^4(\fallingdotseq 6.85)$ 倍ずつ増えていくことがわかります。

また、
　$x:(x-y):y\fallingdotseq {\phi }^2:\phi :1$
ですから、パスカルの三角形の行の中では、両端からの比がおよそ $1:\phi$ の位置にあることになります。

パスカルの三角形は左右対称ですので、同じ行の中にもう一つ同じ数字があります。2つの数字の、行の中での位置の両端からの比は $\phi :1:\phi$ であることもわかりますね。

全体が相似の関係になっており、フラクタルのように思えます。面白いですね!

より直接的な表現

一般化すると

フィボナッチ数がたくさんでなかなか壮観ですね!

関連情報など

もともとは、Twitterでの　ゆう の 右腕　さんのこのツイートを見て、自分で解いてみようと思ったのが始まりでした。(ツイート内で言及されている資料はまだ見ていません。)

ゆう の 右腕　さんのツイート

「あの数列」とみてもしやと思ったのですが、やはりフィボナッチ数列が絡んできましたね!
また、この問題は　ゆう の 右腕　さんのブログ記事の演習問題にもなっています。ペル型方程式の解もこのブログから引用しています。

Arithmetica算術ノート:フィボナッチ数の判定式（1） 二次体の整数の整除と単数
Arithmetica算術ノート:フィボナッチ数の判定式（2） 二次体の整数の整除と単数
Arithmetica算術ノート:フィボナッチ数の判定式（3） 二次体の整数の整除と単数

それから、tsujimotter　さんのブログ記事に、今回の記事ででてきた「Singmasterの定理」と、パスカルの三角形に複数回出てくる数字とのとても面白い関係が紹介されています。

tsujimotterのノートブック:パスカルの三角形にたくさん出てくる数: 3003

この記事を見ると、パスカルの三角形に8回出てくる3003という数が特別であることがよくわかります!

おわりに

フィボナッチ数と二項定理には、ほかにもいろいろ面白い関係が隠れていそうです。

関連情報など何かあれば教えていただければ幸いです。