パスカルの三角形にフィボナッチ数列が潜んでいる理由を複雑に説明

パスカルの三角形を斜めに見る

パスカルの三角形にフィボナッチ数列が潜んでいるのは有名(?)です.実際,下の表の斜めの部分(同じ色のセル)の和を計算すると,順に
$$1, 1, 2, 3, 5, 8, 13, 21, 34$$
が出てきます.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84  126  126 84 36 9 1

この性質は二項係数の
$$\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}$$
を部分的に使いまくることで,フィボナッチ数列の漸化式が見えてくるので,野暮ったい方法で説明ができるのですが,今回はあえて高級(?)な概念で説明してみます.ひとまずパスカルの三角形を二項係数で再表示してみます.

\(\binom{0}{0}\)
\(\binom{1}{0}\) \(\binom{1}{1}\)
\(\binom{2}{0}\) \(\binom{2}{1}\) \(\binom{2}{2}\)
\(\binom{3}{0}\) \(\binom{3}{1}\) \(\binom{3}{2}\) \(\binom{3}{3}\)
\(\binom{4}{0}\) \(\binom{4}{1}\) \(\binom{4}{2}\) \(\binom{4}{3}\) \(\binom{4}{4}\)
\(\binom{5}{0}\) \(\binom{5}{1}\) \(\binom{5}{2}\) \(\binom{5}{3}\) \(\binom{5}{4}\) \(\binom{5}{5}\)
\(\binom{6}{0}\) \(\binom{6}{1}\) \(\binom{6}{2}\) \(\binom{6}{3}\) \(\binom{6}{4}\) \(\binom{6}{5}\) \(\binom{6}{6}\)
\(\binom{7}{0}\) \(\binom{7}{1}\) \(\binom{7}{2}\) \(\binom{7}{3}\) \(\binom{7}{4}\) \(\binom{7}{5}\) \(\binom{7}{6}\) \(\binom{7}{7}\)
\(\binom{8}{0}\) \(\binom{8}{1}\) \(\binom{8}{2}\) \(\binom{8}{3}\) \(\binom{8}{4}\) \(\binom{8}{5}\) \(\binom{8}{6}\) \(\binom{8}{7}\) \(\binom{8}{8}\)
\(\binom{9}{0}\) \(\binom{9}{1}\) \(\binom{9}{2}\) \(\binom{9}{3}\) \(\binom{9}{4}\) \(\binom{9}{5}\) \(\binom{9}{4}\) \(\binom{9}{3}\) \(\binom{9}{2}\) \(\binom{9}{1}\)

フィボナッチ数列の一般項を \(F_n\) で表すと,
$$\begin{align}
F_1 &= \binom{0}{0}\\
F_2 &= \binom{1}{0}\\
F_3 &= \binom{2}{0}+\binom{1}{1}\\
F_4 &= \binom{3}{0}+\binom{2}{1}\\
F_5 &= \binom{4}{0}+\binom{3}{1}+\binom{2}{2}\\
F_6 &= \binom{5}{0}+\binom{4}{1}+\binom{3}{2}\\
F_7 &= \binom{6}{0} + \binom{5}{1} + \binom{4}{2} + \binom{3}{3}\\
F_8 &= \binom{7}{0}+\binom{6}{1}+\binom{5}{2}+\binom{4}{3}\\
F_9 &= \binom{8}{0}+\binom{7}{1}+\binom{6}{2}+\binom{5}{3}+\binom{4}{4}\\
F_{10} &= \binom{9}{0} + \binom{8}{1} + \binom{7}{2} + \binom{6}{3} +\binom{5}{4}
\end{align}$$
と表せます.例えば, \(F_7\) を \(\sum\) で表してみると
$$\begin{align}
F_7 = \sum_{k=0}^{3}\binom{6-k}{k} = \sum_{k=0}^{\lfloor6/3\rfloor}\binom{6-k}{k}
\end{align}$$
となります.この 表示を見て「あれ?」と思った人はかなりの上級者でしょう.\(F_8\) も見てみると
$$\begin{align}
F_8 = \sum_{k=0}^{3}\binom{7-k}{k}= \sum_{k=0}^{\lfloor 7/2\rfloor}\binom{7-k}{k}
\end{align}$$
となります.このことから次の公式が予測されます.

フィボナッチ数列の一般項

$$
F_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}\quad(n\geqq 0)
$$

この公式こそが,パスカルの三角形を斜めに見るとフィボナッチ数列が浮き上がってくる理由の説明になります.ここで
$$\binom{n-k}{k}$$
という二項係数は,\(\cos n\theta\) の表示で紹介した, \(a^n+b^n\) を基本対称式で表すときに用いた形式的冪級数を求める際に似たような式が出てきたのを思い出してください.

