京大特色2016-1を和分差分で機械的に解く

京大特色2016-1を機械的に解くために和分差分の記号を導入していく.
和分差分の記号は場所によって揺れがあるために, この記事で用いる記号を定義しておく必要があるのだ.
説明ざっくり, 例多めのイメージで記事を書くことにしたので例をたくさん見てほしい.

以下に差分計算の例を挙げる.
$$\Delta 3 = 0$$
$$\Delta n^2 = (n+1)^2 - n^2 = 2n + 1$$
$$\Delta n(n-1) = (n+1)n-n(n-1)= 2n$$
$$\Delta 2^n = 2^{n+1} - 2^n = 2^n$$
$$\Delta 3^{-n} = 3^{-(n+1)}- 3^{-n} = - \frac 2 3 \cdot 3^{-n}= -2\cdot 3^{-(n+1)} $$
$$\Delta a^n = a^{n+1}- a^n = (a-1)\cdot a^n$$

不定積分のように定数分の任意性があるので和分定数$C$なるものが付属することに注意しておく.
これは和分を差分の逆として定義しているということである.

ちなみに和分定数分のずれを無視すれば, $ \sum \left(\Delta a_n \right)= a_n$ も成立する.

以下に不定和分の例を挙げる.
$$\sum 1 = n + C$$
$$\sum 3n = \frac3 2 n(n-1) + C$$
$$\sum 2^n = 2^n + C$$
$$\sum 3^{-n} = -\frac 3 2 \cdot 3^{-n}$$
$$\sum a^n = \frac 1 {a-1} \cdot a^n \quad (a \not = 1)$$

確かに右辺の差分をとると左辺の中身になっている.

これで和分を使ってシグマ計算することができるようになった.

実際にやってみる.
$$\sum_{n=0}^n 1 = \left[n\right]_0^{n+1}= n+1$$
$$\sum_{n=1}^{10} 3n = \left[\frac3 2 n(n-1)\right]_1^{11}=165 $$
$$\sum_{n=0}^{n-1} 2^n = \left[2^n\right]_0^n = 2^n -1$$
$$\sum_{n=0}^{n-1} 3^{-n} = \left[-\frac 3 2 \cdot 3^{-n}\right]_0^n = -\frac 3 2 \left(3^{-n} -1\right)$$
$$\sum_{n=0}^n a^n = \left[\frac 1 {a-1} \cdot a^n\right]_0^{n+1} = \frac {a^{n+1} - 1} {a-1} \quad (a\ne 1)$$

和分区間の上端を$+1$することを忘れがちなことに注意する.

添字を$n+1$に変更する方の数列はどちらでも良い.
すなわち$\Delta (a_n b_n) = (\Delta a_n)b_{n+1} + a_{n}(\Delta b_n)$も成立する.

実際に$\Delta n(n-1)$を2通りの積の差分で計算して, どちらもが通常の計算結果$2n$と一致することを確認する.
$$\Delta n(n-1) = 1\cdot(n-1) + (n+1)\cdot 1 = 2n$$
$$\Delta n(n-1) = 1\cdot n + n \cdot 1 = 2n$$
確かに一致した.

次の定理/操作は非常に重要で, 和分に対して新しく記号を導入する動機の一つと言えるほどのものである. これは和分なしでも語れるが記法が煩雑になるので, できるだけ和分の枠組みで語りたい.

これを使って実際にいくつか計算してみる.
$$\sum_{k=0}^n k\cdot2^k = \left[k\cdot2^k\right]_0^{n+1} - \sum_{k=0}^n 1\cdot2^{k+1} = (n+1)2^{n+1} - \left[2^{k+1}\right]_{0}^{n+1}= (nー1)\cdot2^{n+1} +2$$
瞬間部分積分を知っている人は次のように計算することもできる.
以降これを瞬間部分和分と呼ぶことにする.
2回目以降積分するときに添字を$+1$しなければならないことに注意する.
$$\sum_{k=0}^n k\cdot2^k = \left[k\cdot2^k - 2^{k+1} \right]_0^{n+1} = (nー1)\cdot2^{n+1} +2$$

もう少し難しい例で計算してみる.

$$ \begin{align} \sum_{k=0}^{n-1} k^2 \cdot 3^{-k} &= \left[ k^2\cdot\left(-\frac 3 2\right)\cdot 3^{-k} -(2k+1)\cdot\left(-\frac 3 2\right)^2 \cdot 3^{-(k+1)} + 2 \cdot \left(-\frac 3 2\right)^3 \cdot 3^{-(k+2)} \right]_0^n \\ &=\left[ -\frac 1 2 (k^2 + k + 1)\cdot 3^{-k+1} \right]_0^n \\ &=-\frac 1 2 (n^2 + n + 1)\cdot 3^{-n+1} + \frac 3 2 \end{align} $$

