頭脳王優勝者である河野玄斗（げんげん）氏が、2018年3月21日にtwitter上で数学の問題を投稿していた。 それは以下の数式を求める問題である。
$$\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\frac{{}_{n-k}C_{k}}{n^k}$$
こんな問題である。この問題を見たとき、五時間以上奮闘してなんとか解いたのだが、やはり難しい問題だった。 彼はこの問題について忙しいからかは知らないが何も解説を書いていなかったので、暇な大学生である自分が解説を書こうと思った次第である。
答えっぽいものは出たけど議論をもっと厳密にするべき部分がたくさんある上にまったく高校数学的な解法ではないというやつ pic.twitter.com/9JnT0GPWO1
— しゃかやみ (@shakayami_) 2018年3月21日
これに尽きる。ただこのまま記事を終えるだけでは味気ないのでどのように考えてこの解答に至ったかを示そうと思う。
求めるべき数式は $$\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor}\frac{{}_{n-k}C_{k}}{n^k}$$ である。このままいきなり求めようとすると死ぬので、式をある程度簡単な形にした場合にどのようになるかを考える。 簡単にすると言っても、いろいろある。たとえば${}_{n-k}C_{k}$を${}_{n}C_{k}$とか、$n-{}_{k}C_{k}$に変換するとかである。（特に2番目はネタだが…間違えて解釈している人も多かったので書いた次第） まあとにかく、なぜシグマの足す範囲が$\lfloor \frac{n}{2}\rfloor$なのかを考えると、二項係数がうまく定義できる範囲が$n-k\geq k,n-k\geq 0$より$0\leq k\leq \lfloor \frac{n}{2}\rfloor$となくてはいけないということになる。 逆に言えばあまり形を崩さないためには、シグマの足す範囲と二項係数の形${}_{n-k}C_{k}$は一定に保っていないといけないだろう。
つまり問題の意図を崩さないまま易化させるにはたとえば次のように変換すればいいだろう。 $$\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor}{}_{n-k}C_k$$ となる。これがどのような形になるのかは一瞬ではわからなかったので、実際に実験して$n$が小さい場合の値を求めてみると以下の表のようになる。
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| $\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor}{}_{n-k}C_{k}$ | 1 | 2 | 3 | 5 | 8 | 13 | 21 |
フィボナッチであることを示すためにはいろいろな方法があるが、（げんげん氏は漸化式でやったのかと思われる） 今回は母関数でやる方法を考えた。「フィボナッチ数列 二項係数 母関数」とググったらすぐに詳細が出てくるので、大体の流れだけ書くと、 $$f(x)=\sum_{n=0}^{\infty}\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor}{}_{n-k}C_{k}x^n$$ という関数の正体をわかればいいということである。母関数が一致しているならばもとの数列も一致している。（注：級数が収束するくらいに十分に$|x|$は小さいものとする。） シグマの足す順番を以下のように変える。それは
| x | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 0 | 2 | 4 | 6 | 8 | 10 |
| 1 | 1 | 3 | 5 | 7 | 9 | 11 |
| 2 | 2 | 4 | 6 | 8 | 10 | 12 |
| 3 | 3 | 5 | 7 | 9 | 11 | 13 |
| 4 | 4 | 6 | 8 | 10 | 12 | 14 |
| 5 | 5 | 7 | 9 | 11 | 13 | 15 |
から
| x | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 0 | 1 | 2 | 3 | >4 | 5 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 2 | 3 | 4 | 5 | 6 | 7 |
| 3 | 3 | 4 | 5 | 6 | 7 | 8 |
| 4 | 4 | 5 | 6 | 7 | 8 | 9 |
| 5 | 5 | 6 | 7 | 8 | 9 | 10 |
というように変換する。すると元の式は $$\sum_{n=0}^{\infty}\sum_{k=0}^{n}{}_{n}C_{k}x^{n+l}$$ $$=\sum_{n=0}^{\infty}(1+x)^nx^n$$ $$=\sum_{n=0}^{\infty}(x^2+x)^n$$ $$=\frac{1}{1-x-x^2}$$ このとき、$x^2+x-1=0$の解を$\alpha,\beta$とおくと、$\alpha+\beta=-1,\alpha\beta=-1$となり、 $$=\frac{1}{\alpha-\beta}\left(\frac{1}{\alpha -x}-\frac{1}{\beta -x}\right)$$ $$=\frac{1}{\alpha-\beta}\left(\frac{1}{\alpha}\frac{1}{1-\frac{x}{\alpha}}-\frac{1}{\beta}\frac{1}{1-\frac{x}{\beta}}\right)$$ $$=\frac{1}{\alpha-\beta}\sum_{n=0}^{\infty}\left(\alpha^{-n-1}x^{n}-\beta^{-n-1}x^n\right)$$ $$=\frac{1}{\alpha-\beta}\sum_{n=0}^{\infty}(-1)^{n+1}\left(\beta^{n+1}-\alpha^{n+1}\right)x^n$$ ここで、$\alpha=\frac{-1+\sqrt{5}}{2},\beta=\frac{-1-\sqrt{5}}{2}$であるから、 $$=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)x^n$$ $$=\sum_{n=0}^{\infty}F_{n+1}x^n$$ というようになる。
さて、この式をもとの問題に応用すると、壁にぶち当たる。というのもこれと同じ変換をやってしまうと、 $$\sum_{n=0}^{\infty}\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor}\frac{{}_{n-k}C_{k}}{n^k}x^n=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\frac{{}_{n}C_{k}}{(n+k)^k}x^{n+k}$$ となり、二項定理を使うことができない。$(n+k)^k$の変数の中身が$n+k$と$k$に依存しているためそれだけで解くことができなくなる。
そこで小さな発想の転換が必要になる。依存を打ち消すには分母の依存性をうまく対処しなければいけない。そこで自分がやったことはあえて独立変数を増やそうとしたということである。 $$g_{m,n}=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\frac{{}_{n-k}C_{k}}{m^k}$$ とおいて、 $$f_m(x)=\sum_{n=0}^{\infty}\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor}g_{m,n}x^n=\sum_{n=0}^{\infty}\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor}\frac{{}_{n-k}C_{k}}{m^k}x^n$$ としたうえで$g_{m,n}$を求めて、その上で$g_{n,n}$を求めればいいということである。 実際このように変更した場合二項定理を使うことができる。 $$=f_m(x)=\sum_{n=0}^{\infty}\sum_{k=0}^{\infty}\frac{{}_{n}C_{k}}{m^k}x^{n+k}$$ $$=\sum_{n=0}^{\infty}\left(1+\frac{x}{m}\right)^nx^n$$ $$=\sum_{n=0}^{\infty}\left(x+\frac{x^2}{m}\right)^n$$ $$=\frac{1}{1-x-\frac{x^2}{m}}$$ $$=\frac{m}{m-mx-x^2}$$ よって分母を因数分解してというように（さっきやったのと同じ方法で）式を処理していくと、 $$g_{m,n}=\frac{1}{\sqrt{1+\frac{4}{m}}}\left(\left(\frac{1+\sqrt{1+\frac{4}{m}}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{1+\frac{4}{m}}}{2}\right)^{n+1}\right)$$ というようになるので、与式は $$g_{n,n}=\frac{1}{\sqrt{1+\frac{4}{n}}}\left(\left(\frac{1+\sqrt{1+\frac{4}{n}}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{1+\frac{4}{n}}}{2}\right)^{n+1}\right)$$ というようになる。
フィボナッチっぽいことには結構早い段階で気づいたが、そこから実際に解くにはかなり時間がかかったので方針を思いついても実行に時間がかかる難問である。（もちろんこんな問題を入試に出されたら死ぬ） まあとにかく、数学でよくわからなくなったときの対処法ラキング上位に入っている「単純な場合を考える」と、「小さな値を代入して挙動を観察する」ということを守ればフィボナッチと関連があることを見抜くのはそう難しくはない。 そして変数を増やして複雑化しないと解けない問題という具体例を初めてみた気がする。