二項係数にからんだ数列の極限を考えようとしたら闇が深かった話(前編)

突然ですが、みなさん二項係数は好きですか? 僕は普通です。

最近、友人と二項係数についての問題を考えていたので、その顛末を簡単に書いてみようかなと思います。

梅雨がやっと明けたばかりの7月のことでした。所属しているサークルの集まりに久しぶりに顔を出したら、数学好きの友人がノートPCを抱えて僕のところに近づいてきます。話を聞いてみると、最近とある数列のことを考えていて夜も眠れないらしい(大意)。その日は偶然にも暇だったので、ちょっと面白そうかもしれないと思って一緒に考えてみることにしました。

とある数列

その数列というのは次のようなものです。

$$ 1, 1, 6, 54, 680, 11000, 217392, 5076400, 136761984, \cdots $$

いきなり何桁もの数字の羅列を見せられて「は?」という感じですが、これは第n項が

$$ \displaystyle{\sum_{k=0}^n {}_n{\rm C}_k k^n} $$

で与えられる数列です。え?なんでこんな数列を考えようと思ったかって? そんなの知りません。彼に聞いてください。

とにかく、こういう和の形で表された数列があったとき、まずは一般項を和の記号を使わないで表してみたくなりますよね。 そうはいっても、シグマ記号の中に二項係数${}_n{\rm C}_k$が入っているので、一筋縄では表せそうにありません。

シグマ記号の中がもっと簡単な式だったら、一般項をシグマ記号を使わないで表すことができることもあります。例えば

$$ \displaystyle{\sum_{k=0}^n {}_n{\rm C}_k}=2^n $$

という式が有名です。証明もそんなに難しくはありません。 2^n=(1+1)^nを二項定理で展開すれば

$$ 2^n=(1+1)^n=\sum_{k=0}^n {}_n{\rm C}_k 1^k1^{n-k}=\sum_{k=0}^n {}_n{\rm C}_k $$

となりますから上式が得られます。ちなみにこの式に$n=0$を代入するとさっきの数列の初項になったりします(よく考えたらそれはそう)。

実は、この式をもとにすると二項係数の入った和の式を大量に生産することができます。突然ですが、$(1+x)^n$という多項式を二項定理を使って展開すると

$$ (1+x)^n=\sum_{k=0}^n {}_n{\rm C}_k x^k $$

となります(さっき登場した式は、この式に$x=1$を代入すると得られる式ですね)。

ここからどうやって新しい式を得るかというと、両辺を$x$で微分するんです。 すると、右辺についてはシグマ記号の各項を微分すればいいので

$$ n(1+x)^{n-1}=\sum_{k=0}^n {}_n{\rm C}_k {kx}^{k - 1} $$

となります。これに$x=1$を代入すれば

$$ n\cdot 2^{n-1}=\sum_{k=0}^n {}_n{\rm C}_k k $$

という式のできあがり。もう気づいている人もいるかもしれませんがこの式に$n=1$を代入したものは、例の数列の第1項(2番目の項)そのものです。

今やった計算は何回も繰り返すことができます。ただし注意が必要で、さっきの式の両辺を何も考えず$x$で微分してしまうとシグマの中身が$k(k - 1)$となってしまうので、先に両辺に$x$を掛けて

$$ nx(1+x)^{n-1}=\sum_{k=0}^n {}_n{\rm C}_k {kx}^{k} $$

としてから$x$で微分します。

$$ n(1+x)^{n-1}+n(n-1)x(1+x)^{n-2}=\sum_{k=0}^n {}_n{\rm C}_k {k^2x}^{k - 1} $$

はい微分しました(ちょっと大変だけど)。これに$x=1$を代入すると

$$ n(n+1)\cdot 2^{n-2}=\sum_{k=0}^n {}_n{\rm C}_k {k^2} $$

が得られます。慧眼な読者はもう気づいているでしょうが$n=2$を代入すると

$$ \sum_{k=0}^2 {}_2{\rm C}_k {k^2}=2\cdot 3=6 $$

ですがこれはさっきの数列の第2項になっています。

