Math Mar∞m

自由気ままに,書いていきます。

Fibonacci 数列の加法定理と階段

※ 2021/4/11:参考文献の閲覧日を追記しました。

こんにちは。Math。です。

花粉症が中々治まってくれません。ツラいです…

さて,人生 2 回目となる記事のテーマは 「Fibonacci 数列の加法定理」です。数式入力の練習を兼ねて書いていこうと思います。

いくつかのサイトを見ていると,この定理は数学的帰納法で証明されるようです。なので,ここでは趣向を変えて,Fibonacci 数列と階段との関係を用いて証明してみます。

Fibonacci 数列

あまりにも有名な数列なので,ここで説明する必要もない気がしますが,今回は数式入力の練習も兼ねているので書いておきます。

Fibonacci 数列

Fibonacci 数列  \{F _ n\} とは,


        F_1 = F_2 = 1, \quad F_{n+2} = F_{n+1} + F_n

で定まる数列のことです。

よく知られたように,1, 1, 2, 3, 5, 8, 13, 21, … と続きます。

さて,この Fibonacci 数列は次のような性質をもっています。

性質

 n 段の階段を 1 段または 2 段ずつ上る方法は  F _ {n+1} 通り。

0 段の階段はないので, n\ge 1 とします。

証明

 n 段の階段の上り方の数を  a _ n とおきます。 a _ 1=1 a _ 2=2 です。また,便宜上, a _ 0=1 と定めておきます。

次に, n+2 段の階段を次の 2 通りに分けて数えます。

(i)初めの 1 歩を 1 段で上る場合

この場合,残り  n+1 段を上ればよいので,その上り方は  a _ {n+1} 通りあります。

(ii)初めの 1 歩を 2 段で上る場合

この場合,残り  n 段を上ればよいので,その上り方は  a _ n 通りあります。

(i)と(ii)より, n+2 段の階段の上り方について  a _ {n+2}=a _ {n+1}+a _ n が成り立ちます。この漸化式は,Fibonacci 数列が満たす漸化式  F _ {n+2}=F _ {n+1}+F _ n と同じ形をしています。しかも  a _ 0=F _ 1=1 a _ 1=F _ 2=1 ですから,より一般に, a _ n=F _ {n+1} が成り立ちます。

したがって, n 段の階段の上り方は  F_{n+1} 通りです。■

この性質についてはさまざまなサイトで証明されているので,分かりづらかった方はそちらも参照していただければと思います。

ここでは,この性質を「階段性質」とよぶことにします。

加法定理

三角関数の加法定理のように,Fibonacci 数列にも加法定理が成り立ちます。

Fibonacci 数列の加法定理

        F_{m+n} = F_m F_{n+1} + F_{m-1} F_n

ただし,添え字が 0 以下とならないように  m\ge 2 n\ge 1 としておきます。

では早速,階段性質を用いて証明してみます。

証明

 m+n-1 段の階段を考えます。階段性質より,この階段の上り方は  F_{m+n} 通りです。これを次の 2 通りに分けて数えます。

(i) m-1 段目を踏む場合

階段性質より, m-1 段目までの上り方は  F_m 通りです。そこからさらに  m+n-1 段目までは  n 段上ればよいので,その上り方は  F_{n+1} 通りです。よって, m-1 段目を踏む場合の上り方は全部で  F _ mF _ {n+1} 通りあります。

(ii) m-1 段目を踏まない場合

階段性質より, m-2 段目までの上り方は  F_{m-1} 通りです。そこから  1 歩で  2 段上り, m 段目に来ます。そこから  m+n-1 段目までは  n-1 段上ればよいので,その上り方は  F_n 通りです。よって, m-1 段目を踏まない場合の上り方は全部で  F _ {m-1}F _ n 通りあります。

(i)と(ii)より, F _ {m+n}=F _ mF _ {n+1}+F _ {m-1}F _ n が成り立ったので証明できたと思いきや,これだけでは不十分です。

なぜなら, m=2 n=1 の場合,(i)や(ii)の中に 0 段の階段が登場してしまうからです。

よって,それらの場合だけ別に証明しておきます。

 m=2 の場合,

 \begin{aligned}
        \textbf{定理の左辺} &= F_{2+n} = F_{n+1} + F_n\\
        \textbf{定理の右辺} &= F_2 F_{n+1} + F_1 F_n = F_{n+1} + F_n
    \end{aligned}

となり,定理が成り立ちます。同様に, n=1 の場合,

 \begin{aligned}
        \textbf{定理の左辺} &= F_{m+1} = F_m + F_{m-1}\\
        \textbf{定理の右辺} &= F_m F_2 + F_{m-1} F_1 = F_m + F_{m-1}
    \end{aligned}

となり,定理が成り立ちます。

以上で, m \ge 2 n \ge 1 に対して加法定理が成り立ちます。■

おわりに

それにしても Fibonacci 数列,本当に有名ですね。少し調べるだけでも山ほど関連サイトが出てきます。中には中学入試に関するものもあって驚きました。

それだけ記事が書かれる理由はやはり,単純な数列に見えて実は,自然界の至るところに現れたり,黄金比と関係していたりと,とにかく関連する話題が尽きないからでしょうか。

数式入力の良い練習にもなったので,今回はこのあたりで失礼します。

参考文献