余談ですが,上の公式は
$$
F_{n} = \sum_{k=0}^{\lfloor (n-1)/2\rfloor}\binom{n-k-1}{k}\quad(n\geqq1)
$$
としてもよいのですが,少し式が複雑に見えるので,あえて \(F_{n+1}\) にしています.

漸化式に着目

\(L_n = a^n+b^n\) のとき
$$\begin{align}
(a+b)(a^{n+1}+b^{n+1})
&= a^{n+2} + a b^{n+1} + a^{n+1}b + b^{n+2}\\
&= a^{n+2} + b^{n+2} + a b (a^n+b^n)
\end{align}$$
より
$$
(a+b)L_{n+1} = L_{n+2} + a b L_{n}
$$
すなわち
$$
L_{n+2} = (a+b)L_{n+1} – a b L_{n}
$$
が成り立ちます.ここで,
$$
a+b = 1,\quad ab = -1
$$
となるように \(a, b\) を選べば, \(L_n\) はフィボナッチ数列と同じ漸化式を満たす数列になります.しかし,
$$\begin{align}
L_0 &= a^0+b^0 = 2\\
L_1 &= a^1+b^1 = 1\\
\end{align}$$
ですから,フィボナッチ数列とは初期値の異なる数列です.歴史的に \(\{L_n\}\) はリュカ数列とよばれており,\(n\geqq1\) のとき
$$\begin{align}
L_n&=a^n+b^n\\
&= \sum_{k=0}^{\lfloor n/2 \rfloor}(-1)^k\frac{n}{n-k}\binom{n-k}{k}(a+b)^{n-2k}(ab)^{k}\\
&= \sum_{k=0}^{\lfloor n/2 \rfloor}(-1)^k\frac{n}{n-k}\binom{n-k}{k}(1)^{n-2k}(-1)^{k}\\
&= \sum_{k=0}^{\lfloor n/2 \rfloor}\frac{n}{n-k}\binom{n-k}{k}
\end{align}$$
が成り立ちます.これと同じ趣向でフィボナッチ数列を和の形で表してみればパスカルの三角形の謎が説明できます.

仮に \(F_n=\lambda a^n + \mu b^n\) とします.
$$\begin{align}
(a+b)(\lambda a^{n+1}+\mu b^{n+1})
&= \lambda a^{n+2} + \mu a b^{n+1} + \lambda a^{n+1}b + \mu b^{n+2}\\
&= \lambda a^{n+2} + \mu b^{n+2} + a b (\lambda a^n+\mu b^n)
\end{align}$$
より,リュカ数列のときと同様に
$$
(a+b)F_{n+1} = F_{n+2} + a b F_{n}
$$
すなわち
$$
F_{n+2} = (a+b)F_{n+1} – a b F_n
$$
が成り立ちます.フィボナッチ数列の漸化式を成立させるために
$$
a+b=1,\quad a b = -1
$$
および
$$
F_0 = 0,\quad F_1 = 1
$$
となるように \(\lambda, \mu\) を決定するのです.解と係数の関係より,\(a, b\) は
$$ x^2 – x – 1 = 0$$
の解であり,\(a > b\) を仮定しても一般性は失わないので,
$$ a = \frac{1+\sqrt{5}}{2},\quad b=\frac{1-\sqrt{5}}{2}$$
となります.また,
$$\begin{align}
F_0 &= \lambda a^0 + \mu b^0 = \lambda + \mu\\
F_1 &= \lambda a^1 + \mu b^1 = \lambda a + \mu b
\end{align}$$
ですから
$$F_0 = 0 \Longleftrightarrow \lambda + \mu = 0 \Longleftrightarrow\mu = -\lambda$$
より
$$F_1 = 1 \Longleftrightarrow \lambda a – \lambda b = 1 \Longleftrightarrow \lambda(a-b)=1$$
となるので,
$$\begin{align}
\lambda &= \frac{1}{a-b}
=\frac{1}{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}} = \frac{1}{\sqrt{5}}\\
\mu &= -\lambda = -\frac{1}{\sqrt{5}}
\end{align}$$
です.以上を総括すると
$$
F_n = \frac{1}{\sqrt{5}}(a^n-b^n)
$$
を得るわけです. \(a^n-b^n\) だったら基本対称式で表せますが,今回は交代式になっています.ここで応用力を働かせましょう.\(\cos n\theta\) の証明法のアイディアを用います.

フィボナッチ数列の母関数