先ほども言ったように、この計算は何回でも繰り返すことができます。とはいえ微分の計算がちょっと大変です。$nx(1+x)^{n-1}+n(n-1)x^2(1+x)^{n-2}$なんて見るからに微分したくないですよね。こういう時はWolframAlphaくんに助けてもらうのがいちばんです。

というわけで今の計算を繰り返すと

$$ \sum_{k=0}^n {}_n{\rm C}_k {k^3}=n(n^2+3n)\cdot 2^{n-3} $$

$$ \sum_{k=0}^n {}_n{\rm C}_k {k^4}=n(n^3+6n^2+3n - 2)\cdot 2^{n-4} $$

$$ \sum_{k=0}^n {}_n{\rm C}_k {k^5}=n(n^4+10n^3+15n^2 - 10n)\cdot 2^{n-5} $$

わあすごいですね。繰り返しますが、この式にそれぞれ$n=3, 4, 5$を代入すると例の数列の第3項、第4項、第5項になります。

ここまで偉そうに説明してきましたが、この導出は全部友人が考えたものです。僕が「え〜何これすごい!」と言うと彼は「これくらい普通の人間なら考えつくでしょ」とか言ってイキってきました。ちょっと何言ってるかわかんないですね。

そういえば一般項を求めようとしていた

ここまでの話を整理しておきましょう。何をしていたかというと、

$$ 1, 1, 6, 54, 680, 11000, 217392, 5076400, 136761984, \cdots $$

という例の数列の一般項を、シグマ記号を使わない形で求めようとしていたんでした。とはいえ、それを求めるのはかなり難しそうです。さっき分かったのは、「この数列の第$n$項を知りたかったら、

$$ \sum_{k=0}^n {}_n{\rm C}_k k=n\cdot 2^{n-1} $$

$$ \sum_{k=0}^n {}_n{\rm C}_k {k^2}=n(n+1)\cdot 2^{n-2} $$

$$ \sum_{k=0}^n {}_n{\rm C}_k {k^3}=n(n^2+3n)\cdot 2^{n-3} $$

$$ \sum_{k=0}^n {}_n{\rm C}_k {k^4}=n(n^3+6n^2+3n - 2)\cdot 2^{n-4} $$

$$ \sum_{k=0}^n {}_n{\rm C}_k {k^5}=n(n^4+10n^3+15n^2 - 10n)\cdot 2^{n-5} $$

という式の$n$番目に$n$を代入しなさいね」ということであって、数列の一般項がひとつの式で表されたわけではありません。

いやー、困った困った。でもなんとかしてこの数列のことをもっとよく知りたいですよね。もう一度、数の並びを見てみましょう。

$$ 1, 1, 6, 54, 680, 11000, 217392, 5076400, 136761984, \cdots $$

改めて見てやると、数がものすごい勢いで増えていっています。第4項までは$1,1,6,54,680$と地に足がついている感じなのに(0番目から数えています)、第5項でいきなり$11000$ですからね。いきなりどうした?って感じです。

こんなに増加するスピードが速いと、ほかの数列と増え方を比べたくなってきます。

増加するのがとても速い数列の代表といえば、階乗$n!$があります。さっきの数列と同じ項数だけ取り出すとどうなるのか見てみましょう。

$$ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, \cdots $$

この数列の第8項、すなわち$8!$が$40320$であるのに対し、例の数列の第8項は$136761984$ですから、4桁も違うことが分かります。でも、単に両者を比べてみてもちょっと分かりにくいですね。

そんなときには、2つの数列の比をとってみると分かりやすいです。つまり、$a_n=\displaystyle{\sum_{k=0}^n {}_n{\rm C}_k k^n},\; b_n=n!$として、$a_n/b_n$の値を調べるわけです。こうすれば、例の数列が階乗の何倍なのかがわかります。 $n$を大きくしていったとき、比の値が$1$に近づけば、両者の増え方は同程度だと見なすことができます。また、比の値が限りなく大きくなるのなら、例の数列の増加スピードが階乗よりも桁違いに大きいことがわかりますし、比の値が$0$に近づくなら、階乗の増加スピードのほうが速いことが分かりますね*1。やってみましょう。

$$ 1,1,3,9, 28, 92, 302, 1007, 3392, \cdots $$

