「Learning Notes」sth about math

from PE441

proof. \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} \epsilon(\gcd(i, j)) \frac{\min(i, n - j)}{ij} = \sum_{\substack{1 \le i < j \le n \\ i \perp j}} \frac{\min(i, n - j)}{ij} = \frac{n}{2} - 1

差分两次即可完成证明。

let\ a_{n} = \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} \epsilon(\gcd(i, j)) \frac{\min(i, n - j)}{ij} = \sum_{\substack{1 \le i < j \le n \\ i \perp j}} \frac{\min(i, n - j)}{ij}

proof.\ a_{n} = \frac{n}{2} - 1

let\ b_{n} = a_{n} - a_{n - 1}

a_{n} = \frac{n}{2} - 1 \iff b_{n} = \frac{1}{2} \cap a_{1} = 0

a_{1} = \sum_{\substack{1 \le i < j \le 1 \\ i \perp j}} \frac{\min(i, n - j)}{ij} = 0

\begin{aligned} b_{n} &= a_{n} - a_{n - 1} \\ &= \sum_{\substack{1 \le i < j \le n \\ i \perp j}} \frac{\min(i, n - j)}{ij} - \sum_{\substack{1 \le i < j \le n - 1 \\ i \perp j}} \frac{\min(i, n - j - 1)}{ij} \\ &= \sum_{\substack{1 \le i < j \le n - 1 \\ i \perp j \\ i + j \geqslant n}} \frac{1}{ij} \end{aligned}

let\ c_{n} = b_{n + 1} - b_{n}

b_{n} = \frac{1}{2} \iff c_{n} = 0 \cap b_{3} = \frac{1}{2}

b_{3} = \sum_{\substack{1 \le i < j \le 2 \\ i \perp j \\ i + j \geqslant 3}} \frac{1}{ij} = \frac{1}{2}

\begin{aligned} c_{n} &= b_{n + 1} - b_{n} \\ &= \sum_{\substack{1 \le i < j \le n \\ i \perp j \\ i + j \geqslant n + 1}} \frac{1}{ij} - \sum_{\substack{1 \le i < j \le n - 1 \\ i \perp j \\ i + j \geqslant n}} \frac{1}{ij} \\ &= \sum_{\substack{1 \le i < n \\ i \perp n}} \frac{1}{ni} - \sum_{\substack{1 \le i < j \le n - 1 \\ i \perp j \\ i + j = n}} \frac{1}{ij} \\ &= \sum_{\substack{1 \le i < n \\ i \perp n}} \frac{1}{ni} - \sum_{\substack{1 \le i < n - i \le n - 1 \\ i \perp (n - i)}} \frac{1}{i(n - i)} \\ &= \sum_{\substack{1 \le i < n \\ i \perp n}} \frac{1}{ni} - \sum_{\substack{1 \le i < n - i \le n - 1 \\ i \perp n}} \frac{1}{i(n - i)} \\ \end{aligned}

\because \frac{1}{nk} + \frac{1}{n(n - k)} = \frac{1}{k(n - k)}

\begin{aligned} c_{n} &= \sum_{\substack{1 \le i < n \\ i \perp n}} \frac{1}{ni} - \sum_{\substack{1 \le i < n - i \le n - 1 \\ i \perp n}} \frac{1}{i(n - i)} \\ &= \sum_{\substack{1 \le i < n \\ i \perp n}} \frac{1}{ni} - \sum_{\substack{1 \le i < n - i \le n - 1 \\ i \perp n}} \left(\frac{1}{ni} + \frac{1}{n(n - i)}\right) \\ &= 0 \end{aligned}