\(F_n\) の母関数を \(\varphi(x)\) とします.
$$
\begin{align}
\varphi(x)
&=\sum_{n=0}^{\infty} F_n x^n\\
&=\frac{1}{\sqrt{5}}\sum_{n=0}^\infty(a^n-b^n)x^n\\
&=\frac{1}{\sqrt{5}}\left(\sum_{n=0}^\infty a^n x^n-\sum_{n=0}^\infty b^n x^n\right)\\
&=\frac{1}{\sqrt{5}}\left(\frac{1}{1-a x}+\frac{1}{1- b x}\right)\\
&=\frac{1}{\sqrt{5}}\frac{1-bx – (1 – ax)}{(1-a x)(1- b x)}\\
&=\frac{1}{\sqrt{5}}\frac{(a-b)x}{1-(a+b)x+a b x^2}
\end{align}
$$
確認ですが, \(a+b = 1,\quad a b = -1,\quad a-b = \sqrt{5}\) でしたので
$$
\varphi(x) = \frac{x}{1-x-x^2}
$$
となります. \(\cos n\theta\) の導出で示しましたが
$$\frac{1}{1-\sigma_1 x + \sigma_2 x^2}$$
の冪級数展開の \(x^n\) の係数は
$$
\sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n-k}{k} \sigma_1^{n-2k}(-\sigma_2)^{k}
$$
だったので, \(\sigma_1 = 1,\ \sigma_2=-1\) としたものが
$$
\frac{1}{1-x-x^2}
$$
の \(x^n\) の係数になります.すなわち,
$$
\frac{1}{1-x-x^2} = \sum_{n=0}^\infty c_n x^n
$$
と置くとき,
$$
c_n=\sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n-k}{k}
$$
となります.よって
$$\begin{align}
\varphi(x)
&= \frac{x}{1-x-x^2}
= x\frac{1}{1-x-x^2}\\
&=x\sum_{n=0}^\infty c_n x^n
=\sum_{n=0}^\infty c_n x^{n+1}
\end{align}$$
が帰結されます. \(\varphi(x)\) は \(F_n\) の母関数ですから \(x^{n+1}\) の係数が \(F_{n+1}\) です.すなわち
$$
F_{n+1} = \sum_{k=0}^{\lfloor {n/2} \rfloor}\binom{n-k}{k}
$$
が成り立ちます.

パスカルの三角形にフィボナッチ数列が潜んでいる理由を複雑に説明” に2件のコメントがあります

  1. aは1より大きいため、無限等比級数が成り立たないと思うのですが、どうして成り立つのでしょうか?

    • \(\sum_{n=0}^\infty a^n x^n = \frac{1}{1-a x}\) の部分のことをおっしゃっているのでしょうか.母関数という用語を記事内で使っていますが,数列 \(F_n\) に対する母関数 \(\sum_{n=0}^\infty F_n x^n\) は形式的冪級数と呼ばれるもので,収束するかどうかを考えません.この \(x\) も具体的な数ではなく不定元と呼ばれる形式的な存在なのです.これを無限等比級数と考えるならば,\(a x\) の絶対値が 1 より小さかを考えなければなりませんが,実際は,\(x\) は数ではないので,\(a x\) も数ではないことになり,絶対値も考えません.だから最初から \(\sum_{n=0}^\infty a^n x^n\) が収束するしないの議論自体がナンセンスになります.

      さて,収束を考えなくていいなどと言われると,胡散臭い香りしかしませんが,大学の数学につかってくると定義さえちゃんとしていればそんなに気にならなくなります(形式的冪級数のちゃんとした定義も自然に受け入れることが可能になります).簡単に説明しますと,\((a_n)\) を数列とするとき
      \begin{align*}
      a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n + \cdots
      \end{align*}
      の形の式を形式的冪級数といって,\(\sum_{n=0}^\infty a_n x^n\) とも表します.2つの形式的冪級数 \(\sum_{n=0}^\infty a_n x^n, \sum_{n=0}^\infty b_n x^n\) に対して和と積をそれぞれ
      \begin{align*}
      &\sum_{n=0}^\infty(a_n + b_n)x^n\\
      &\sum_{n=0}^\infty c_n x^n\ (ただし\ c_n=\sum_{k=0}^n a_{n-k}b_k)
      \end{align*}
      と定義すると,形式的冪級数の全体の集合が加減乗法について閉じている環であることが分かります.この積の定義に従うと
      \begin{align*}
      P(x) = 1 + a x + a^2 x^2 + a^3 x^3 + \cdots
      \end{align*}
      に対して \( P(x) (1 – a x) =1\) が成り立ちます.つまり,\(1 – a x\) は \(P(x)\) の逆元(逆数)になるので,
      \begin{align*}
      P(x) = \frac{1}{1- a x}
      \end{align*}
      という記法が認められるのです.

      キーワードは形式的冪級数です.Wikipediaにも記事がありますが,もし他に質問があったらなんなりと.

コメントする