このようになりました(※値は四捨五入して整数にしています)。見るからに、比の値は増加し続けていますね。これは、例の数列の増加スピードが階乗よりも速いことを意味しています。まあ両者を見比べた時点でそんな感じはしていました。

同じスピードで増える数列を探せ

さて、例の数列が階乗を超えるスピードで増加することがわかりました。ここまでくると、例の数列の増加スピードが正確にどれくらいなのか知りたくなってきます。 でも、未知の数列が増加するスピードなんてどうやって求めるのでしょう? それは、「我々のよく知っている数列で、例の数列と同程度のスピードで増加するものを見つければいい」んです。仮にですよ、$c_n$という具体的な数列があって、$c_n$の増加スピードが例の数列と同じなら、例の数列の増加スピードが分かるわけです。そのような$c_n$を見つけることを、数学では「数列の漸近挙動を調べる」とか言ったりします。そして、$c_n$を見つけるには、例の数列との比をとって、$n$を大きくしたときに$1$になるものを探せばいい。話だけなら単純です。

でもその$c_n$ってどうやって見つければよいのでしょう? とりあえず、例の数列が階乗よりも増加スピードが速いことだけは分かったので、少なくとも$c_n$は階乗よりも速く増加する人々の中から探せばよいでしょう。それでも、階乗よりも速く増加する数列なんて無数にあります。

ここで、前に導出した式に戻りましょう。これです。

$$ \sum_{k=0}^n {}_n{\rm C}_k k=n\cdot 2^{n-1} $$

$$ \sum_{k=0}^n {}_n{\rm C}_k {k^2}=n(n+1)\cdot 2^{n-2} $$

$$ \sum_{k=0}^n {}_n{\rm C}_k {k^3}=n(n^2+3n)\cdot 2^{n-3} $$

$$ \sum_{k=0}^n {}_n{\rm C}_k {k^4}=n(n^3+6n^2+3n - 2)\cdot 2^{n-4} $$

例の数列$a_n$の各項は、これらの式に、$n=1,2,3,\cdots$を順番に代入すれば出てくるのでした。代入してみましょう。

$$ a_1=\sum_{k=0}^1 {}_1{\rm C}_k k=1\cdot 2^{1-1}=1 $$

$$ a_2=\sum_{k=0}^2 {}_2{\rm C}_k {k^2}=2\cdot (2+1)\cdot 2^{2-2}=2^2+2=6 $$

$$ a_3=\sum_{k=0}^3 {}_3{\rm C}_k {k^3}=3\cdot (3^2+3\cdot 3)\cdot 2^{3-3}=3^3+3\cdot 3^2=54 $$

$$ a_4=\sum_{k=0}^4 {}_4{\rm C}_k {k^4}=4\cdot (4^3+6\cdot 4^2+3\cdot 4 - 2)\cdot 2^{4-4}=4^4+6\cdot 4^3+3\cdot 4^2-2\cdot 4=680 $$

よく見てください。$a_2$には$2^2$という項があります。次の$a_3$には、$3^3$という項があります。そして、$a_4$には$4^4$が登場しています。このままいくと、$a_n$には$n^n$という項が現れそうです*2

ということは、まず手始めに、$a_n$と同程度で増える数列$c_n$の候補として$n^n$をとってくればよさそうです*3。参考までに、$n^n$の各項を並べてみると

$$ 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489, \cdots $$

うん、さっきよりは期待できそう。さっそく比をとってみましょう。$a_n/c_n$を計算します。

$$ 1, 1, 1.5, 2, 2.7, 3.5, 4.7, 6.2, 8.2, \cdots $$

こんな感じになりました(※値は小数第2位を四捨五入しています)。うーん、どんどん増加していって、$1$にはならなそうです。 それでも、階乗のときと比べると、増加の仕方はだいぶ穏やかですね。比の値の変化の仕方にも秘密がありそうです。

こんなときはDesmosを使いましょう。Desmosは数学徒御用達の万能視覚化ツールで、座標平面上にさまざまなグラフを描くことができます。想像以上に高機能で、関数のグラフはもちろん、パラメータ表示された曲線を描いたり、点を動かしたりすることもできます。

f:id:hal2000_phy:20190823213941p:plain

これがDesmosの画面です。いまからここに点をプロットしていきましょう。まずは横軸を$n$、縦軸を例の数列$a_n$にとって、第$10$項まで表示させてみます。

