この記事は
・
k-ナッチ数列の部分和からなる数列の一般項についての予想
・
k-ナッチ数列の部分和からなる数列の一般項についての予想(その2・厳密解との関係)
・
k-ナッチ数列の部分和からなる数列の一般項についての予想(その3・確率論からのアプローチ)
の続きの記事になります。まだ読んでいない方はそちらを先に読んでみてください。
予想の内容を再掲します。
${\displaystyle \begin{align} S_k(n) &= \left\lfloor \frac{A_k^{n+1}}{C_k} -\frac{1}{k-1} \right\rceil \end{align} }$
ただし、$A_k,C_k$は次の定数である。
$f_k(x)=x^k-x^{k-1}-x^{k-2}-\cdots-x^2-x-1$
として、
${\displaystyle A_k\cdots\cdots f_k(x)=0\text{ の正の実数解} }$
${\displaystyle \begin{align} C_k &=(A_k-1)f_k'(A_k) \end{align} }$
次のようにいくつかの関数を定義します。
$a_k(n)$ を $k$-ナッチ数列の第 $n$ 項として、
${\displaystyle S_k(n):=\sum_{i=0}^{n} a_k(i)}$
式を見やすくするため、次の関数を定義します。
${\displaystyle Q_k(n):=\frac{A_k^{n+1}}{C_k}
-\frac{1}{k-1}}$
誤差の数列 $\{R_k(n)\}$ を次のように定義します。
$R_k(n):=S_k(n)-Q_k(n)$
$\left\lfloor x\right\rceil$は四捨五入を表す関数です。すなわち
${\displaystyle \left\lfloor x\right\rceil=\left\lfloor x+\frac{1}{2}\right\rfloor}$
今回は、前回残った「示すべきこと」の部分を示して、証明を完成させます。
$0\le n \le k-1$ のとき
$\left|R_k(n)\right|<\frac{1}{2}$
以下の記事では特に断りがない限り $k$ は 2以上の整数、$n$ は0以上の整数とします。
※ 些末な部分は省略していますので適宜補完してください。
$S_k(0)=S_k(1)=\cdots=S_k(k-2)=0,$
$S_k(k-1)=1$
ですから、次のことを証明すればよいことになります。
${\displaystyle \begin{align} -\frac{1}{2}\le Q_k(n) <\frac{1}{2} &\qquad(0\le n\le k-2)\\ \frac{1}{2}\le Q_k(n) <\frac{3}{2} &\qquad(n= k-1) \end{align} }$
評価すべき式は単調増加であることを考慮すれば、次の命題3を証明すれば命題2も証明できますので、今から命題3を順に証明していきます。
${\displaystyle \begin{align} (1)&\qquad -\frac{1}{2}< Q_k(0)\\\\ (2)&\qquad Q_k(k-2)<\frac{1}{2}\\\\ (3)&\qquad \frac{1}{2}< Q_k(k-1)\\\\ (4)&\qquad Q_k(k-1)<1 \end{align} }$
(i) $k=2$ のとき
${\displaystyle Q_2(0)=\frac{\varphi^2}{\sqrt{5}}-1
=0.17\cdots
>-\frac{1}{2}}$
(ii) $k\ge 3$ のとき
${\displaystyle \frac{A_k}{C_k}>0}$ であり、${\displaystyle \frac{1}{k-1}<\frac{1}{2}}$ であるから、
${\displaystyle Q_k(0)=\frac{A_k}{C_k} -\frac{1}{k-1}>-\frac{1}{2}}$
したがってすべての $k$ について $-\frac{1}{2}\le Q_k(0)$ が成り立つ。
(i)$k=2$ のとき
$Q_2(0)=0.17\cdots<\frac{1}{2}$
(i)$k=3$ のとき
$Q_3(1)=0.23\cdots<\frac{1}{2}$
(i)$k\ge4$ のとき
${\displaystyle \begin{align} C_k &=(A_k-1)f_k'(A_k)\\ &=(A_k-1)\cdot\frac{(k+1)A_k^k-2kA_k^{k-1}}{A_k-1}\\ &=((k+1)A_k-2k)A_k^{k-1} \end{align} }$
${\displaystyle \begin{align} Q_k(k-2)&=\frac{A_k^{k-1}}{C_k}-\frac{1}{k-1}\\ &=\frac{1}{((k+1)A_k-2k)}-\frac{1}{k-1}\\ &=\frac{(k-1)-((k+1)A_k-2k)}{((k+1)A_k-2k)(k-1)}\\ \end{align} }$
ここで
$(k+1)A_k-2k>0$
であることはわかっているから、
(参考:
k-ナッチ数列の四捨五入表示についての考察(ほぼ証明)
)
${((k+1)A_k-2k)(k-1)}>{2((k-1)-((k+1)A_k-2k))}$
を示せばよい。
左辺-右辺は
${\displaystyle
\begin{align}
&((k+1)A_k-2k)(k-1)-2((k-1)-((k+1)A_k-2k))\\
&= A_k (k + 1)^2-2 (k^2 + 2 k - 1) \\
&=(k+1)^2\left(
A_k-\left(2-\frac{4}{(k+1)^2}\right)
\right)
\end{align}}$
となるから、結局
${\displaystyle A_k>2-\frac{4}{(k+1)^2}}$
を示せばよい。
$k\ge4$ のときは
$2(1-2^{-k})>2-\frac{4}{(k+1)^2}$ であり、
$A_k>2(1-2^{-k})$ とわかっているから、
(参考:
k-ナッチ数列の四捨五入表示についての考察(ほぼ証明)
)
${\displaystyle A_k>2(1-2^{-k})>2-\frac{4}{(k+1)^2}}$
となり、これが示すべきことであった。
(i)$k=2$ のとき
$Q_2(1)=0.89\cdots>\frac{1}{2}$
(ii)$k\ge3$ のとき
${\displaystyle
\begin{align}
Q_k(k-1)&=\frac{A_k}{((k+1)A_k-2k)}-\frac{1}{k-1}\\
&=\frac{2(k-A_k)}{((k+1)A_k-2k)(k-1)}\\
\end{align}
}$
したがって
$((k+1)A_k-2k)(k-1)<4(k-A_k)$
を示せばよい。
左辺-右辺は
${\displaystyle
\begin{align}
&((k+1)A_k-2k)(k-1)-4(k-A_k)\\
&=A_k (k^2 + 3)-2 k (k + 1)\\
&= (k^2 + 3)\left(
A_k-\left(2+\frac{2k-6}{k^2+3}
\right)
\right)\\
&<0
\end{align}
}$
となり、これが示すべきことであった。
(i)$k\le4$ のとき
$Q_2(1)=0.89\cdots<1$
$Q_3(2)=0.85\cdots<1$
$Q_4(3)=0.84\cdots<1$
(ii)$k\ge5$ のとき
${\displaystyle
\begin{align}
Q_k(k-1)
&=\frac{2(k-A_k)}{((k+1)A_k-2k)(k-1)}\\
\end{align}
}$
であるから
$((k+1)A_k-2k)(k-1)>2(k-A_k)$
を示せばよい。
左辺-右辺は
${\displaystyle
\begin{align}
&((k+1)A_k-2k)(k-1)-2(k-A_k)\\
&=A_k (k^2 + 1) - 2 k^2\\
&= (k^2 + 1)\left(
A_k-\left(2-\frac{2}{k^2 + 1}
\right)
\right)\\
\end{align}
}$
となるから、結局
${\displaystyle A_k>2-\frac{2}{k^2 + 1}}$
を示せばよい。
$k\ge5$ のときは
${\displaystyle 2(1-2^{-k})>2-\frac{2}{k^2 + 1}}$ であり、
$A_k>2(1-2^{-k})$ とわかっているから、
(参考:
k-ナッチ数列の四捨五入表示についての考察(ほぼ証明)
)
${\displaystyle A_k>2(1-2^{-k})>2-\frac{2}{k^2 + 1}}$
となり、これが示すべきことであった。
以上より、命題3が真であるから、命題2も真であり、さらには命題1も真である。
したがって、確率論からのアプローチにより、予想が正しいことが証明された。
これで予想が正しいことが証明できました!
${\displaystyle \begin{align} S_k(n) &= \left\lfloor \frac{A_k^{n+1}}{C_k} -\frac{1}{k-1} \right\rceil \end{align} }$
ただし、$A_k,C_k$は次の定数である。
$f_k(x)=x^k-x^{k-1}-x^{k-2}-\cdots-x^2-x-1$
として、
${\displaystyle A_k\cdots\cdots f_k(x)=0\text{ の正の実数解} }$
${\displaystyle \begin{align} C_k &=(A_k-1)f_k'(A_k) \end{align} }$
途中で気が付いたのですが、
${\displaystyle f_k'(A_k)=\frac{(k+1)A_k^k-2kA_k^{k-1}}{A_k-1}}$
を使うと導関数を使わない表現に書き換えることができます。
${\displaystyle \begin{align} S_k(n) &= \left\lfloor \frac{A_k^{n-k+2}}{(k+1)A_k-2k} -\frac{1}{k-1} \right\rceil \end{align} }$
ただし、$A_k$は ${\displaystyle x^k-x^{k-1}-x^{k-2}-\cdots-x^2-x-1=0\text{ の正の実数解} }$
さて、今回証明した式に使い道はあるでしょうか。例えば、「トリボナッチ数列の初項から第$9999999999999999$項までの和」の桁数を簡単に計算できます。
${\displaystyle \begin{align} &\log_{10} S_3(9999999999999999)\\ &\fallingdotseq \log_{10} \frac{A_3^{10000000000000000}}{C_3}\\ &=10000000000000000\log_{10} A_3-\log_{10} C_3\\ &=2646494434842508.05\cdots \end{align} }$
$2646494434842509$桁となりました。
計算精度を上げれば、桁数だけでなく上位の数字も計算できます。
これを漸化式から再帰的に計算すると、かなりの時間がかかることでしょう。
このように、「急いでトリボナッチ数列の初項から第$9999999999999999$項までの和を調べなくてはならなくなったとき」などに役立つと思います!
ここまでお付き合いいただきありがとうございました。