Σ[k=1→n][√k] - RPGツクールと数学のブログ

過去ブログの転載です。

$\displaystyle \sum_{k=1}^{n} \left\lfloor \sqrt{k} \right\rfloor$ を求める方法の考え方です。 $\displaystyle \left\lfloor \cdot \right\rfloor$ は切り捨てを意味します。この場合は整数部分といっても正しいです。

要するに次のような値の総和を求める手続きです。

$\displaystyle \left\lfloor \sqrt{1} \right\rfloor = \left\lfloor 1 \right\rfloor = 1$
$\displaystyle \left\lfloor \sqrt{2} \right\rfloor = \left\lfloor 1.414\cdots \right\rfloor = 1$
$\displaystyle \left\lfloor \sqrt{3} \right\rfloor = \left\lfloor 1.732\cdots \right\rfloor = 1$
$\displaystyle \left\lfloor \sqrt{4} \right\rfloor = \left\lfloor 2 \right\rfloor = 2$
$\displaystyle \left\lfloor \sqrt{5} \right\rfloor = \left\lfloor 2.236\cdots \right\rfloor = 2$

……

求めるのは一見するととても難しそうですが、数値の見方を変えると捉えやすくなります。

f:id:fermiumbay13:20190802011616p:plain

シグマのイメージですと上の図において左から順に縦に数えていくイメージになりますが、そうじゃなくて色分けしたように横に数えていくようにするわけです。
1＋1＋1＋2＋2＋2＋2＋2＋3＋3＝19とするのでなく、青が10個、緑が7個、黄色が2個だから、10＋7＋2＝19　この方がなんだかラクですよね。
$\displaystyle \left\lfloor \sqrt{n} \right\rfloor$ は単調増加でしかも1つずつ上がっていきますから、初めて値が上がるときの $n$ の値を控えておけばそれを使って簡単に求まるわけです。

そこで、初めて $a_{n}$ になるときの $n$ の値を $b_{a_{n}}$ と書きます。図で表した地点ですね。

$a_{n}$ が初めて $1$ になるのは $n=1$ なので、 $b_{1}=1$
$a_{n}$ が初めて $2$ になるのは $n=4$ ですから、 $b_{2}=4$
初めて $3$ になるのは $n=9$ だから、 $b_{3}=9$
……というかんじです。

なんとなく類推できると思いますけど、 $b_{n}=n^{2}$ っぽいですね。後で示します。

$b_{n}$ の値を使えば、さっきの総和は次のようにして求まります。

$\displaystyle \sum_{k=1}^{10} \left\lfloor \sqrt{k} \right\rfloor$
$\displaystyle =(11-b_{1})+(11-b_{2})+(11-b_{3})$ （← 青＋緑＋黄色）
$\displaystyle =(11-1)+(11-4)+(11-9)$
$\displaystyle =10+7+2=19$

まずは $b_{n}$ を求めましょう。 $n^{2}$ になるんですけどね。

$a_{n}=\left\lfloor \sqrt{n} \right\rfloor$ より、 $\sqrt{n}-1 \lt a_{n} \le \sqrt{n}$ と表せます。切り捨てだから当然ですね。以下参考です：

床関数と天井関数 - Wikipedia

これを $n$ について解くことを考えます。

$\displaystyle \sqrt{n}-1 \lt a_{n} \le \sqrt{n}$
$\displaystyle -1-a_{n} \lt -\sqrt{n} \le -a_{n}$
$\displaystyle a_{n} \le \sqrt{n} \lt a_{n}+1$
$\displaystyle a_{n}^{2} \le n \lt (a_{n}+1)^{2}$

つまり、 $n$ の最小値は $a_{n}^{2}$ ということになりますから、 $b_{a_{n}}=a_{n}^{2}$ ということになることより、 $b_{n}=n^{2}$ が示されます。

$b_{n}$ が求まれば、あとはさっきの方法を一般の $n$ についてできるようにするだけです。

1から10までの和の場合は $b_{3}$ まで使いましたが、図からもわかるように1から $n$ までの和の場合は $b_{\left\lfloor \sqrt{n} \right \rfloor}$ まで使うことになりますね。

従って、 $\displaystyle \sum_{k=1}^{n} \left\lfloor \sqrt{k} \right\rfloor = \sum_{k=1}^{\left\lfloor \sqrt{n} \right\rfloor} (n+1-b_{k})$ と書けます。あとは展開ですね。

$\displaystyle \sum_{k=1}^{\left\lfloor \sqrt{n} \right\rfloor} (n+1-b_{k})$
$\displaystyle =\sum_{k=1}^{\left\lfloor \sqrt{n} \right\rfloor} (n+1-k^{2})$
$\displaystyle =\left\lfloor \sqrt{n} \right\rfloor (n+1) - \sum_{k=1}^{\left\lfloor \sqrt{n} \right\rfloor} k^{2}$
$\displaystyle =\left\lfloor \sqrt{n} \right\rfloor (n+1) - \frac{1}{6} \left\lfloor \sqrt{n} \right\rfloor (\left\lfloor \sqrt{n} \right\rfloor + 1)(2\left\lfloor \sqrt{n} \right\rfloor + 1)$
$\displaystyle =\left\lfloor \sqrt{n} \right\rfloor \left\{ (n+1) - \frac{1}{6} (\left\lfloor \sqrt{n} \right\rfloor + 1)(2\left\lfloor \sqrt{n} \right\rfloor + 1) \right\}$
$\displaystyle =\frac{1}{6} \left\lfloor \sqrt{n} \right\rfloor \left\{ 6n+6 - (2\left\lfloor \sqrt{n} \right\rfloor ^{2} + 3\left\lfloor \sqrt{n} \right\rfloor + 1) \right\}$
$\displaystyle =\frac{1}{6} \left\lfloor \sqrt{n} \right\rfloor ( 6n - 2\left\lfloor \sqrt{n} \right\rfloor ^{2} - 3\left\lfloor \sqrt{n} \right\rfloor + 5)$

となります。

よって
$\displaystyle \sum_{k=1}^{n} \left\lfloor \sqrt{k} \right\rfloor=\frac{1}{6} \left\lfloor \sqrt{n} \right\rfloor ( 6n - 2\left\lfloor \sqrt{n} \right\rfloor ^{2} - 3\left\lfloor \sqrt{n} \right\rfloor + 5)$
となります。案外きれいになりませんでしたね。