f:id:hal2000_phy:20190823214241p:plain

はいできました。一瞬です。とはいえ、この数列はありえないほどのスピードで増えるので、縦軸の目盛りをありえないほど細かくしても最初の数項しか見えていません。

気を取り直して$n^n$もプロットしましょう。$n=0, 1, \cdots, 10$に対して点$(n, n^n)$を表示させます。

f:id:hal2000_phy:20190823214938p:plain

なんかおしいことはわかるけどよくわからん。そこで、両者の比の値をプロットしてみます。

f:id:hal2000_phy:20190823214940p:plain

わあ! なんか見たことのある曲線がでてきた! 僕知ってます、知ってますよ。これ指数関数ってやつでしょ。いや数列だから等比数列か。この紫の点列、何かの等比数列$ar^n$と重ねてみると$n$が大きいところではほとんどぴったり一致しそうじゃないですか。

紫の点が等比数列っぽい増え方をするなら、公比$r$があるはずです。

公比、知りたい…。知りたくない…?

僕は知りたいので、とりあえず

$$ 1, 1, 1.5, 2, 2.7, 3.5, 4.7, 6.2, 8.2, \cdots $$

の隣同士の比をとって見ましょう。それが近づいていく先が求めたい公比$r$です。

$n$ $a_n$ $n^n$ $r_n=a_n/n^n$ $r_n/r_{n-1}$
0 1 1 1.00000
1 1 1 1.00000 1.00000
2 6 4 1.50000 1.50000
3 54 27 2.00000 1.33333
4 680 256 2.65625 1.32812
5 11000 3125 3.52000 1.32517
6 217392 46656 4.65946 1.32371
7 5076400 823543 6.16409 1.32291
8 136761984 16777216 8.15164 1.32243
9 4175432064 387420489 10.77751 1.32212

いちばん右の列に注目してください。なんかめっちゃ$1.32\cdots$に近づいていってませんか? もしかしてこれが公比$r$なのではないでしょうか?

公比$r$のおおまかな値は、Desmosを利用しても求めることができます。順を追って説明しますね。

まずは、縦軸を対数目盛りにします。どういうことかというと、$(n, a_n/n^n)$をプロットするかわりに$(n, \log{(a_n/n^n)})$をプロットするということです。あ、Desmosでは自然対数は$\log$ではなく$\ln$で書くので気をつけてくださいね。すると…

f:id:hal2000_phy:20190823222442p:plain

めっちゃ直線上に並んでるー! 実は、等比数列$ar^n$を、縦軸を対数目盛りにしてプロットすると点は直線に並ぶのです。理由は簡単。横軸に$n$、縦軸に$\log(ar^n)$をプロットしたのですから、$x$と$y$の関係は

$$ y=\log(ar^x) $$

になっているはずです。右辺を対数の性質を使って変形してやると

$$ y=(\log{r})x+\log{a} $$

となり、これは傾きが$\log{r}$で切片が$\log{a}$の直線を表しています。だから、縦軸を対数目盛りにして等比数列をプロットすると、点が直線に並ぶわけです。

ということはですよ、直線に並んだ紫の点の傾きを求めてやれば、公比$r$が求められるのでは…? 傾きが$p=\log{r}$なのですから、傾き$p$から$r$を求めるには$r=e^p$を計算すればいいわけです*4

さっそく傾き(の近似値)を求めましょう。直線からのずれが少ない、$n$が大きい部分の2点を代表して選び、2点間の傾きを計算します。

f:id:hal2000_phy:20190823223907p:plain

計算しやすいように$(5, 1.258)$と$(15,4.051)$の2点を選びました。そこから傾き$p$を求めると

$$ p\simeq\frac{4.051-1.258}{15-5}\simeq 0.2793 $$

となり、この$p$の値から算出される公比$r$は

$$ r=e^p \simeq e^{0.2793}=1.322\cdots $$

になります。やっぱり$1.32\cdots$という値が出てきました。

ここまでわかったこと

ここで少し、今までの話を整理しましょう。

$$ a_n=\sum_{k=0}^n {}_n{\rm C}_k k^n $$

