この記事は 日曜数学 Advent Calendar 2022 の 5 日目の記事です。
数学好きであればフィボナッチ数という言葉を一度は聞いたことがあると思います。$1,1$から始めて、前の 2 つの数を足すという操作を繰り返すことで得られる数列をフィボナッチ数列といいます。つまり$1,1,2,3,5,8,13,21,34,55,89,\ldots$という数列です。式で書くと
$$ F_1=1, F_2=1, F_{n+2}=F_{n+1}+F_n $$
です。
フィボナッチ数列の面白い性質はたくさんありますが、その中でパスカルの三角形との関連を紹介します。パスカルの三角形は$(a+b)^n$を展開したときの係数を並べて得られる数の三角形です。この三角形で斜めに並ぶ数を足すとフィボナッチ数が現れるという性質があります。
1 | 1 | 2 | 3 | 5 | |
---|---|---|---|---|---|
1 | |||||
1 | 1 | ||||
1 | 2 | 1 | |||
1 | 3 | 3 | 1 | ||
1 | 4 | 6 | 4 | 1 | |
1 | 5 | 10 | 10 | 5 | 1 |
一番上の行が斜めに並んだ数を足した結果です。数式で書くと
$$ F_{n+1}=\sum_{i=0}^{\lfloor n/2\rfloor}\binom{n-i}{i} $$
となります (ただし$\binom{n}{k}$は二項係数)。この式は次の問題を考えることで得られます。
$n$段の階段がある。この階段を 1 段上るか、2 段上るか、という 2 通りの方法を組み合わせて上るとき、階段の上り方は何通りあるか。
漸化式を作るとフィボナッチ数と同じ式になるので、左辺が得られます。右辺は 2 段上りを何回行うかで場合分けすると得られます。
さて、フィボナッチ数列の兄弟ともいえる、リュカ数列という数列があります。これは$L_1=1,L_2=3,L_{n+2}=L_{n+1}+L_n$で定義される数列です。最初が$1,3$で、あとはフィボナッチ数列と同じように前の 2 つを足していくことで得られます。$1,3,4,7,11,18,29,\ldots$という数列です。
パスカルの三角形を斜めに足すとフィボナッチ数列になりましたが、斜めに足すとリュカ数列になるような三角形はあるでしょうか?
パスカルの三角形は$(a+b)^n$の係数を並べたものでしたが、$(a+b)^{n-1}(a+2b)$の係数を並べると条件を満たす三角形を考えてみましょう。
1 | 3 | 4 | 7 | 11 | 18 | |
---|---|---|---|---|---|---|
1 | 2 | |||||
1 | 3 | 2 | ||||
1 | 4 | 5 | 2 | |||
1 | 5 | 9 | 7 | 2 | ||
1 | 6 | 14 | 16 | 9 | 2 | |
1 | 7 | 20 | 30 | 25 | 11 | 2 |
斜めに足すとリュカ数列になっています。
$(a+b)^{n-1}(a+2b)$を展開したときの$a^{n-k}b^k$の係数は
$$ \binom{n-1}{k}+2\binom{n-1}{k-1}=\binom{n}{k}+\binom{n-1}{k-1} $$
です。斜めに足すとリュカ数になるということを数式で表すと
$$ L_n=\sum_{i=0}^{\lfloor n/2\rfloor}\left(\binom{n-i}{i}+\binom{n-i-1}{i-1}\right) $$
となります。ところでパスカルの三角形で斜めに足すとフィボナッチ数になるので、この式は
$$ L_n=F_{n+1}+F_{n-1} $$
となります。逆にこの式を既知とすれば、上の三角形で斜めに足すとリュカ数になることがわかります。
改めてこの三角形を見てみましょう。
1 | 3 | 4 | 7 | 11 | 18 | |
---|---|---|---|---|---|---|
1 | 2 | |||||
1 | 3 | 2 | ||||
1 | 4 | 5 | 2 | |||
1 | 5 | 9 | 7 | 2 | ||
1 | 6 | 14 | 16 | 9 | 2 | |
1 | 7 | 20 | 30 | 25 | 11 | 2 |
パスカルの三角形と違って、この三角形は左右対称ではありません。では左右反転するとどうなるでしょうか?
2 | 3 | 5 | 8 | 13 | 21 | |
---|---|---|---|---|---|---|
2 | 1 | |||||
2 | 3 | 1 | ||||
2 | 5 | 4 | 1 | |||
2 | 7 | 9 | 5 | 1 | ||
2 | 9 | 16 | 14 | 6 | 1 | |
2 | 11 | 25 | 30 | 20 | 7 | 1 |
なんと、フィボナッチ数列になるのです!まさにフィボナッチ数とリュカ数が兄弟であるということを感じさせますね。
少し一般化をします。$(a+b)^{n-1}(pa+qb)$の係数を並べた三角形において斜めに足して得られる数列を$S_n$とすると、$S_1=p, S_2=p+q, S_{n+2}=S_{n+1}+S_n$をみたします。左右反転するということは$a,b$を入れ替えるということなので、$(a+b)^{n-1}(qa+pb)$の係数を並べた三角形となります。斜めに足して得られる数列を$T_n$とすると、$T_1=q,T_2=p+q,T_{n+2}=T_{n+1}+T_n$となります。
今回登場した数列はすべてフィボナッチ数列と同じ$F_{n+2}=F_{n+1}+F_n$をみたす数列でした。他の漸化式を生み出す三角形はあるでしょうか?また斜め以外の方法で足すとどうなるでしょうか?面白そうな問題が色々あります。ぜひ皆さんも考えてみてください!