お前も非ナベアツ数の逆数和を求めてみないか (前編)
どうも、数値計算botこと、Y.K.です。
今回の記事、ちょっとばかりレベルが高いですよ。
まぁ、高校数学の二項定理や数IIIの微分が分かればぜんぜん大丈夫です。(大フラグ)
今回の目標は、
非ナベアツ数の逆数和
$$\sum_{k\in \text{NB}^c} \frac1k$$
の値は、約$14.20598003408932794149190575203631490147074474872510358921881909519943818306805\cdots$である。
これを高速に求める方法を考えてみましょう！
逆数和のふるまい
ここからは、まずは逆数和とはどんなものか、どういう値になるのかを見てみましょう。
発散する例
自然数の逆数和
皆さん自然数の逆数和が発散していることはご存じのことと思います。
つまりこれですね
\begin{eqnarray}
\frac11+\frac12+\frac13+\frac14+\frac15+\cdots
\end{eqnarray}
これは興味深いことに、どんどん足す数が小さくなっているのに全部を足すと無限大になるという式になっています。
$$\sum_{k=1}^\infty \frac1k = \frac11+\frac12+\frac13+\frac14+\frac15+\cdots \quad =\; \infty$$
簡単な証明をのせておきましょうか
有限の値になると仮定してみます。それを$S$と置きましょう。
\begin{eqnarray}
S = \sum_{k=1}^{\infty} \frac1k = \frac11+\frac12+\frac13+\frac14+\frac15+\cdots
\end{eqnarray}
しかしここで、次のようにこの$S$を下から不等式で抑えることができます。
\begin{eqnarray}
S &=&&&\l{\frac11+\frac12}&+&&\l{\frac13+\frac14}&+&&\l{\frac15+\frac16}&+&&\l{\frac17+\frac18}&+&&\l{\frac19+\frac1{10}}&&+&\cdots
\\&>&&&\l{\frac12+\frac12}&+&&\l{\frac14+\frac14}&+&&\l{\frac16+\frac16}&+&&\l{\frac18+\frac18}&+&&\l{\frac1{10}+\frac1{10}}&&+&\cdots
\\&=&&&\frac11&+&&\frac12&+&&\frac13&+&&\frac14&+&&\frac15&&+&\cdots
\end{eqnarray}
$\;\;\,=S$
つまり、$S>S$となってしまいますが、これは矛盾です。
よって$S$が発散する(つまり無限大)が分かりました。
(厳密に言うと$2N$までの有限和と$N$までの有限和の比較から極限を取ると$\ge$となり等号が成立してしまうように見えるが、初手の$\left(\frac11+\frac12\right)$をそのままにしておけば$S\ge S+\frac12$となって矛盾を導ける。それと、「絶対収束しない無限級数は括弧の順番を変えると値が変わる」という定理があるが、今回はもし収束するならば絶対収束するという特殊な級数なので、厳密な証明ができる。今回の記事は基本的に単純さ重視で書く。)
この無限の足し算は級数というもののうちの一つで、今回の自然数の逆数和に限っては、調和級数という名前がついています。
$$\sum_{k=1}^n \frac1k = \frac11+\frac12+\frac13+\frac14+\frac15+\frac16+\frac17+\frac18+\frac19+\frac1{10}+\frac1{11}+\cdots$$
素数の逆数和
では、自然数すべての逆数和ではなく、すべての素数の逆数和ではどうでしょうか？
つまりは、
$$\frac12+\frac13+\frac15+\frac17+\frac1{11}+\frac1{13}+\frac1{17}+\frac1{19}+\frac1{23}+\frac1{29}+\frac1{31}+\frac1{37}+\frac1{41}+\cdots$$
です。
これは、実は発散することが知られています。
証明はちょっと難しいので割愛します。けど素数って結構スッカスカなのに発散するのすごい。
( Paul Erdős が1938年に発表した証明がめちゃ分かりやすいので余裕のある人は調べてみて)
収束する例
有名な例
こっちで一番有名なのはこれですよね。
\begin{eqnarray}
\sum_{k=1}^\infty \frac1{2^k} = \frac12+\frac14+\frac18+\frac1{16}+\frac1{32}+\frac1{64}+\frac1{128}+\cdots = 1
\end{eqnarray}
まぁ、$\frac1{2^k}$はかなりすぐ小さくなるので、無限には全然いかなそうですよね。
他には、
\begin{eqnarray}
\sum_{k=1}^\infty \frac1{k^2} = \frac11+\frac14+\frac19+\frac1{16}+\frac1{25}+\frac1{36}+\frac1{49}+\cdots = \frac{\pi^2}6 \approx 1.644934
\end{eqnarray}
というものがあります。
他には、
\begin{eqnarray}
\sum_{k=1}^\infty \frac{(-1)^{k+1}}{k} = \frac11-\frac12+\frac13-\frac14+\frac15-\frac16+\frac17-\frac18+\frac19-\frac1{10}+\frac1{11}-\cdots = \log(2) \approx 0.693147
\end{eqnarray}
とかも面白いですね。
さて、今回の本題に少し、踏み入りましょうか、
9がつかない数
(十進法で)9がつかない数の逆数和は、収束するでしょうか？これ実は収束して、入試問題にも出たことがあるらしいです。
\begin{eqnarray}
\sum_{k\text{は9がつかない数}} \frac1k = \frac11+\frac12+\frac13+\frac14+\frac15+\frac16+\frac17+\frac18+\frac1{10}+\frac1{11}+\cdots
\end{eqnarray}
こういう風に、$k$がどんな数かを$\sum$の下に書くことにして、その条件を満たす$k$の全部で$\frac1k$を足すことにします。
まぁ見てわかる通り9が抜けてますよね。19や29、90~99は全部抜けます。
\begin{eqnarray}
\sum_{k\text{は9がつかない数}} \frac1k &=& \frac11+\frac12+\frac13+\frac14+\frac15+\frac16+\frac17+\frac18
\\&+& \frac1{10}+\frac1{11}+\frac1{12}+\frac1{13}+\frac1{14}+\frac1{15}+\frac1{16}+\frac1{17}+\frac1{18}
\\&+& \frac1{20}+\frac1{21}+\frac1{22}+\frac1{23}+\frac1{24}+\frac1{25}+\frac1{26}+\frac1{27}+\frac1{28}
\\&+& \frac1{30}+\frac1{31}+\frac1{32}+\frac1{33}+\frac1{34}+\frac1{35}+\frac1{36}+\frac1{37}+\frac1{38}
\\&+& \frac1{40}+\frac1{41}+\frac1{42}+\frac1{43}+\frac1{44}+\frac1{45}+\frac1{46}+\frac1{47}+\frac1{48}
\\&+& \frac1{50}+\frac1{51}+\frac1{52}+\frac1{53}+\frac1{54}+\frac1{55}+\frac1{56}+\frac1{57}+\frac1{58}
\\&+& \frac1{60}+\frac1{61}+\frac1{62}+\frac1{63}+\frac1{64}+\frac1{65}+\frac1{66}+\frac1{67}+\frac1{68}
\\&+& \frac1{70}+\frac1{71}+\frac1{72}+\frac1{73}+\frac1{74}+\frac1{75}+\frac1{76}+\frac1{77}+\frac1{78}
\\&+& \frac1{80}+\frac1{81}+\frac1{82}+\frac1{83}+\frac1{84}+\frac1{85}+\frac1{86}+\frac1{87}+\frac1{88}
\\&+& \frac1{100}+\frac1{101}+\frac1{102}+\frac1{103}+\frac1{104}+\frac1{105}+\frac1{106}+\frac1{107}+\frac1{108}+\frac1{110}+\cdots
\end{eqnarray}
まぁこんな感じです。9がないですね。さみしい。
それにしても9が抜けただけで、、、そんなに調和級数と変わらないですよね。
どうやって収束することを示すのでしょうか？
ケンプナー級数との前哨戦
前哨戦（ぜんしょうせん、英語: preliminary skirmish）は、戦争において大規模な会戦に先立ち両軍の前哨部隊同士の間で行われる小規模な戦闘のこと。
転じて、スポーツ等の大会で大きなレースに出場する個人や団体を決定する競走もしくは大会の事を指す英語のトライアルの訳語としても使われる。
-wikipedia
ケンプナー級数という有名な級数があります。さっきのやつのことです。
\begin{eqnarray}
\sum_{k\text{は9がつかない数}} \frac1k = \frac11+\frac12+\frac13+\frac14+\frac15+\frac16+\frac17+\frac18+\frac1{10}\cdots
\end{eqnarray}
ケンプナー級数の収束性
これは昔から研究されていまして、収束はするのですがものすごい収束が遅いことが知られています。
ですが、収束することはある程度容易に証明できます！
なので証明してみましょう
証明
9がつかない数というのは結構厄介な物なので、1桁の時、2桁の時、3桁の時、というように、
桁数で分けて考えてみましょう。
・1桁の時
1桁で9がつかない数ですから、$1,2,3,4,5,6,7,8$の8つですね
これの逆数の和は、
\begin{eqnarray} &&\frac11+\frac12+\frac13+\frac14+\frac15+\frac16+\frac17+\frac18 \\&<&\:1\:+\:1\:+\:1\:+\:1\:+\:1\:+\:1\:+\:1\:+\:1 &=& 8 \end{eqnarray}
つまり$8$より小さいですね！
まぁ、一番大きいのが$\frac11$ですから、それが8個あるので
\begin{eqnarray} \frac11+\frac12+\frac13+\frac14+\frac15+\frac16+\frac17+\frac18 < \frac11\times8 = 8 \end{eqnarray}
でいいですけど。
・2桁の時
これはどうでしょうか？2桁なので1桁の物は考えてはいけませんよ。
十の位と一の位で分けて、十の位と一の位に何か数字を入れると考えるといいでしょう。
十の位に$5$を入れて、一の位で$7$を入れると$57$ができる。みたいな
十の位に入れる数字ですが、ここに入れられる数字は$1,2,3,4,5,6,7,8$のどれかです。
$9$はダメだし、$0$だと2桁の数になりません。
一の位に入れる数字ですが、ここに入れられる数字は$0,1,2,3,4,5,6,7,8$のどれかです。
今度はさっきと違って、$0$は入っても大丈夫なんですよね。まぁ$10$とか$70$とかそうですし。
ということで、全部でいくつ、9のつかない2桁の数があるでしょうか？
十の位で$8$通り、一の位で$9$通りあるので、全部で$8\times9=72$通りです！
まぁ、上で大量に書いた分数を実際に計算してもいいですがね。
さて、$72$個の分数の中で一番大きいのが$\frac1{10}$です。$10$は2桁の数の中で一番小さいですからね。
よって、2桁の9のつかない数の逆数を全部足したやつは、このように上から抑えられます。
\begin{eqnarray} &&\sum_{\substack{k\text{は9がつかない} \\ k\text{は2桁}}} \frac1k = \frac1{10}+\frac1{11}+ \cdots + \frac1{88} < \frac1{10}\times 72 \\ &&\sum_{\substack{k\text{は9がつかない} \\ k\text{は2桁}}} \frac1k < \frac{72}{10} \end{eqnarray}
おお、$7.2$よりは小さいみたいです。いい発見ですね。
ああいう風に$\sum$の下に条件をいくつも付けてもいいです。今回の場合なら、$k$は2桁の整数で、9がつかないものの全部で$\frac1k$を足し算します。
・3桁の時
これも分けて考えたらいいですね。百の位と十の位と一の位で分けます。
百の位に入れる数字ですが、ここに入れられる数字は$1,2,3,4,5,6,7,8$のどれかです。
さっきと同じで$9$はダメだし、やっぱり$0$だと2桁の数になりません。
十の位に入れる数字ですが、ここに入れられる数字は$0,1,2,3,4,5,6,7,8$のどれかです。
百の位に数字が入ってますし、こっちには$0$を入れても大丈夫です。
一の位に入れる数字ですが、ここに入れられる数字も$0,1,2,3,4,5,6,7,8$のどれかです。
さっきと同じですね。
と、言うことで結局何通りあるんですか？$8\times9\times9=648$通りです！
多いですかね？まぁこんなもんでしょうか。
さっきと同じように、$100$が3桁のなかで一番小さい数ですから、$\frac1{100}$が一番大きい分数と分かります。
よって、3桁で9のつかない数の逆数を全部足したやつは、このように上から抑えられます。
\begin{eqnarray} &&\sum_{\substack{k\text{は9がつかない} \\ k\text{は3桁}}} \frac1k = \frac1{100}+\frac1{101}+ \cdots + \frac1{888} < \frac1{10}\times 648 \\ &&\sum_{\substack{k\text{は9がつかない} \\ k\text{は3桁}}} \frac1k < \frac{648}{100} \end{eqnarray}
なるほど、$6.48$よりは小さいようですね。
・$d$桁の時
これをずっと続けていくとどうなるのか？というのを考えたいと思います。
まぁ、おんなじことするだけです。$d$は2以上の自然数とします。
またやっぱり位で分けて考えてみましょう。
一番上の位($10^{d-1}$の位)に入れる数字ですが、ここに入れられる数字は$1,2,3,4,5,6,7,8$のどれかです。一番上なので$0$を入れてはいけません。$9$ももちろんだめです。
その一つ下の、
二番目の位($10^{d-2}$の位)に入れる数字ですが、ここに入れられる数字は$0,1,2,3,4,5,6,7,8$のどれかです。一番上じゃなくなったし$0$を入れてもいいですね。
三番目の位($10^{d-3}$の位)に入れる数字ですが、これも入れられる数字は$0,1,2,3,4,5,6,7,8$のどれかです。
四番目の位($10^{d-4}$の位)に入れる数字ですが、これも入れられる数字は$0,1,2,3,4,5,6,7,8$のどれかです。またです。
...つまりは、一番上の位だけ$1,2,3,4,5,6,7,8$が入れられて、一番上の位以外は$0,1,2,3,4,5,6,7,8$を入れられるっていうわけですわ。
ということは、$d$桁あるんだから、$1$桁だけ$8$通りで、残りの$d-1$桁はそれぞれ$9$通りの数字の入れ方があるってことですね。なるほど。
じゃぁ、結局$d$桁の数字で9のつかないものは、全部で$8\times9^{d-1}$通りあると分かりました！
さっきと同じように、やはり$d$桁の数字で一番小さいのは$10^{d-1}$ですから、
この逆数である$\frac1{10^{d-1}}$が、$8\times9^{d-1}$通りの分数の中で一番大きい分数になります。
ということは...?
\begin{eqnarray} &&\sum_{\substack{k\text{は9がつかない} \\ k\text{は$d$桁}}} \frac1k < \frac1{10^{d-1}}\times 8\times9^{d-1} \\ &&\sum_{\substack{k\text{は9がつかない} \\ k\text{は3桁}}} \frac1k < \frac{9^{d-1}}{10^{d-1}}\times8 \\ &&\sum_{\substack{k\text{は9がつかない} \\ k\text{は3桁}}} \frac1k <\l{\frac9{10}}^{d-1}\times8 \end{eqnarray}
なるほど。$\l{\frac9{10}}^{d-1}\times8$よりは小さいみたいですね！これはいい結果ではないでしょうか？
・結論
ケンプナー級数は、次のように桁数ごとに分けて考えることができます。
\begin{eqnarray} \sum_{k\text{は9がつかない}} \frac1k &=& \sum_{\substack{k\text{は9がつかない} \\ k\text{は1桁}}} \frac1k + \sum_{\substack{k\text{は9がつかない} \\ k\text{は2桁}}} \frac1k + \sum_{\substack{k\text{は9がつかない} \\ k\text{は3桁}}} \frac1k + \cdots \end{eqnarray}
ここで、さっきの議論により、
\begin{eqnarray} \sum_{\substack{k\text{は9がつかない} \\ k\text{は$d$桁}}} \frac1k < \l{\frac9{10}}^{d-1}\times8 \end{eqnarray}
ですから、一個一個を上から抑えることができます！
\begin{eqnarray} \sum_{k\text{は9がつかない}} \frac1k &=&&& \sum_{\substack{k\text{は9がつかない} \\ k\text{は1桁}}} \frac1k &&+& \sum_{\substack{k\text{は9がつかない} \\ k\text{は2桁}}} \frac1k &&+& \sum_{\substack{k\text{は9がつかない} \\ k\text{は3桁}}} \frac1k &&+& \sum_{\substack{k\text{は9がつかない} \\ k\text{は3桁}}} \frac1k &&+&\cdots \\&<&&& 8 &&+& \l{\frac9{10}}^{2-1}\times8 &&+& \l{\frac9{10}}^{3-1}\times8 &&+& \l{\frac9{10}}^{4-1}\times8 &&+& \cdots \end{eqnarray}
つまり、
\begin{eqnarray} \sum_{k\text{は9がつかない}} \frac1k &<& 8+8\cdot\l{\frac9{10}}^1+8\cdot\l{\frac9{10}}^2+8\cdot\l{\frac9{10}}^3+8\cdot\l{\frac9{10}}^4+\cdots \\&=& 8 \l{1+\l{\frac9{10}}^1+\l{\frac9{10}}^2+\l{\frac9{10}}^3+\l{\frac9{10}}^4+\cdots} \end{eqnarray}
ここで、$-1<\frac9{10}<1$ですから、無限等比級数の和の公式：
$$a+ar+ar^2+ar^3+\cdots = \frac a{1-r}$$
が使えます！($-1< r<1$が使える条件)
これを使うと、
\begin{eqnarray} &&8 \l{1+\l{\frac9{10}}^1+\l{\frac9{10}}^2+\l{\frac9{10}}^3+\l{\frac9{10}}^4+\cdots} \\&=& 8\l{\frac{1}{1-\frac9{10}}} \\&=& 8\l{\frac1{\frac1{10}}} \\&=& 8\cdot10 \\&=& 80 \end{eqnarray}
ということは.....
ケンプナー級数が80未満であることが分かりました！！！！
\begin{eqnarray} \sum_{k\text{は9がつかない}} \frac1k < 80 \end{eqnarray}
素晴らしいですね！等比級数で抑えれるというのはびっくりだと思います。
これでケンプナー級数の値は$80$未満だと分かりました！
ケンプナー級数の本当の値
君たちはケンプナー級数の恐ろしさを知らない。
というのもですね、こちらのグラフを見てくれると分かると思います。
上の緑の破線がさっき示した$80$という値です。
で、赤の点線が本当に収束するはずのケンプナー級数の真の値です。
で、その下の青い線、これが愚直に分数を一つずつ足していったものです。
なんとですね、さっきの$80$というのはそもそも全然真の値に近くない($3.49$倍も違う)し、
しかも愚直に足したほうも全然大きくならないのです。
つまり、真の値を考えるには上からも下からも抑えるのが甘すぎるってことですね。
じゃぁどおする？
うーん...
一般化二項定理
ちょっと途中で使うことになるので、これの証明をしておきます。
$p$が正の整数で$x$が$-1< x<1$の時、以下が成り立つ：
\begin{eqnarray}
\frac{1}{(1+x)^p} = \sum_{j=0}^{\infty} {}_{p+j-1}C_{j}(-1)^j x^j \tag{1}
\end{eqnarray}
ただし、${}_nC_r$は二項係数
ここでは$0^0=1$としておきます。
一応高校数学範囲で証明はできます。(厳密ではない)
証明
本当はマクローリン展開というかっこいい証明方法があるのですが、それ相応の知識がいるので、ここでは$p$についての数学的帰納法で示します。
$p=1$の時
$|x| < 1$のとき、初項$1$公比$-x$の無限等比級数の和の公式より：
\begin{eqnarray} \frac{1}{1+x} = \sum_{j=0}^{\infty} (-1)^j x^j = 1 - x + x^2 - x^3 + x^4 - \dots \end{eqnarray}
一方、$(1)$の右辺へ$p=1$を代入すると、
\begin{eqnarray} \sum_{j=0}^{\infty} {}_jC_j(-1)^jx^j = \sum_{j=0}^{\infty}(-1)^jx^j \end{eqnarray}
となり成立します。
$p=k$で成り立っていると仮定して、$p=k+1$で成り立つことを示します。
帰納法の仮定より、
\begin{eqnarray} \frac1{(1+x)^k} = \sum_{j=0}^\infty {}_{k+j-1}C_{j}(-1)^jx^j \end{eqnarray}
が成立します。この両辺を$x$で微分していきます。
左辺を微分すると、
\begin{eqnarray} \frac{d}{dx}\frac1{(1+x)^k} &=& \frac{d}{dx}(1+x)^{-k} \\&=& -k(1+x)^{-k-1} \\&=& -\frac{k}{(1+x)^{k+1}} \end{eqnarray}
となります。
右辺を微分すると、
\begin{eqnarray} \frac{d}{dx}\l{\sum_{j=0}^\infty {}_{k+j-1}C_j(-1)^jx^j} &=& \frac{d}{dx}\l{{}_{k-1}C_0(-1)^0x^0+\sum_{j=1}^\infty {}_{k+j-1}C_j(-1)^jx^j} \quad(j=0\text{の時だけ分けた}) \\&=& \frac{d}{dx}\l{1+\sum_{j=1}^\infty {}_{k+j-1}C_j(-1)^jx^j} \\&=& 0 + \sum_{j=1}^\infty {}_{k+j-1}C_j(-1)^jjx^{j-1} \\&=& \sum_{j=1}^\infty j\cdot{}_{k+j-1}C_j (-1)^jx^{j-1} \end{eqnarray}
今は$j$は$1,2,3,4,\cdots$と動いていきますが、 $(j=1\sim\infty)$
ここで$j$を$0,1,2,3,\cdots$と動かしたいです。 $(j=0\sim\infty)$
こうなると、もともと$j$が$1,2,3,4,\cdots$となっていたところは、$j+1$が$1,2,3,4,\cdots$となることになります。つまり、$j$だったところを$j+1$に直せばいいです。
\begin{eqnarray} \sum_{j=1}^\infty j\cdot {}_{k+j-1}C_j x^{j-1} &=& \sum_{j=0}^\infty (j+1)\cdot {}_{k+(j+1)-1}C_{(j+1)} (-1)^{(j+1)}x^{(j+1)-1} \\&=& \sum_{j=0}^\infty (j+1)\cdot {}_{k+j}C_{j+1} (-1)^{j+1}x^j \tag{2} \end{eqnarray}
ここで、係数の部分を考察しておきます。
二項係数の階乗での書き方を使います。
${}_nC_r = \frac{n!}{(n-r)!\,r!}$これです。
これを使うと、
\begin{eqnarray} (j+1)\cdot {}_{k+j}C_{j+1} &=& (j+1)\frac{(k+j)!}{(k+j-(j+1))!\,(j+1)!} \\&=& (j+1)\frac{(k+j)!}{(k-1)!\,(j+1)!} \\&=& \frac{(k+j)!}{(k-1)!\,j\;\!!} \\&=& k\cdot\frac1k\cdot\frac{(k+j)!}{(k-1)!\,j\;\!!} \\&=& k\cdot\frac{(k+j)!}{k!\,j\;\!!} \\&=& k\cdot {}_{k+j}C_j \end{eqnarray}
したがって、式$(2)$は以下のようになります。
\begin{eqnarray} &&\sum_{j=0}^\infty k\cdot{}_{k+j}C_j(-1)^{j+1}x^j \\&=& -k\sum_{j=0}^\infty \cdot{}_{k+j}C_j(-1)^jx^j \end{eqnarray}
さぁ、左辺の微分と右辺の微分が等しいので、
\begin{eqnarray} -\frac{k}{(1+x)^{k+1}} &=& -k\sum_{j=0}^\infty \cdot{}_{k+j}C_j(-1)^jx^j \\ \end{eqnarray}
両辺$-k$で割って、
\begin{eqnarray} \frac{1}{(1+x)^{k+1}} &=& \sum_{j=0}^\infty {}_{k+j}C_j(-1)^jx^j \\ \end{eqnarray}
これはまさに式$(1)$の$p=k+1$の時と完全に一緒です！
以上により、数学的帰納法によって任意の正の整数$p$について式$(1)$が成り立つことが分かりました。
(厳密には、「無限級数を項別に微分してよいか？」という点が問題になるが、冪級数が収束半径の内部$|x| < 1$で何回でも項別微分可能（解析的）であるという解析学の定理によって保証されている。)
ケンプナー級数と戦う
まぁちょっと考えてみましょうや。
先ほどのケンプナー級数の収束性の証明のところで、一つ興味深いことがあったのを覚えていますか？
百の位に入れる数字ですが、ここに入れられる数字は$1,2,3,4,5,6,7,8$のどれかです。
さっきと同じで$9$はダメだし、やっぱり$0$だと2桁の数になりません。
十の位に入れる数字ですが、ここに入れられる数字は$0,1,2,3,4,5,6,7,8$のどれかです。
百の位に数字が入ってますし、こっちには$0$を入れても大丈夫です。
一の位に入れる数字ですが、ここに入れられる数字も$0,1,2,3,4,5,6,7,8$のどれかです。
さっきと同じですね。
ここです。分かりますか？"さっきと同じ"なんですよ。さっきと同じなんですよ
ここで言う「さっき」というのは2桁の時のことですね。
つまり、3桁で考えたときに 百の位 に入れられる数字は、2桁で考えた時に 十の位 に入れられる数字と同じです。
3桁で考えた時に 十の位 に入れられる数字は、2桁で考えた時に 一の位 に入れられる数字と同じです。
要するに、2桁の時に考えた数字は、全部3桁を考えたときの上2桁に入るってことです
73を例にとったが、何でも行ける
さらに言うと、3桁の数を考えたときに出てくる上2桁は、2桁の時に考えた数で全部尽くされているんですよ。
つまり、2桁のほうを考えれば3桁は全部調べられるってことです。
一の位には$0,1,2,3,4,5,6,7,8$のどれかが入ります。これはそのままですね。
一個前のやつを使って書こう
このアイデアをもうちょっと数学的に書きましょうか。
$d$桁の9がつかない数を全て集めた集合を、$K_{d\!\;\text{桁}}$とします。
上のアイデアをこれで言うと、
$K_{d+1\!\;\text{桁}}$の中のどの数字$k'$を取ってきても、$K_{d\!\;\text{桁}}$の中のある数字$k$と、$0\sim8$の数字の内のどれか$m$を使って、
$$k' = 10k+m$$
と表せる。
ということです。
例えば$K_{3\!\;\text{桁}}$から3桁の数字を一つ、例えば$276$を取ってきます。
これを見ると、明らかに$K_{2\!\;\text{桁}}$から$27$をとり、$m=6$とすれば、
$$276 = 10\cdot 27 + 6$$
を満たしています。なるほどですね。
これを使って、収束性を確かめたときのように、「$d+1$桁の9のつかない数の逆数和」を、「$d$桁の9がつかない数の逆数和」で表せないでしょうか？？？
ちょっと考えてみます。
$d$桁の9がつかない数の逆数和、というのを$S_{d\!\;\text{桁}}$で表すことにします。
\begin{eqnarray}
S_{d\!\;\text{桁}} = \sum_{k'\in K_{d\!\;\text{桁}}} \frac1{k'}
\end{eqnarray}
ここの$k'\in K_{d\!\;\text{桁}}$というのは、$k'$は$K_{d\!\;\text{桁}}$の中の数字という条件です。
この条件を満たす$k'$全てにおいて$\frac1{k'}$の合計を$S_{d\!\;\text{桁}}$とする、ということです。
そして、さっきの話から$K_{d+1\;\!\text{桁}}$は、$K_{d\!\;\text{桁}}$と$0\sim8$の数で表せるので、
\begin{eqnarray}
S_{d+1\!\;\text{桁}} &=& \sum_{k'\in K_{d+1\!\;\text{桁}}} \frac1{k'}
\\&=&\sum_{k\in K_{d\!\;\text{桁}}} \l{ \frac1{10k+0}+\frac1{10k+1}+\frac1{10k+2}+\frac1{10k+3}+\frac1{10k+4}+\frac1{10k+5}+\frac1{10k+6}+\frac1{10k+7}+\frac1{10k+8}}
\end{eqnarray}
こういうことですね！確かに$K_{d+1\!\;\text{桁}}$の中から一つ数$k'$を取ってきたやつを、$K_{d\!\;\text{桁}}$の中の数$k$に$0\sim8$を後ろに付けることで表せています。
ただ、$\frac1{10k+0}+\frac1{10k+1}+\frac1{10k+2}+\frac1{10k+3}+\frac1{10k+4}+\frac1{10k+5}+\frac1{10k+6}+\frac1{10k+7}+\frac1{10k+8}$
というのはさすがに長いので、$\displaystyle{\sum_{m=0}^8 \frac1{10k+m}}$という風にまとめておきましょう。
\begin{eqnarray} S_{d+1\!\;\text{桁}} &=& \sum_{k\in K_{d\!\;\text{桁}}} \l{\sum_{m=0}^8 \frac1{10k+m}} \end{eqnarray}
こんな感じになりました！
さらなる目標
1乗の時
目標としては、$S_{d+1\!\;\text{桁}}$を$S_{d\!\;\text{桁}}$で表したいんですよぉぉ
だから、上の式の右辺、こいつをどうにかしたいです。どうにか、
\begin{eqnarray}
S_{d\!\;\text{桁}} = \sum_{k\in K_{d\!\;\text{桁}}} \frac1{k}
\end{eqnarray}
つまり$\frac1{k}$をひねり出してやりたいんですよ。
ほなひねり出しましょうや。
\begin{eqnarray}
\frac1{10k+m} = \frac1{10k(1+\frac m{10k})} = \frac1{10k}\cdot\frac1{1+\frac m{10k}}
\end{eqnarray}
いくらなんでも無理やりすぎやろ...
けど、これが使えます。
最後の項の、$\displaystyle{\frac1{1+\frac m{10k}}}$の部分、これに見覚えがないですか？
そうですね。一般化二項定理ですよ！
$p$が正の整数で$x$が$-1< x<1$の時、以下が成り立つ：
\begin{eqnarray}
\frac{1}{(1+x)^p} = \sum_{j=0}^{\infty} {}_{p+j-1}C_{j}(-1)^j x^j \tag{1}
\end{eqnarray}
ただし、${}_nC_r$は二項係数
これこれ、この$p=1$の時にピッタリ一致します！
\begin{eqnarray}
\frac1{(1+x)^1} &=& \sum_{j=0}^\infty {}_{1+j-1}C_j(-1)^jx^j
\\&=& \sum_{j=0}^\infty {}_jC_j(-1)^jx^j
\\&=& \sum_{j=0}^\infty (-1)^jx^j
\end{eqnarray}
です。そして$x$の条件に合うかですが、$0 \leqq \frac m{10k} <1$ですから、ぜんぜん大丈夫です。
ということで$x=\frac m{10k}$を代入しましょう
\begin{eqnarray}
\frac1{1+\frac m{10k}} = \sum_{j=0}^\infty (-1)^j\l{\frac m{10k}}^j
\end{eqnarray}
こうなりました。
これによって、
\begin{eqnarray}
\frac1{10k+m} &=& \frac1{10k}\cdot\frac1{1+\frac m{10k}}
\\&=& \frac1{10k}\sum_{j=0}^\infty (-1)^j\l{\frac m{10k}}^j
\\&=& \frac1{10k}\sum_{j=0}^\infty (-1)^jm^j\frac 1{(10k)^j}
\\&=& \sum_{j=0}^\infty (-1)^jm^j\frac 1{(10k)^{j+1}}
\end{eqnarray}
ですね。
元の式はこうなります。
\begin{eqnarray}
S_{d+1\!\;\text{桁}} &=& \sum_{k\in K_{d\!\;\text{桁}}} \l{\sum_{m=0}^8 \frac1{10k+m}}
\\&=& \sum_{k\in K_{d\!\;\text{桁}}} \l{\sum_{m=0}^8 \l{\sum_{j=0}^\infty (-1)^jm^j\frac 1{(10k)^{j+1}}}}
\end{eqnarray}
ぐへぇ、三重シグマですか。
ただ、シグマって入れ変えれるの知ってましたか？
例えば、
\begin{eqnarray}
\sum_{a=1}^4 \l{\sum_{b=2}^8 10a+b}
\end{eqnarray}
というのは、内側の部分が
$$\sum_{b=2}^8 10a+b = (10a+2)+(10a+3)+(10a+4)+(10a+5)+(10a+6)+(10a+7)+(10a+8)$$
ですから、
\begin{eqnarray}
&&\sum_{a=1}^4 \l{\sum_{b=2}^8 10a+b}
\\&=& \sum_{a=1}^4 \big((10a+2)+(10a+3)+(10a+4)+(10a+5)+(10a+6)+(10a+7)+(10a+8)\big)
\\&&= 12+13+14+15+16+17+18
\\&&+22+23+24+25+26+27+28
\\&&+32+33+34+35+36+37+38
\\&&+42+43+44+45+46+47+48
\end{eqnarray}
となります。
これ、縦に見ると、
\begin{eqnarray}
12+22+32+42 \\
13+23+33+43 \\
14+24+34+44 \\
15+25+35+45 \\
16+26+36+46 \\
17+27+37+47 \\
18+28+38+48
\end{eqnarray}
という風に並んでます。この各行は、一の位を$b$とすれば
$(10+b)+(20+b)+(30+b)+(40+b)$になり、一の位が$2\sim8$まで動いているので、
\begin{eqnarray}
\sum_{b=2}^8 \big((10+b)+(20+b)+(30+b)+(40+b)\big)
\end{eqnarray}
と纏められますよね。
で、
\begin{eqnarray}
(10+b)+(20+b)+(30+b)+(40+b) = \sum_{a=1}^4 10a+b
\end{eqnarray}
ですから、これを入れると
\begin{eqnarray}
\sum_{b=2}^8 \l{\sum_{a=1}^4 10a+b}
\end{eqnarray}
になりました！つまりは、シグマの順番を入れ替えれたということになります。
結局は、$a$を先に動かすか$b$を先に動かすかの違いであって、全部展開してしまえば全く同じ項しか出てこないのです。$a$を先に動かしても、必ず$a=3,b=7$の時が足されるのだし、$b$を先に動かしても、必ず$b=7,a=3$の時がやってくるのです。シグマが入れ替えれそうだと思ってくれたでしょうか？
とりあえず、シグマの順番は入れ替えても大丈夫です。
(今回は$\displaystyle \sum_{j=0}^\infty$が無限級数ですが、等比数列の和なので有限値に収束すること、外側の$\displaystyle \sum_{k\in K_{d\!\;\text{桁}}}, \sum_{m=0}^8 $が有限和であることから、極限の線形性より入れ替えることができます。)
さっきの式を入れ替えてやりましょう。
\begin{eqnarray}
&&\sum_{k\in K_{d\!\;\text{桁}}} \l{\sum_{m=0}^8 \l{\sum_{j=0}^\infty (-1)^jm^j\frac 1{(10k)^{j+1}}}}
\\&=& \sum_{j=0}^\infty \l{\sum_{k\in K_{d\!\;\text{桁}}} \l{\sum_{m=0}^8 (-1)^jm^j\frac 1{(10k)^{j+1}}}}
\end{eqnarray}
一番中の$\displaystyle (-1)^jm^j\frac1{(10k)^{j+1}}$ですが、$m$に関係のない部分は$\displaystyle \sum_{m=0}^8$の外に出せます。
\begin{eqnarray}
&=& \sum_{j=0}^\infty \l{\sum_{k\in K_{d\!\;\text{桁}}} (-1)^j\frac 1{(10k)^{j+1}}\l{\sum_{m=0}^8 m^j}}
\end{eqnarray}
もう一度、$\displaystyle (-1)^j\frac1{(10k)^{j+1}}\l{\sum_{m=0}^8 m^j}$の部分を$\displaystyle (-1)^j\frac1{10^{j+1}}\l{\sum_{m=0}^8 m^j}\cdot\frac1{k^{j+1}}$にばらして、
前半の$k$に関係のない部分は$\displaystyle \sum_{k\in K_{d\!\;\text{桁}}}$の外に出してしまいましょう。
\begin{eqnarray}
&=& \sum_{j=0}^\infty \l{{\color{#00f}\sum_{k\in K_{d\!\;\text{桁}}}} {\color{#f00}(-1)^j\frac 1{10^{j+1}}\l{\sum_{m=0}^8 m^j}}\cdot{\color{#00f}\frac1{k^{j+1}}}}
\\&=& \sum_{j=0}^\infty \l{{\color{#f00}(-1)^j\frac1{10^{j+1}}\l{\sum_{m=0}^8 m^j}}\l{{\color{#00f}\sum_{k\in K_{d\!\;\text{桁}}} \frac1{k^{j+1}}}}}
\end{eqnarray}
やったー できた
\begin{eqnarray} S_{d+1\!\;\text{桁}} = \sum_{j=0}^\infty \l{(-1)^j\frac1{10^{j+1}}\l{\sum_{m=0}^8 m^j}\l{\sum_{k\in K_{d\!\;\text{桁}}} \frac1{k^{j+1}}}} \end{eqnarray}
と思っていたのですが、なにやら変なものが出てきてしまいました。
\begin{eqnarray}
\sum_{k\in K_{d\!\;\text{桁}}} \frac1{k^{j+1}}
\end{eqnarray}
えぇ、ちょっと違う...
欲しかったのは
\begin{eqnarray}
S_{d\!\;\text{桁}} = \sum_{k\in K_{d\!\;\text{桁}}} \frac1{k}
\end{eqnarray}
であって、$j+1$乗はいらないのですが...
これ、どうも悩ましくてですね、どうにもこれでは$j+1$乗は回避できないようなのです。
どうやっても冪乗が回避できないなら、、、冪乗の時の和も考えればよいのでは？
$p$乗の時
ということで、もう一度考え直してみましょう。
冪乗の和が出てきたので、これ自体について考えてみます
\begin{eqnarray}
S_{d\!\;\text{桁}}^{(p)} = \sum_{k\in K_{d\!\;\text{桁}}} \frac1{k^p}
\end{eqnarray}
つまりは、単に逆数を取って足すのではなく$p$乗して逆数を取って足します。
\begin{eqnarray}
&&S_{2\!\;\text{桁}}^{(3)} = \sum_{k\in K_{2\!\;\text{桁}}} \frac1{k^3}
\\&=& \frac1{10^3}+\frac1{11^3}+\frac1{12^3}+\frac1{13^3}+\frac1{14^3}+\frac1{15^3}+\frac1{16^3}+\frac1{17^3}+\frac1{18^3}
\\&+&\frac1{20^3}+\frac1{21^3}+\frac1{22^3}+\frac1{23^3}+\frac1{24^3}+\frac1{25^3}+\frac1{26^3}+\frac1{27^3}+\frac1{28^3}
\\&+&\frac1{30^3}+\frac1{31^3}+\frac1{32^3}+\frac1{33^3}+\frac1{34^3}+\frac1{35^3}+\frac1{36^3}+\frac1{37^3}+\frac1{38^3}
\\&+&\frac1{40^3}+\frac1{41^3}+\frac1{42^3}+\frac1{43^3}+\frac1{44^3}+\frac1{45^3}+\frac1{46^3}+\frac1{47^3}+\frac1{48^3}
\\&+&\frac1{50^3}+\frac1{51^3}+\frac1{52^3}+\frac1{53^3}+\frac1{54^3}+\frac1{55^3}+\frac1{56^3}+\frac1{57^3}+\frac1{58^3}
\\&+&\frac1{60^3}+\frac1{61^3}+\frac1{62^3}+\frac1{63^3}+\frac1{64^3}+\frac1{65^3}+\frac1{66^3}+\frac1{67^3}+\frac1{68^3}
\\&+&\frac1{70^3}+\frac1{71^3}+\frac1{72^3}+\frac1{73^3}+\frac1{74^3}+\frac1{75^3}+\frac1{76^3}+\frac1{77^3}+\frac1{78^3}
\\&+&\frac1{80^3}+\frac1{81^3}+\frac1{82^3}+\frac1{83^3}+\frac1{84^3}+\frac1{85^3}+\frac1{86^3}+\frac1{87^3}+\frac1{88^3}
\end{eqnarray}
です。なんだか仰々しいというか、迫力がありますが、やってることに大したことはないです。
9がつかない二桁の数を3乗して逆数の和を計算してるだけです。
さてさて、この$S_{d\!\;\text{桁}}^{(p)}$に対して、漸化式を出せるでしょうか？
と言ってもまぁ、さっきと同じことするだけなんですがね。
やったりますか。
さっきは、
\begin{eqnarray}
S_{d+1\!\;\text{桁}} &=& \sum_{k\in K_{d\!\;\text{桁}}} \l{\sum_{m=0}^8 \frac1{10k+m}}
\end{eqnarray}
だったのですが、今回は分数が全部$p$乗されているとのことなので、
\begin{eqnarray}
S^{(p)}_{d+1\!\;\text{桁}} &=& \sum_{k\in K_{d\!\;\text{桁}}} \l{\sum_{m=0}^8 \frac1{(10k+m)^p}}
\end{eqnarray}
ですね。ここら辺は楽勝です。
えーっと、次は$\frac1{k}$をひねり出してましたっけ？
ただ、今度は$S^{(p)}_{d\!\;\text{桁}}$なので、$\frac1{k^p}$をひねり出したいですね。
\begin{eqnarray}
\frac1{(10k+m)^p} &=& \frac1{(10k)^p(1+\frac m{10k})^p} &=& \frac1{(10k)^p}\cdot\frac1{(1+\frac m{10k})^p}
\end{eqnarray}
これも楽勝ですね。
じゃぁ、ここに一般化二項定理をぶち込んでやります。
\begin{eqnarray} \frac{1}{(1+x)^p} = \sum_{j=0}^{\infty} {}_{p+j-1}C_{j}(-1)^j x^j \tag{1} \end{eqnarray}
えーっと？$x=\frac m{10k}$にして、$p$はそのままにすればいいか。
\begin{eqnarray}
\frac1{(1+\frac m{10k})^p} &=& \sum_{j=0}^\infty {}_{p+j-1}C_j(-1)^j\l{\frac m{10k}}^j
\\&=& \sum_{j=0}^\infty {}_{p+j-1}C_j(-1)^jm^j\frac 1{(10k)^j}
\end{eqnarray}
二項係数はどうしようもないですね... そのままにしておきましょう。
これを使うと、
\begin{eqnarray}
\frac1{(10k+m)^p} &=& \frac1{(10k)^p}\cdot\frac1{(1+\frac m{10k})^p}
\\&=& \frac1{(10k)^p} \cdot \sum_{j=0}^\infty {}_{p+j-1}C_j(-1)^jm^j\frac 1{(10k)^j}
\\&=& \sum_{j=0}^\infty {}_{p+j-1}C_j(-1)^jm^j\frac 1{(10k)^{p+j}}
\end{eqnarray}
元の式に入れるとこうなります。
\begin{eqnarray} S^{(p)}_{d+1\!\;\text{桁}} &=& \sum_{k\in K_{d\!\;\text{桁}}} \l{\sum_{m=0}^8 \frac1{(10k+m)^p}} \\&=& \sum_{k\in K_{d\!\;\text{桁}}} \l{\sum_{m=0}^8 \l{\sum_{j=0}^\infty {}_{p+j-1}C_j(-1)^jm^j\frac1{(10k)^{p+j}}}} \end{eqnarray}
出ましたね。3重シグマです。入れ替えてやりましょう。
\begin{eqnarray} &&\sum_{k\in K_{d\!\;\text{桁}}} \l{\sum_{m=0}^8 \l{\sum_{j=0}^\infty {}_{p+j-1}C_j(-1)^jm^j\frac1{(10k)^{p+j}}}} \\&&\downarrow \\&&\sum_{j=0}^\infty \l{\sum_{k\in K_{d\!\;\text{桁}}} \l{\sum_{m=0}^8 {}_{p+j-1}C_j(-1)^jm^j\frac1{(10k)^{p+j}}}} \end{eqnarray}
$\displaystyle\sum_{j=0}^\infty$を一番後ろに持ってきました。
一番中の、$\displaystyle {}_{p+j-1}C_j(-1)^jm^j\frac1{(10k)^{p+j}}$ですが、$m$に関係のない部分は外に出せます。
\begin{eqnarray} \sum_{j=0}^\infty \l{\sum_{k\in K_{d\!\;\text{桁}}} {}_{p+j-1}C_j(-1)^j\frac1{(10k)^{p+j}}\l{\sum_{m=0}^8 m^j}} \end{eqnarray}
さらに、
\begin{eqnarray} {}_{p+j-1}C_j(-1)^j\frac1{(10k)^{p+j}}\l{\sum_{m=0}^8 m^j} = {}_{p+j-1}C_j(-1)^j\frac1{10^{p+j}}\l{\sum_{m=0}^8 m^j}\cdot \frac1{k^{p+j}} \end{eqnarray}
という風にばらして、前半の$k$に関係のない部分は$\displaystyle \sum_{k\in K_{d\!\;\text{桁}}}$の外に出してしまいましょう。
\begin{eqnarray} &=& \sum_{j=0}^\infty \l{{\color{#00f}\sum_{k\in K_{d\!\;\text{桁}}}} {\color{#f00}{}_{p+j-1}C_j(-1)^j\frac1{10^{p+j}}\l{\sum_{m=0}^8 m^j}}\cdot{\color{#00f}\frac1{k^{p+j}}}} \\&=& \sum_{j=0}^\infty \l{{\color{#f00}{}_{p+j-1}C_j(-1)^j\frac1{10^{p+j}}\l{\sum_{m=0}^8 m^j}}\l{{\color{#00f}\sum_{k\in K_{d\!\;\text{桁}}} \frac1{k^{p+j}}}}} \end{eqnarray}
やったーということで、はいここ注目
\begin{eqnarray}
\sum_{k\in K_{d\!\;\text{桁}}} \frac1{k^{p+j}}
\end{eqnarray}
これ、完全に$S^{(p+j)}_{d\!\;\text{桁}}$ですね！
ということは
\begin{eqnarray}
\sum_{j=0}^\infty \l{{}_{p+j-1}C_j(-1)^j\frac1{10^{p+j}}\l{\sum_{m=0}^8 m^j}S^{(p+j)}_{d\!\;\text{桁}}}
\end{eqnarray}
こうなります。
打ち切り項数の決定
\begin{eqnarray} S^{(p)}_{d+1\!\;\text{桁}} &=& \sum_{j=0}^\infty \l{{}_{p+j-1}C_j(-1)^j\frac1{10^{p+j}}\l{\sum_{m=0}^8 m^j}S^{(p+j)}_{d\!\;\text{桁}}} \end{eqnarray}
さて、$d$桁と$d+1$桁を結ぶ漸化式は無事で来たのですが、これ、計算に使えるんですか？
いやいや、というのも$\displaystyle \sum_{j=0}^\infty$って無限に足してるじゃないですか。
ということで、どこかで$j$については打ち切らないといけないようです。
え、どこで？
どこで打ち切ったらいいんでしょうか？？？
いや、精度いっぱい計算して値が変わらなくなったら終わったらいいじゃないかって？
いや、これを必要としている人物もいるんですよ、世の中には。
これも実は、計算できます。
誤差を考える
とりあえず$\displaystyle \sum_{j=0}^\infty$の中身を$A_j$と置きます。
\begin{eqnarray}
&& S^{(p)}_{d+1\!\;\text{桁}} = \sum_{j=0}^\infty A_j
\\&& A_j = {}_{p+j-1}C_j(-1)^j\frac1{10^{p+j}}\l{\sum_{m=0}^8 m^j}S^{(p+j)}_{d\!\;\text{桁}}
\end{eqnarray}
私たちが今求めたい、というか知りたいのは、$j$が$0$から$N$項目まで足したときの値
$$\sum_{j=0}^N A_j $$
と、本当の値
$$\sum_{j=0}^\infty A_j$$
との差、
$$\l{\sum_{j=0}^\infty A_j} - \l{\sum_{j=0}^N A_j} = \sum_{j=N+1}^\infty A_j$$
の、大きさです。
つまり$\displaystyle \left|\sum_{j=N+1}^\infty A_j\right|$ですね。絶対値でか
こいつ、$R_N$という名前を付けておきます。
\begin{eqnarray}
R_N &=& \left|\sum_{j=N+1}^\infty A_j\right|
\end{eqnarray}
ここに三角不等式を使ってあげます。
実数$x,y$に対し、
$$|x+y| \leqq |x|+|y|$$
が成り立つ
絶対値の定義から、
$-|x| \leqq x \leqq |x|$
$-|y| \leqq y \leqq |y|$ が成り立ちます。
これを辺々足すと、
$-(|x|+|y|) \leqq x+y \leqq |x|+|y|$
これは$x+y$の絶対値が$|x|+|y|$以下であることを表しているのに他ならないです。
よって、$|x+y| \leqq |x|+|y|$です。
これ強くて、何回も使うことで
\begin{eqnarray}
\left|\sum_{j=N+1}^\infty A_j\right| &=& \Big|A_{N+1}+A_{N+2}+A_{N+3}+A_{N+4}+A_{N+5}+\cdots\Big|
\\&\leqq& |A_{N+1}| + \Big|A_{N+2}+A_{N+3}+A_{N+4}+A_{N+5}+\cdots\Big|
\\&\leqq& |A_{N+1}| + |A_{N+2}| + \Big|A_{N+3}+A_{N+4}+A_{N+5}+\cdots\Big|
\\&\leqq& |A_{N+1}| + |A_{N+2}| + |A_{N+3}| + \Big|A_{N+4}+A_{N+5}+\cdots\Big|
\\&\leqq& |A_{N+1}| + |A_{N+2}| + |A_{N+3}| + |A_{N+4}| + \Big|A_{N+5}+\cdots\Big|
\\&\vdots&
\\&\leqq& |A_{N+1}| + |A_{N+2}| + |A_{N+3}| + |A_{N+4}| + |A_{N+5}| + \cdots
\\&=& \sum_{j=N+1}^\infty |A_j|
\end{eqnarray}
ということが証明できます！
(厳密には有限和を考えて絶対値関数の連続性から極限をとって極限の性質から不等式が保存されることを示す)
各項の評価
ということで、
\begin{eqnarray}
\left|\sum_{j=N+1}^\infty A_j\right| &\leqq& \sum_{j=N+1}^\infty |A_j|
\end{eqnarray}
を示せたので、あとは$|A_j|$を上から評価しちゃいましょう！
\begin{eqnarray} |A_j| &=& \left|{}_{p+j-1}C_j(-1)^j\frac1{10^{p+j}}\l{\sum_{m=0}^8 m^j}S^{(p+j)}_{d\!\;\text{桁}}\right| \\&=& \Big|{}_{p+j-1}C_j\Big| \cdot \frac1{10^{p+j}} \cdot \left|\sum_{m=0}^8 m^j \right| \cdot \left|S^{(p+j)}_{d\!\;\text{桁}}\right| \end{eqnarray}
- 1つめ
$\displaystyle \left|\sum_{m=0}^8 m^j\right|$ですが、普通に展開すると
\begin{eqnarray}
\left|\sum_{m=0}^8 m^j\right| &=& \left|0^j+1^j+2^j+3^j+4^j+5^j+6^j+7^j+8^j\right|
\\&=& 0^j+1^j+2^j+3^j+4^j+5^j+6^j+7^j+8^j
\\&\leqq& 8\times8^j
\\&=& 8^{j+1}
\end{eqnarray}
でよさそうです。
- 2つめ
\begin{eqnarray}
\left|S^{(p+j)}_{d\!\;\text{桁}}\right| = \left|\sum_{k\in K_{d\!\;\text{桁}}} \frac1{k^{p+j}}\right| = \sum_{k\in K_{d\!\;\text{桁}}} \frac1{k^{p+j}}
\end{eqnarray}
ですが、$d$桁の数というのは$10^{d-1}$以上ですから、$k$が$K_{d\!\;\text{桁}}$の中の数字なら、
$\frac1k \leqq \frac1{10^{d-1}}$が成り立ちます。
そういえば、$K_{d\!\;\text{桁}}$っていくつ数字があるんでしたっけ？
これは実は上の方でケンプナー級数が収束することの証明の時に求めています。
じゃぁ、結局$d$桁の数字で9のつかないものは、全部で$8\times9^{d-1}$通りあると分かりました！
よって、$8\times9^{d-1}$個の分数があるので、
\begin{eqnarray}
\left|S^{(p+j)}_{d\!\;\text{桁}}\right| &=& \sum_{k\in K_{d\!\;\text{桁}}} \frac1{k^{p+j}}
\\&\leqq& \sum_{k\in K_{d\!\;\text{桁}}} \frac1{\l{10^{d-1}}^{p+j}}
\\&=& \frac1{\l{10^{d-1}}^{p+j}} \cdot 8 \cdot9^{d-1}
\\&=& \frac{9^{d-1}}{\l{10^{p+j}}^{d-1}}\cdot8
\\&=& 8\l{\frac9{10^{p+j}}}^{d-1}
\end{eqnarray}
ふう。上から抑えられました。
- 3つめ
\begin{eqnarray}
\Big|{}_{p+j-1}C_j\Big|
\end{eqnarray}
こいつですが、いい方法がありますよ。
$n$を非負整数、$x$を実数とすると、
\begin{eqnarray}
(1+x)^n = \sum_{i=0}^n {}_nC_i x^i
\end{eqnarray}
が成り立つ。
普通の二項定理を持ってきました。
こいつに、${}_{p+j-1}C_j$を出現させるために、$n=p+j-1$としましょう。
$$(1+x)^{p+j-1} = \sum_{i=0}^{p+j-1} {}_{p+j-1}C_ix^i$$
そして、$x>0$としておきます。そうすれば各項が正になって、こういう風な評価ができます
\begin{eqnarray}
(1+x)^{p+j-1} = \sum_{i=0}^{p+j-1} {}_{p+j-1}C_ix^i > {}_{p+j-1}C_jx^j
\end{eqnarray}
どこかで$i$が$j$と等しくなる時がありますからね。そしてその項以外は正なので、項を一つだけ抜き出してくると必ず小さくなります。
$x^j>0$ですから、両辺を$x^j$で割ってあげましょう。
\begin{eqnarray}
\frac{(1+x)^{p+j-1}}{x^j} &>& {}_{p+j-1}C_j \\
(1+x)^{p-1}\frac{(1+x)^j}{x^j} &>& {}_{p+j-1}C_j \\
(1+x)^{p-1}\l{\frac{1+x}{x}}^j &>& {}_{p+j-1}C_j \\
\end{eqnarray}
こうなりますね。$x$は正なら自由に決めていいです。
じゃぁ全部上から抑えられたことですし、がっちゃんこしてみましょう。
\begin{eqnarray}
|A_j| &=& \Big|{}_{p+j-1}C_j\Big| \cdot \frac1{10^{p+j}} \cdot \left|\sum_{m=0}^8 m^j \right| \cdot \left|S^{(p+j)}_{d\!\;\text{桁}}\right|
\\&<& (1+x)^{p-1}\l{\frac{1+x}{x}}^j \cdot \frac1{10^{p+j}} \cdot 8^{j+1} \cdot 8\l{\frac9{10^{p+j}}}^{d-1}
\\&=& (1+x)^{p-1}\l{\frac{1+x}{x}}^j \cdot \frac1{10^p} \cdot \frac1{10^j} \cdot 8^{j+2} \cdot \l{\frac9{10^p}\cdot\frac1{10^j}}^{d-1}
\\&=& (1+x)^{p-1}\l{\frac{1+x}{x}}^j \cdot \frac1{10^p} \cdot \frac1{10^j} \cdot 8^{j+2} \cdot \frac{9^{d-1}}{10^{p(d-1)}} \cdot \frac1{10^{j(d-1)}}
\\&=& (1+x)^{p-1} \cdot \frac{9^{d-1}}{10^{p(d-1)}} \cdot \l{\frac{1+x}{x}}^j \cdot \frac1{10^j} \cdot 8^{j+2} \cdot \frac1{10^{j(d-1)}}
\\&=& 64 \cdot (1+x)^{p-1} \cdot \frac{9^{d-1}}{10^{p(d-1)}} \cdot \l{\frac{1+x}{x}}^j \cdot 8^j \cdot \frac1{10^{j(d-1)+j}}
\\&=& 64 \cdot (1+x)^{p-1} \cdot \frac{9^{d-1}}{10^{p(d-1)}} \cdot \l{8\cdot\frac{1+x}{x}}^j \cdot \frac1{10^{jd}}
\end{eqnarray}
うーむ。$\displaystyle 8\cdot\frac{1+x}x$をきれいにしたいですね。
$x>0$ですし、$x=8$とでもしますか？
\begin{eqnarray}
&=& 64 \cdot (1+8)^{p-1} \cdot \frac{9^{d-1}}{10^{p(d-1)}} \cdot \l{8\cdot\frac{1+8}8}^j \cdot \frac1{10^{jd}}
\\&=& 64 \cdot 9^{p-1} \cdot \frac{9^{d-1}}{10^{p(d-1)}} \cdot 9^j \cdot \frac1{10^{jd}}
\\&=& 64 \cdot 9^{p-1} \cdot \frac{9^{d-1}}{10^{p(d-1)}} \cdot \frac{9^j}{10^{jd}}
\\&=& 64 \cdot \frac{9^{p-1+d-1}}{10^{p(d-1)}} \cdot \l{\frac9{10^d}}^j
\\&=& 64 \cdot \frac{9^{p+d-2}}{10^{pd-p}} \cdot \l{\frac9{10^d}}^j
\end{eqnarray}
ということで、この評価が出ました
\begin{eqnarray}
|A_j| < 64 \cdot \frac{9^{p+d-2}}{10^{pd-p}} \cdot \l{\frac9{10^d}}^j
\end{eqnarray}
おおお。
各項をまとめ上げる
では、もともとの評価したかった誤差に戻りましょう。$R_N$です。
\begin{eqnarray}
R_N &=& \left|\sum_{j=N+1}^\infty A_j\right|
\\&\leqq& \sum_{j=N+1}^\infty |A_j|
\\&<& \sum_{j=N+1}^\infty 64 \cdot \frac{9^{p+d-2}}{10^{pd-p}} \cdot \l{\frac9{10^d}}^j
\\&=& 64 \cdot \frac{9^{p+d-2}}{10^{pd-p}} \cdot \sum_{j=N+1}^\infty \l{\frac9{10^d}}^j
\end{eqnarray}
最後の部分よく見てみると、等比数列の和になっていますね。$j$乗しかされていないですからね。
実数$a$と実数$r$に対して、$|r|<1$ならば、
\begin{eqnarray}
\sum_{i=0}^\infty ar^i &=& \frac a{1-r}
\end{eqnarray}
そして、$\displaystyle \left|\frac9{10^d}\right| \leqq \frac9{10} < 1$ですから、条件を満たしています。
そして$j$が$N+1$から始まっている件ですが、要は
\begin{eqnarray}
\sum_{j=N+1}^\infty \l{\frac9{10^d}}^j &=& \l{\frac9{10^d}}^{N+1} + \l{\frac9{10^d}}^{N+2} + \l{\frac9{10^d}}^{N+3} + \l{\frac9{10^d}}^{N+4} + \cdots
\end{eqnarray}
つまり初項が$\displaystyle\l{\frac9{10^d}}^{N+1}$で公比が$\displaystyle \frac9{10^d}$である等比数列になっているので、
$j$を$0$から始めるとすると、
\begin{eqnarray}
\sum_{j=0}^\infty \l{\frac9{10^d}}^{N+1}\l{\frac9{10^d}}^j
\end{eqnarray}
こうなります。初項が$\displaystyle\l{\frac9{10^d}}^{N+1}$で公比が$\displaystyle \frac9{10^d}$にちゃんとなっています。
よって公式から、
\begin{eqnarray}
\sum_{j=0}^\infty \l{\frac9{10^d}}^{N+1}\l{\frac9{10^d}}^j &=& \frac{\l{\frac9{10^d}}^{N+1}}{1-\frac9{10^d}}
\\&=& \frac1{1-\frac9{10^d}}\cdot\l{\frac9{10^d}}^{N+1}
\\&=& \frac{10^d}{10^d-9}\cdot\l{\frac9{10^d}}^{N+1}
\\&=& \frac{10^d}{10^d-9}\cdot\frac9{10^d}\cdot\l{\frac9{10^d}}^N
\\&=& \frac{9\cdot10^d}{10^d-9}\cdot\l{\frac9{10^d}}^N
\end{eqnarray}
と分かりました。
これをぶちこんでやると、
\begin{eqnarray}
R_N &<& 64 \cdot \frac{9^{p+d-2}}{10^{pd-p}} \cdot \sum_{j=N+1}^\infty \l{\frac9{10^d}}^j
\\&=& 64 \cdot \frac{9^{p+d-2}}{10^{pd-p}} \cdot \frac{9\cdot10^d}{10^d-9}\cdot\l{\frac9{10^d}}^N
\\&=& 64 \cdot \frac{9^{p+d-2}}{10^{pd-p}} \cdot \frac1{10^{-d}} \cdot \frac{9}{10^d-9}\cdot\l{\frac9{10^d}}^N
\\&=& 64 \cdot \frac{9^{p+d-2}}{10^{pd-p-d}} \cdot \frac{9}{10^d-9}\cdot\l{\frac9{10^d}}^N
\\&=& 64 \cdot \frac{9^{p+d-1}}{10^{pd-p-d}} \cdot \frac1{10^d-9}\cdot\l{\frac9{10^d}}^N
\\&=& \frac{64}{10^d-9} \cdot \frac{9^{p+d-1}}{10^{pd-p-d}} \cdot \l{\frac9{10^d}}^N
\end{eqnarray}
こうなりました。ふぅ。
誤差制御
結局これをどう使うんですかと。
じゃぁ例えば$n$桁の精度でケンプナー級数を求めたいとしましょう。
すると、誤差を$10^{-n}$未満に抑えたいということになりますよね。
ということは、あの$R_N$を$10^{-n}$未満になるように$N$を設定してあげればいいのです
\begin{eqnarray}
R_N &<& 10^{-n}
\end{eqnarray}
しかし$R_N$を直接計算はしにくいので、
\begin{eqnarray}
\frac{64}{10^d-9} \cdot \frac{9^{p+d-1}}{10^{pd-p-d}} \cdot \l{\frac9{10^d}}^N &<& 10^{-n}
\end{eqnarray}
これを満たす$N$を求めましょう！
そうすれば自動的に
\begin{eqnarray}
R_N &<& \frac{64}{10^d-9} \cdot \frac{9^{p+d-1}}{10^{pd-p-d}} \cdot \l{\frac9{10^d}}^N < 10^{-n}
\\R_N &<& 10^{-n}
\end{eqnarray}
と、不等式が満たされますからね。
じゃぁ
\begin{eqnarray}
\frac{64}{10^d-9} \cdot \frac{9^{p+d-1}}{10^{pd-p-d}} \cdot \l{\frac9{10^d}}^N &<& 10^{-n}
\end{eqnarray}
これを満たす$N$なんですが、普通に「$N>$」の形にゴリゴリ変形していきます
\begin{eqnarray}
\frac{64}{10^d-9} \cdot \frac{9^{p+d-1}}{10^{pd-p-d}} \cdot \l{\frac9{10^d}}^N &<& 10^{-n}
\\
\l{\frac9{10^d}}^N &<& 10^{-n} \cdot \frac{10^d-9}{64} \cdot \frac{10^{pd-p-d}}{9^{p+d-1}}
\end{eqnarray}
ここで常用対数を取ります。(底が$10$の対数)両辺正なので大丈夫です。
\begin{eqnarray}
\l{\frac9{10^d}}^N &<& 10^{-n} \cdot \frac{10^d-9}{64} \cdot \frac{10^{pd-p-d}}{9^{p+d-1}}
\\
\log_{10}\l{\l{\frac9{10^d}}^N} &<& \log_{10}\l{10^{-n} \cdot \frac{10^d-9}{64} \cdot \frac{10^{pd-p-d}}{9^{p+d-1}}}
\\
N\log_{10}\l{\frac9{10^d}} &<& \log_{10}\l{10^{-n}} + \log_{10}\l{\frac{10^d-9}{64} \cdot \frac{10^{pd-p-d}}{9^{p+d-1}}}
\\
N\l{\log_{10}\l{9}-\log_{10}\l{10^d}} &<& \log_{10}\l{10^{-n}} + \log_{10}\l{\frac{10^d-9}{64} \cdot \frac1{9^{p+d-1}}}+\log_{10}\l{10^{pd-p-d}}
\\
N\l{\log_{10}\l{9}-d} &<& -n + \log_{10}\l{\frac{10^d-9}{64} \cdot \frac1{9^{p+d-1}}}+pd-p-d
\\\\
N &>& \frac{-n + \log_{10}\l{\frac{10^d-9}{64} \cdot \frac1{9^{p+d-1}}}+pd-p-d}{\log_{10}\l{9}-d}
\\\\
N &>& \frac{pd-p-d-n + \log_{10}\l{\frac{10^d-9}{64} \cdot \frac1{9^{p+d-1}}}}{\log_{10}\l{9}-d}
\\\\
N &>& \frac{n+p+d-pd - \log_{10}\l{\frac{10^d-9}{64} \cdot \frac1{9^{p+d-1}}}}{d-\log_{10}\l{9}}
\end{eqnarray}
あ、そうそう。一個一個はそんなに激しく変形しないようにしています。
式変形というか、項がどう動いたのかは分かりやすいと思いますが、
\begin{eqnarray}
\log_{10}(9)-d
\end{eqnarray}
が、負なのは注意してくださいね。割ると不等号が逆になりますよ。
と、言うことで、
$n$桁のケンプナー級数を求めるのに必要な項数$N$が求められました～～～!!!
ここで「これ、$p$とか$d$が大きいとき右辺が負になるんじゃね？」って思ったやつ、鋭い。
確かに負になります。けど、$p$とか$d$が大きいとき、そもそも
\begin{eqnarray}
S_{d\!\;\text{桁}}^{(p)} = \sum_{k\in K_{d\!\;\text{桁}}} \frac1{k^p}
\end{eqnarray}
ですから、分数がめちゃくちゃ小さくなるんですね。
だからそもそも$S_{d\!\;\text{桁}}^{(p)}$が$10^{-n}$よりも小さくなってるよ、ということを表してるんですねぇ。
だから大丈夫です。
$R_N$が$10^{-n}$未満になるのに十分な$N$の大きさは、
\begin{eqnarray}
N &>& \frac{n+p+d-pd - \log_{10}\l{\frac{10^d-9}{64} \cdot \frac1{9^{p+d-1}}}}{d-\log_{10}\l{9}}
\end{eqnarray}
で与えられる。
あぁあと、一つ忘れてました
ケンプナー級数はもともと、
\begin{eqnarray}
\sum_{k\text{は9がつかない}} \frac1k = \sum_{d=1}^\infty S_{d\!\;\text{桁}}^{(1)}
\end{eqnarray}
ですから、これもいくらまで足せばいいのか確認しないとですね。
でも、上の方でこの場合はやっていて、
\begin{eqnarray}
\left|S^{(p)}_{d\!\;\text{桁}}\right| &=& \sum_{k\in K_{d\!\;\text{桁}}} \frac1{k^{p}}
\\&\leqq& \sum_{k\in K_{d\!\;\text{桁}}} \frac1{\l{10^{d-1}}^{p}}
\\&=& \frac1{\l{10^{d-1}}^{p}} \cdot 8 \cdot9^{d-1}
\\&=& \frac{9^{d-1}}{\l{10^{p}}^{d-1}}\cdot8
\\&=& 8\l{\frac9{10^{p}}}^{d-1}
\end{eqnarray}
と求めていました。($p+j$を$p$に変えています)
例えば$d=1\sim D$まで足すとすると、
真の値との誤差は
\begin{eqnarray}
\left|\sum_{d=1}^\infty S_{d\!\;\text{桁}}^{(1)} - \sum_{d=1}^D S_{d\!\;\text{桁}}^{(1)}\right| &=& \left|\sum_{d=D+1}^\infty S_{d\!\;\text{桁}}^{(1)}\right|
\\&\leqq& \sum_{d=D+1}^\infty \left|S_{d\!\;\text{桁}}^{(1)}\right|
\\&\leqq& \sum_{d=D+1}^\infty 8\l{\frac9{10^{p}}}^{d-1}
\end{eqnarray}
そして、今回$p=1$を考えればいいので、
\begin{eqnarray} \sum_{d=D+1}^\infty 8\l{\frac9{10}}^{d-1} \end{eqnarray}
になります。
これもまた等比数列の和の公式が使えて、
初項が$\displaystyle 8\l{\frac9{10}}^D$で公比が$\displaystyle \frac9{10}$ですから、
\begin{eqnarray} \sum_{d=D+1}^\infty 8\l{\frac9{10}}^{d-1} &=& \frac{8\l{\frac9{10}}^D}{1-\frac9{10}} \\&=& 8\l{\frac9{10}}^D \cdot \frac1{1-\frac9{10}} \\&=& 8\l{\frac9{10}}^D \cdot \frac{10}{10-9} \\&=& 80\l{\frac9{10}}^D \end{eqnarray}
これが$10^{-n}$未満となる$D$まで足せばいいですね！
\begin{eqnarray} 80\l{\frac9{10}}^D < 10^{-n} \end{eqnarray}
常用対数を取ると、
\begin{eqnarray}
80\l{\frac9{10}}^D &<& 10^{-n}
\\
\log_{10}\l{80\l{\frac9{10}}^D} &<& \log_{10}\l{10^{-n}}
\\
\log_{10}(80) + D\log_{10}\l{\frac9{10}} &<& -n
\\
D\l{\log_{10}(9) - \log_{10}(10)} &<& -n - \log_{10}(80)
\\
D\l{\log_{10}(9) - 1} &<& -n - \log_{10}(8) - \log_{10}(10)
\\
D &>& \frac{-n - \log_{10}(8) - 1}{\log_{10}(9) - 1}
\\
D &>& \frac{n + \log_{10}(8) + 1}{1 - \log_{10}(9)}
\end{eqnarray}
と解けました。ふむ。
討伐
じゃぁ、計算してみましょうか。意のままに。
コードをゴリゴリ書いていきます、書きました。
見た目ややこしい
中では必要な$p$を$d$ごとに決めるということをしていたりします。
これは、$d=$指定桁数で、$p=1$というのから漸化式を逆からさかのぼっていけば$p$を出せます。
一度出してみましょうか。
いい感じですね。
問題点と発展
次の記事では、このケンプナー級数を求める関数の問題点と、非ナベアツ数の逆数を求める発展をしていきたいともいます。とりあえずお楽しみに。
参考文献 (References)
- Baillie, R. (1979). "Sums of series of reciprocals of integers missing given digits." Mathematics of Computation, 33(148), 1333–1338.
- Schmelzer, T., & Trefethen, L. N. (2008). "Computing 10,000 digits of the Kempner series." The American Mathematical Monthly, 115(6), 544–561.
- Baillie, R., & Eichhorn, T. (2018). "An efficient algorithm for sums of reciprocals of integers missing specified digits." Journal of Integer Sequences, 21, Article 18.9.3.
- Olver, F. W. J. (1997). Asymptotics and Special Functions. A K Peters/CRC Press.