という数列の増加スピードを調べていました。目標は、$a_n$と同程度に増える数列$c_n$を見つけること、すなわち$a_n/c_n$の値が$n\to\infty$のとき$1$に収束するような数列$c_n$を見つけることです。いちいち「同程度に増える」とか「比の値が$n\to\infty$のとき$1$に収束する」とか言っていると面倒なので、このことを

$$ a_n\sim c_n $$

という記号で表すことにしましょう。現在の目標は、

$$ \sum_{k=0}^n {}_n{\rm C}_k k^n \sim c_n $$

になるような数列$c_n$を発見することです。そこで、$a_n$という数列を$n^n$で割ったものを考えたのですが、これが等比数列$ar^n$っぽい増え方をするようなのでした。先ほどの記号で書けば

$$ \frac{a_n}{n^n}\sim ar^n $$

ということです。言い換えると

$$ a_n=\sum_{k=0}^n {}_n{\rm C}_k k^n \sim ar^nn^n $$

ですね。ここで注意ですが、この式はあくまで予想であって、まだ証明したわけではありません。

この式において、定数$a$も$r$も未知ですが、先ほどの考察から、$r$がおよそ$1.32$であることが分かりました。

1.32の正体を探す

ここまでくると、俄然$a$や$r$が何なのか知りたくなりますね。$a$と$r$が分かれば、$a_n$と同程度に増える数列がまさに見つかるわけです。特に$r$については、$1.322$という近似値まで分かっていますから、あとはこれが何の近似値なのか分かればいいのです。

さて、皆さんはWolframAlphaすごい機能があるのを知っていますか? WolframAlphaの検索窓に、$1.322$と入力してみてください。

f:id:hal2000_phy:20190823230321p:plain

はい。入力しましたか? よろしい。そうしたら、検索結果を下にスクロールしください。

f:id:hal2000_phy:20190823230323p:plain

なんと、WolframAlphaくんは有能なので、$1.322$を入力すると$1.322$を近似値にもつような実数の候補を教えてくれるんです。控えめに言って天才です。勝てへん。

1段目に出てくる$\displaystyle{\frac{\pi\log\pi}{e}}$はまだわかります。2段目に出てくる$\displaystyle{-\frac{2H_4}{5}}$に至ってはもはや意味がわかりません。「4th hundred-dollar challenge constant」って何ですか。Wikipediaによると、

$$ \exp\sin{50x}+\sin{60e^y}+\sin(70\sin x)+\sin(\sin 80y)-\sin 10(x+y)+(x^2+y^2)/4 $$

という関数の最小値を$H_4$というらしいですが、何でこんな関数の最小値に名前をつけようと思ったんでしょうか。謎です。

さて、WolframAlphaくんに$1.322$の正体の候補を出してもらいました。$\displaystyle{\frac{\pi\log\pi}{e}}$なんてめちゃめちゃそれっぽいですよね。もうこれでいいじゃん。あとは証明するだけ。

…そう思って証明をつけようと頑張りましたが、いくらやってもできませんでした。友人と僕の数学力が足りないのか、予想が外れているのか、どちらなのかは分かりませんが、たぶん両方だと思います。

オンライン整数列大辞典とかいうのがすごい

ところで、世の中にはオンライン整数列大辞典(OEIS)というものがあります。これです。

f:id:hal2000_phy:20190823232317p:plain

オンライン整数列大辞典は、古今東西ありとあらゆる数列を集めたインターネット上の大辞典です。そこに、例の数列を入力してみます。

f:id:hal2000_phy:20190823232521p:plain

すると…

f:id:hal2000_phy:20190823232607p:plain

まさにこの数列の記事が載っとる


ξ

……載ってました。

オンライン整数列大辞典に収録されている数列には、識別番号がついています。どうやら、この数列の識別番号はA072034のようですね。

さて、この大辞典には数列ごとに個別のページがあり、そこにたくさんの有益情報が載っています。A072034もその例に漏れず、何やら色々かいてあります。COMMENTSという欄にはこの数列の特徴付け(具体的意味)が書いてあったりします。なになに?

COMMENTS: The number of functions from {1,2,...,n} into a subset of {1,2,...,n} summed over all subsets.