三角関数の和分についても考えてみる.
これは難しい問題として時折現れる対象で, 機械的に処理できると非常に心強いと思われる.

$\Delta \sin ak = \sin a(k+1) - \sin ak = \left(2\sin \frac a 2\right) \cos a \left(k + \frac 1 2\right)$
$\Delta \cos ak = \cos a(k+1) - \cos ak = -\left(2\sin \frac a 2\right) \sin a\left(k + \frac 1 2\right)$
和積の公式で計算した.
結果を見ると$\sin, \cos$の微分の類似として解釈できることがわかる.
符号の付き方も同じで, どちらも係数として$2\sin \frac a 2$が出てくるだけである.
そしてその逆である和分については以下が従う.

ただし和分定数は省略.

これを使って簡単に計算を3つほどしてみる.

$$\sum_{k=0}^{n-1} \sin \frac {2\pi k}{n} = \left[ -\frac{\cos \frac{2\pi}{n}(k- \frac1 2)} {2\sin \frac \pi n}\right]_0^n =\left(-\frac 1 {2\sin \frac \pi n}\right) \left( \cos \frac{2\pi}{n}\left(n- \frac1 2\right) - \cos \frac{2\pi}{n}\left(- \frac1 2\right) \right) = 0 $$

$$ \sum_{k=0}^{n-1} \cos \frac {\pi k}{n} = \left[ \frac{\sin \frac{\pi}{n}(k- \frac1 2)} {2\sin \frac \pi {2n}}\right]_0^n =\left(\frac 1 {2\sin \frac \pi {2n}}\right) \left( \sin \frac {\pi}{n}\left(n-\frac 1 2\right) - \sin \frac {\pi}{n}\left(-\frac 1 2\right) \right) = 1 $$

$$ \sum_{k=0}^{n-1} \sin \frac {\pi k}{n} = \left[ -\frac{\cos \frac{\pi}{n}(k- \frac1 2)} {2\sin \frac \pi {2n}}\right]_0^n =\left(-\frac 1 {2\sin \frac \pi {2n}}\right) \left( \cos \frac {\pi}{n}\left(n-\frac 1 2\right) - \cos \frac {\pi}{n}\left(-\frac 1 2\right) \right) = \cot \frac \pi {2n} $$

以上の和分差分の知識を以て本題である京大特色2016-1を機械的に解いてみる.

$\mathrm{P,Q,R}$のうち一点を$\mathrm{P_0}$に固定し, 残りの2点を$\mathrm{P_i, P_j}$とする.
そのとき確率は$\frac 1 {n^2}$で, 面積は$ \frac 1 2 \left|\sin\frac{2\pi}{n}i + \sin \frac{2\pi}{n}(j-i) + \sin \frac{2\pi}{n}(n-j) \right|$.
絶対値の中身は$i< j$のとき正, $i>j$のとき負をとることに注意する.
$$\begin{align} E_n &= \frac1 {2n^2} \sum_{0 \leq i,j \leq n-1} \left| \sin\frac{2\pi}{n}i + \sin \frac{2\pi}{n}(j-i) + \sin \frac{2\pi}{n}(n-j) \right| \\ &=\frac1 {n^2} \sum_{0 \leq i < j \leq n-1} \left( \sin\frac{2\pi}{n}i + \sin \frac{2\pi}{n}(j-i) + \sin \frac{2\pi}{n}(n-j) \right) \\ &=\frac3 {n^2} \sum_{0 \leq i < j \leq n-1} \sin\frac{2\pi}{n}i \\ &=\frac3 {n^2} \sum_{0 \leq i \leq n-2} (n-1-i)\sin\frac{2\pi}{n}i \\ &=\frac3 {n^2} \sum_{0 \leq i \leq n-2} i\left(-\sin\frac{2\pi}{n}(i+1)\right) \\ &= \frac 3 {n^2} \left[ i\frac{\cos\frac{2\pi}{n}(i+\frac 1 2)} {2\sin\frac{\pi}{n}} - \frac{\sin\frac{2\pi}{n}(i+1)} {4\sin^2\frac{\pi}{n}} \right]_{i=0}^{n-1} \\ &= \frac 3 {2n^2}\left( (n-1)\cot\frac{\pi}n + \frac{\sin\frac{2\pi}{n}} {2\sin^2\frac{\pi}{n}} \right) \\ &= \frac 3 {2n}\cot\frac{\pi}n \quad \square \end{align}$$
2行目ではi,jの対称性から和をとる区間を変更し, 2倍して絶対値を外した.

3行目では３つの項がそれぞれで足す順番を変えると同じものになることを利用.

5行目ではiの足す順番を最後から足すように変更.

6行目では瞬間部分和分を利用.

機械的に解けるとはいえ, 結局部分和分の計算はミスが発生しやすい(機械的にできるので練習すれば通常の方法よりはミスしにくくなるが)ために, この問題が難しいことに変わりはない.