要するに、$\displaystyle{\sum_{k=0}^n {}_n{\rm C}_k k^n}$というのは「$n$個の元からなる集合を定義域とし、その部分集合を値域とする写像の総数(ただし対応としては同じ写像でも値域が違うものは区別する)」を意味しているらしいです。よく考えればたしかにそうだ。

その下にあるFORMULAという欄には、数列の一般項の別表現だったり、母関数だったり、漸近挙動だったりといったお役立ち情報が載っています。なるほど。じゃあこの数列のFORMULA欄も見てみようか。




f:id:hal2000_phy:20190823233748p:plain




ん??




f:id:hal2000_phy:20190823233834p:plain




???




f:id:hal2000_phy:20190823233737p:plain




!?!?!?!?

何ですかこれ。どこから降ってきたんですか。ありえんゴツくないですかこれ。てかLambertWって何だよ。

LambertWというのはランベルトのW関数のことです。僕も数学徒の端くれなのでランベルトのW関数のことは定義だけ知っていました。関数$f(x)=xe^x$の逆関数のことをランベルトのW関数といい、$W(x)$と書きます。つまり$y=W(x)$とは

$$ x=ye^y $$

と同じことを言っているということです。お察しの通り、$W(x)$を三角関数や指数関数といった初等関数の組み合わせで表現することはできません。いわゆる特殊関数というやつです。

さて、この式を見るに、$W(1/e)$なる数を使えば、どうやらこの数列A072034と同じスピードで増加する数列を表現できるらしいのです。定義から、$W(1/e)$というのは

$$ xe^x=\frac{1}{e} $$

を満たす実数のことですね。WolframAlphaによれば、その値はおよそ$0.278$だそう。

f:id:hal2000_phy:20190823234858p:plain

そして、オンライン整数列大辞典さまによると、実は

$$ a_n=\sum_{k=0}^n {}_n{\rm C}_k k^n \sim \frac{1}{\sqrt{1+w}}\left(\frac{n}{ew}\right)^n $$

が成り立っているらしい($w=W(1/e)=0.278\cdots$)。はたして本当にそうでしょうか。

でも、この式は、さっきDesmosとにらめっこしながら予想した

$$ a_n=\sum_{k=0}^n {}_n{\rm C}_k k^n \sim ar^nn^n $$

と形の上では一致しています。なぜなら、この式において

$$ a=\frac{1}{\sqrt{1+w}}, \; r=\frac{1}{ew} $$

とすれば、まさに辞典に載っている式になるからです。極め付けは、

$$ \frac{1}{ew}=1.321\cdots $$

になることです。WolframAlphaくんがそう言っています。

f:id:hal2000_phy:20190823235640p:plain

紫の点の傾きから算出した$1.32$という値が登場しました。どうやら

$$ a_n=\sum_{k=0}^n {}_n{\rm C}_k k^n \sim \frac{1}{\sqrt{1+w}}\left(\frac{n}{ew}\right)^n $$

が成り立っている可能性はかなり高いようです。

それにしてもやばい式ですよね。どこからランベルトのW関数が出てくるのかまったく想像がつきません。

証明したい

こんな式を見せられたら、証明したくなるのが人情というものです。ん? 証明したくならない? そういう数学に興味ないやつ大学生活心配なんだよね。ちゃんと人とコミュニケーションとれてる? え? 3人で歩いてると気づいたら自分以外の2人が前を歩いててその後ろを無言でついていきがち?

じゃあ俺と一緒だね()

………はい。

というわけで、式自体はオンライン整数列大辞典とかいうチートを使って超自然的に発見してしまったので、証明ぐらいは自力でやり遂げたいですね。実は先日、数々の偶然が重なって証明をつけることに成功したのですが、長くなったので続きは後日書きたいと思います。

それではこの辺で。さようなら。

後編はこちらから↓

halphy.hatenablog.com

*1:比の値が$1$または$0$以外の定数に近づく場合もありますが、これは両者の増え方は同程度だが定数倍の差があるということを意味します。

*2:実際にこれは成り立ちます。

*3:ただし、これは$a_n$が$n^n$の程度で増えることを必ずしも意味しません。あとで見るように、実際そうなっていません。

*4:さらに、この点列にいちばんよくフィットする直線を求めて、その切片が分かれば$a$の値も分かります