[时间复杂度 Time Complexity of Algorithms

神犇说世上的美有三种,一是优美精致的数据结构,二是巧夺天工的神奇算法,三是你温暖世界的笑容

计算机之所以叫做计算机,就是因为它在“计算”这一件事上做的可以比人类快。而我们的任务,就是告诉计算机要如何去进行一个计算,也就是要实现一个算法。
想要让程序更快,除了要提升计算机处理器的运行速度之外,最重要的就是要提升算法的效率,以及算法的在这个计算机上实现的的速度。
做同样的一件事情,可以有无数种做法。比如说给一些数字排序,就有好几种做法。那么要怎么比较他们的速度呢?
最直观的做法自然是写出对应的程序,给定一个输入,然后比较一下他们的运行时间。这样的做法简单粗暴,然而并不能给我们关于这些算法的更多信息,也只能反映这些算法在这个特定输入的情况,误差也不容小视。
更为严谨的做法,是对这个算法进行数学上的分析,以得出这个算法在理论上的运行效率。
以选择排序为栗子把
(然后把栗子剥开吃掉~

来看看他的运行原理
选择排序
第零轮从所有的n个数据中找出最小的,需要对每个\(j\in \left ( 0,n \right )\)进行一次比较,共n-1次
第一轮从剩下的n-1个数据中找出最小的,需要对\(j\in \left ( 1,n \right )\)每个进行一次比较,共n-2次
……
第i轮从剩下的n-i个数据中找出最小的,需要对\(j\in \left ( i,n \right )\)每个进行一次比较,共n-i-1次
第n-2轮从剩下的2个数据中找出最小的,需要进行一次比较

总共需要进行 \(\sum_{k = 1}^{n-1} k=\frac{n\left ( n-1 \right )}{2}\)次比较
然后每轮需要对数据进行一次交换,合计是\(\left ( n-1 \right )\)次交换
也就是说,这个程序所需要运行的时间大致上是
\(T=\frac{n\left ( n-1 \right )}{2}T_{0}+\left ( n-1 \right )T_{1}\),其中\(T_{0}\)为一次比较需要的时间,\(T_{1}\)为一次交换所需要的时间
当n很大的时候,对T的量级起到决定性作用的将会是什么呢?
(还记得函数在无穷大的极限吗?
n趋向于无穷大时,起作用的将会是n的二次项,也就是\(\frac{n^{2}}{2}T_{0}\)
那么可以看出,选择排序的算法的运行时间在n充分大的时候,大致正比于\(n^{2}\)
继续阅读

[Dr.Lib]Note:Math – Elegant Proof II

北京数竞 1957

平面上任取三个格点, 试证:它们不能是正三角形三个顶点

证明:

设三个点分别为\(  A(x_{1},y_{1}),B(x_{2},y_{2}),C(x_{3},y_{3})\)则
\( S_{\Delta ABC}=\frac{1}{2}\begin{Vmatrix}\
x_1&y_1 &1 \\
x_2&y_2 &1 \\
x_3&y_3 &1 \
\end{Vmatrix}\)为有理数,而

\( S_{\Delta ABC}=\frac{\sqrt{3}}{4}((x_1-x_2)^2+(y_1-y_2)^2)\)为无理数,矛盾。

49th Moscow MO 1986

求证:对于实数\(x,y,z\),以下三个式子不可能同时成立。

\( \left | x \right | < \left | y-z \right | , \left | y \right | < \left | z-x \right |, \left | z \right | < \left | x-y \right | \)

证明:

反证法。若三式全部成立,有

\[\left\{\begin{matrix}x^2<(y-z)^2 \
\\ y^2<(z-x)^2
\\ z^2<(x-y)^2 \
\end{matrix} \right. \
\rightarrow \left\{\begin{matrix}(x-y+z)(x+y-z)<0 \
\\ (y-z+x)(y+z-x)<0
\\ (z-x+y)(z+x-y)<0 \
\end{matrix}\right.\]

三式相乘

\(((x+y-z)(y+z-x)(z+x-y))^2<0\)矛盾。

St.Petersburg MO 1988

是否存在两个不等于0的整数\(x,y\),满足其中之一可被它们的和整除,另一个可被差整除?

解答:

不存在。

否则,\(\left |x+y \right |\)、\(\left |x-y \right |\) 必有一个既大于x又大于y。它不可能是\(x\)或\(y\)的约数,矛盾。

 

[Dr.Lib]Note:Math – Elegant Proof I

16th CanadianMO 1984

任给7个实数,求证必有两个数x、y满足:

\[0 \leq\frac{x – y}{1+x y} \leq\frac{\sqrt{3}}{3} \]

拿到题目后第一反应就是和什么公式好像……结果还真是……

证明:

设七个数为\(a_{1}< a_{2}< a_{3}< a_{4}< a_{5}< a_{6}<a_{7}\),令\(\theta _{i}=arctan(a_{i})\)。

有\( \frac{-\pi}{2}<\theta _{1}<\theta _{2}<\theta _{3}<\theta _{4}<\theta _{5}<\theta _{6}<\theta _{7}<\frac{\pi}{2}\)

则必有\( 0<\theta _{i+1}-\theta _{i}\leq \frac{-\pi}{6} i \in \left [ 1,6 \right ] \)

则\( 0<tan(\theta _{i+1}-\theta _{i})= \frac{tan(\theta _{i+1})-tan(\theta _{i})}{1+tan(\theta _{i})tan(\theta _{i+1})}\leq \frac{\sqrt{3}}{3} \)即\[0 \leq \frac{x – y}{1+x y} \leq \frac{\sqrt{3}}{3} \]

练习:

50th Moscow MO 1987 求证:从任意三个正数或四个实数中总能取两个数x,y满足 \[0 \leq \frac{x – y}{1+x y} \leq 1 \]

3th CMO WC 1988

(1)设正数a,b,c满足 \((a^{2}+b^{2}+c^{2})^{2}>2(a^{4}+b^{4}+c^{4})\)

求证:a,b,c是三角形的三边。

(2)设\((a_{1}^{2}+a_{2}^{2}+a_{3}^{2}+ … +a_{n}^{2})^{2}>(n-1)(a_{1}^{4}+a_{2}^{4}+…+a_{n}^{4}) n\geq3\),求证:\({a_{n}}\)中任意三个数是三角形的三边。

看起来就是各种因式分解。。

证明:

(1)

由题意得\(2a^{2}b^{2}+2b^{2}c^{2}+2a^{2}c^{2}-a^{4}-b^{4}-c^{4}>0\)

即\((a+b-c)(a+c-b)(b+c-a)(a+b+c)>0\)

不妨设\(a\geq b \geq\ c\)

有\((b+c-a)>0\)即a,b,c是三角形的三边。

(2)

\(n=3\)时由(1)立即可得。

\(n>3\)时

\[(n-1)(a_{1}^{4}+a_{2}^{4}+…+a_{n}^{4}) \]
\[<(a_{1}^{2}+a_{2}^{2}+a_{3}^{2}+ … +a_{n}^{2})^{2} \]
\[=(\frac{a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}{2}+\frac{a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}{2}+ … +a_{n}^{2})^{2} \]
\[\leq (n-1)(\frac{(a_{1}^{2}+a_{2}^{2}+a_{3}^{2})^{2}}{4}+\frac{(a_{1}^{2}+a_{2}^{2}+a_{3}^{2})^{2}}{4}+a_{4}^{4}+…+a_{n}^{4}) (柯西不等式) \]
\[=(n-1)(\frac{(a_{1}^{2}+a_{2}^{2}+a_{3}^{2})^{2}}{2}+a_{4}^{4}+…+a_{n}^{4})\]

所以

\((a_{1}^{2}+a_{2}^{2}+a_{3}^{2})^{2}>2(a_{1}^{4}+a_{2}^{4}+a_{3}^{4})\)

由(1)知\(a_{1},a_{2},a_{3}\)是三角形的三边。

由对称性可知,\({a_{n}}\)中任意三个数是三角形的三边。

【To be continued】

[Dr.Lib]Note:Math – \(\Sigma \frac{1}{n^{2}}\)

转载自http://www.ivy-end.com/archives/1098


今天我们来介绍一个曾经在数列题中做过无数遍的数列\(a_{n}=\frac{1}{n^{2}}\),为了方便下文的讨论,我们记\(S_{n}\)为数列\(a_{n}\)的前\(n\)项和。我们做过最熟悉的题目莫过于证明\(S_{n}<2\),这个证明对于大家来说应该是非常容易的\[S_{n}=\sum_{i=1}^{n}\frac{1}{i^{2}}=1+\sum_{i=2}^{n}\frac{1}{i\cdot\left(i-1 \right )}=2-\frac{1}{n}.\]

那么大家是否考虑过,\(\lim_{n \to \infty }S_{n}\)究竟等于多少?我记得严桂华讲过欧拉曾经计算过这个问题,今天在国外一个数学讨论网站上翻到了一篇关于如何计算\(\lim_{n \to \infty }S_{n}\)的问答(原文地址)。在此仅介绍几种方法。

首先给出结果,再用多种方法进行证明\[\lim_{n \to \infty }S_{n}=\frac{\pi^{2}}{6}.\]不得不说,这一结果是非常不可思议的,因为它居然包含了\(\pi\)。读者如果不相信的话,可以自行计算一下,当\(n\)趋向于正无穷时,答案便越接近\(\frac{\pi^{2}}{6}\)。

好了,废话不说,我们进入证明部分。

法一:

当\(0<x<\frac{\pi}{2}\)时,有\(0<\sin{x}<x<\tan{x}\)。至于这个命题的证明,请参考下图:

Mathematics 003-1-1

这样,我们可以得到\[\frac{1}{\tan^{2}{x}}<\frac{1}{x^{2}}<\frac{1}{\sin^{2}{x}}.\]我们知道,\(\frac{1}{\tan^{2}{x}}=\frac{1}{\sin^{2}{x}}-1\)(很容易由三角恒等式导出)。将区间\(\left(0,\frac{\pi}{2}\right)\)等分成\(2^{n}\)个部分,令\(x_{k}=\frac{\pi}{2}\cdot\frac{k}{2^{n}}\),并将不等式两边对\(x_{k}\)进行求和,可以得到\[\sum_{k=1}^{2^n-1} \frac{1}{\sin^2 x_k} – \sum_{k=1}^{2^n-1} 1 < \sum_{k=1}^{2^n-1} \frac{1}{x_k^2} < \sum_{k=1}^{2^n-1} \frac{1}{\sin^2 x_k}.\]我们不妨将不等式右边的表达式记为\(T_{n}\),那么原不等式可以化简为\[T_{n} – \left(2^n – 1\right) < \sum_{k=1}^{2^n-1} \left( \frac{2 \cdot 2^n}{\pi} \right)^2 \frac{1}{k^2} < T_n.\]接下来我们主要考察\(T_{n}\)。它看起来是一个非常复杂的求和,实际上可以非常简单的计算出来。首先,我们考虑下面的式子\[\frac{1}{\sin^2 x} + \frac{1}{\sin^2 (\frac{\pi}{2}-x)} = \frac{\cos^2 x + \sin^2 x}{\cos^2 x \cdot \sin^2 x} = \frac{4}{\sin^2 2x}.\]因此,如果我们将\(T_{n}\)以\(\frac{\pi}{4}\)为中点进行配对(选取区间\(\left(0,\frac{\pi}{2}\right)\)左边的点\(x_{k}\),与右边的点\(\frac{\pi}{2}-x_{k}\)),考虑递推,再加上中点\(\frac{1}{\sin^{2}{\frac{\pi}{4}}}=2\),则可以得到\[T_{n}=4T_{n-1}+2.\]又\(T_{1}=2\),我们可以很容易的得到\(T_{n}\)的通项公式\[T_n = \frac{2(4^n-1)}{3}.\]于是,我们得到了这样的不等式\[\frac{2(4^n-1)}{3} – (2^n-1) \leq \frac{4^{n+1}}{\pi^2} \sum_{k=1}^{2^n-1} \frac{1}{k^2} \leq \frac{2(4^n-1)}{3}.\]两边同时乘以\(\frac{\pi^{2}}{4^{n+1}}\)使得不等式的中间与我们的目标形式更加相似,这样我们又得到一个不等式\[\frac{\pi^{2}}{4^{n+1}} \cdot \frac{2(4^n-1)}{3} – (2^n-1) \leq \sum_{k=1}^{2^n-1} \frac{1}{k^2} \leq\frac{\pi^{2}}{4^{n+1}} \cdot \frac{2(4^n-1)}{3}.\]当\(n\rightarrow\infty\)时,不等式左右两边同时趋向于\(\frac{\pi^{2}}{6}\),由夹逼准则得\(\lim_{n \to \infty }S_{n}=\frac{\pi^{2}}{6}\)。证毕。

法二:

我们可以借助函数\(f\left(x\right)=x^{2},x\in\left[-\pi,\pi\right]\)来找到它对应的三角傅立叶级数\[\frac{a_{0}}{2}+\sum_{n=1}^{\infty }(a_{n}\cos nx+b_{n}\sin x),\]且它是周期收敛的。

又\(f\left(x\right)\)为偶函数,这足够让我们得到它的系数\[a_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }f(x)\cos nx\;dx\qquad n=0,1,2,3,\cdots,\]因为\[b_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }f(x)\sin nx\;dx=0\qquad n=1,2,3,\cdots.\]令\(n=0\)得\[a_{0}=\frac{1}{\pi }\int_{-\pi }^{\pi }x^{2}dx=\frac{2}{\pi }\int_{0}^{\pi}x^{2}dx=\frac{2\pi ^{2}}{3}.\]当\(n=1,2,3,\cdots\)时,我们有\[a_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }x^{2}\cos nx\;dx\\=\frac{2}{\pi }\int_{0}^{\pi }x^{2}\cos nx\;dx=\frac{2}{\pi }\times \frac{2\pi }{n^{2}}(-1)^{n}=(-1)^{n}\frac{4}{n^{2}},\]因为\[\int x^2\cos nx\;dx=\frac{2x}{n^{2}}\cos nx+\left( \frac{x^{2}}{n}-\frac{2}{n^{3}}\right) \sin nx.\]因此\[f(x)=\frac{\pi ^{2}}{3}+\sum_{n=1}^{\infty }\left( (-1)^{n}\frac{4}{n^{2}}\cos nx\right).\]又\(f\left(\pi\right)=\pi^{2}\),我们可以得到\[\pi ^{2}=\frac{\pi ^{2}}{3}+\sum_{n=1}^{\infty }\left( (-1)^{n}\frac{4}{n^{2}}\cos \left( n\pi \right) \right)\]即\[\pi ^{2}=\frac{\pi ^{2}}{3}+4\sum_{n=1}^{\infty }\left( (-1)^{n}(-1)^{n}\frac{1}{n^{2}}\right)\]进一步化简得\[\pi ^{2}=\frac{\pi ^{2}}{3}+4\sum_{n=1}^{\infty }\frac{1}{n^{2}}.\]因此\[\sum_{n=1}^{\infty }\frac{1}{n^{2}}=\frac{\pi ^{2}}{4}-\frac{\pi ^{2}}{12}=\frac{\pi ^{2}}{6}.\]证毕。

法三:

当\(x=0\)时\(\sin{x}\)可以使用泰勒级数展开\[\sin x = x – \frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots.\]于是我们可以得到\[\frac{x^3}{3!}=x\left(\frac{x^2}{\pi^2} + \frac{x^2}{2^2\pi^2}+ \frac{x^2}{3^2\pi^2}+\cdots\right)=x^3\sum_{n=1}^{\infty}\frac{1}{n^2\pi^2},\]即\[\sum_{n=1}^\infty\frac{1}{n^2}=\frac{\pi^2}{6}.\]证毕。

法四:

设\(z\)为复数,考虑\[\frac{\pi^2}{\sin^2\pi z}=\sum_{n=-\infty}^{\infty}\frac{1}{(z-n)^2}\]由复变函数分析可得\[\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}=\sum_{n=1}^{\infty}\frac{1}{(z-n)^2}+\sum_{n=1}^{\infty}\frac{1}{(z+n)^2}.\]这样,当右边\(z=0\)时,我们就可以得到\[\lim_{z\to 0}\left(\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}\right)=2\sum_{n=1}^{\infty}\frac{1}{n^2}.\]又\[\lim_{z\to 0}\left(\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}\right)=\frac{\pi^2}{3}.\]因此\[\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}.\]证毕。

法五:

这是欧拉的方法。令\[s=\sin^{-1}{x}.\]那么\[\int_{0}^{\frac{\pi}{2}}sds=\frac{\pi^{2}}{8}.\]但是\[\int\limits_0^1 {\frac{{{{\sin }^{ – 1}}x}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{{\pi ^2}}}{8}.\]又\[{\sin ^{ – 1}}x = \int {\frac{{dx}}{{\sqrt {1 – {x^2}} }}} = x + \frac{1}{2}\frac{{{x^3}}}{3} + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{{{x^5}}}{5} + \frac{{1 \cdot 3 \cdot 5}}{{2 \cdot 4 \cdot 6}}\frac{{{x^7}}}{7} + \cdots.\]我们可以得到\[\int\limits_0^1 {\left\{ {\frac{{dx}}{{\sqrt {1 – {x^2}} }}\int {\frac{{dx}}{{\sqrt {1 – {x^2}} }}} } \right\}} = \int\limits_0^1 {\left\{ {x + \frac{1}{2}\frac{{{x^3}}}{3}\frac{{dx}}{{\sqrt {1 – {x^2}} }} + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{{{x^5}}}{5}\frac{{dx}}{{\sqrt {1 – {x^2}} }} + \cdots } \right\}}.\]但是\[\int\limits_0^1 {\frac{{{x^{2n + 1}}}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{2n}}{{2n + 1}}\int\limits_0^1 {\frac{{{x^{2n – 1}}}}{{\sqrt {1 – {x^2}} }}dx}.\]这样,可以得到\[\int\limits_0^1 {\frac{{{x^{2n + 1}}}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{\left( {2n} \right)!!}}{{\left( {2n + 1} \right)!!}}.\]又所有的次数都是奇数,所以最终的结果为\[\frac{{{\pi ^2}}}{8} = 1 + \frac{1}{2}\frac{1}{3}\left( {\frac{2}{3}} \right) + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{1}{5}\left( {\frac{{2 \cdot 4}}{{3 \cdot 5}}} \right) + \frac{{1 \cdot 3 \cdot 5}}{{2 \cdot 4 \cdot 6}}\frac{1}{7}\left( {\frac{{2 \cdot 4 \cdot 6}}{{3 \cdot 5 \cdot 7}}} \right) \cdots,\]\[\frac{{{\pi ^2}}}{8} = 1 + \frac{1}{{{3^2}}} + \frac{1}{{{5^2}}} + \frac{1}{{{7^2}}} + \cdots.\]令\[1 + \frac{1}{{{2^2}}} + \frac{1}{{{3^2}}} + \frac{1}{{{4^2}}} + \cdots = \omega.\]则\[\frac{1}{{{2^2}}} + \frac{1}{{{4^2}}} + \frac{1}{{{6^2}}} + \frac{1}{{{8^2}}} + \cdots = \frac{\omega }{4}.\]这样,我们可以得到\[\frac{\omega }{4} + \frac{{{\pi ^2}}}{8} = \omega.\]即\[\omega = \frac{{{\pi ^2}}}{6}.\]证毕。

法六:

\[\sum_{i=1}^{n}\frac{1}{i^{2}}=\zeta(2)=\frac{4}{3}\sum_{n=0}^{+\infty}\frac{1}{(2n+1)^2}=\frac{4}{3}\int_{0}^{1}\frac{\log y}{y^2-1}dy\]\[=\frac{2}{3}\int_{0}^{1}\frac{1}{y^2-1}\left[\log\left(\frac{1+x^2 y^2}{1+x^2}\right)\right]_{x=0}^{+\infty}dy=\frac{4}{3}\int_{0}^{1}\int_{0}^{+\infty}\frac{x}{(1+x^2)(1+x^2 y^2)}dx\,dy\]
\[=\frac{4}{3}\int_{0}^{1}\int_{0}^{+\infty}\frac{dx\, dz}{(1+x^2)(1+z^2)}=\frac{4}{3}\cdot\frac{\pi}{4}\cdot\frac{\pi}{2}=\frac{\pi^2}{6}.\]证毕。

就介绍这几种方法吧,大家可以有选择的进行阅读。以后数学作业中再有证明\(S_{n} < 2\)的时候,不妨这样写\(\lim_{n \to \infty }S_{n}=\frac{\pi}{6} < 2\),怕老师不承认,可以顺便证明一下,至于给不给分,就不好说了。

 

[Dr.Lib]Note:Math – Iverson bracket

In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is a notation that denotes a number that is 1 if the condition in square brackets is satisfied, and 0 otherwise. More exactly,

\( [P] = \begin{cases} 1 & \text{if } P \text{ is true;} \\ 0 & \text{otherwise.} \end{cases} \)

where P is a statement that can be true or false. This notation was introduced by Kenneth E. Iverson in his programming language APL,while the specific restriction to square brackets was advocated by Donald Knuth to avoid ambiguity in parenthesized logical expressions.

The Iverson bracket converts a Boolean value to an integer value through the natural map \( \textbf{false}\mapsto 0; \textbf{true}\mapsto1 \), which allows counting to be represented as summation. For instance, the Euler phi function that counts the number of positive integers up to n which are coprime to n can be expressed by

\( \phi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1],\qquad\text{for }n\in\mathbb N^+. \)

More generally the notation allows moving boundary conditions of summations (or integrals) as a separate factor into the summand, freeing up space around the summation operator, but more importantly allowing it to be manipulated algebraically. For example

\( \sum_{1\le i \le 10} i^2 = \sum_{i} i^2[1 \le i \le 10]. \)

In the first sum, the index \( i \) is limited to be in the range 1 to 10. The second sum is allowed to range over all integers, but where i is strictly less than 1 or strictly greater than 10, the summand is 0, contributing nothing to the sum. Such use of the Iverson bracket can permit easier manipulation of these expressions.

Another use of the Iverson bracket is to simplify equations with special cases. For example, the formula

\( \sum_{1\le k\le n \atop \gcd(k,n)=1}\!\!k = \frac{1}{2}n\varphi(n) \)

which is valid for n > 1 but which is off by 1/2 for n = 1. To get an identity valid for all positive integers n (i.e., all values for which \(\phi(n) \) is defined), a correction term involving the Iverson bracket may be added:

\( \sum_{1\le k\le n \atop \gcd(k,n)=1}\!\!k = \frac{1}{2}n(\varphi(n)+[n=1]) \)

 -By Wikipedia https://en.wikipedia.org/wiki/Iverson_bracket

Via Ivy – End  http://www.ivy-end.com/archives/1064

闲来无事,逛逛Mathematics。看到一道关于数列的题目,不妨拿来研究一下。原题地址

题目是这么说的,计算\[\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n} \right )^{2}+\cdots + \left ( \frac{1}{n-1}+\frac{1}{n} \right )^{2}+\left ( \frac{1}{n} \right )^{2}.\]各位可以自己动笔计算一下。

下面我们主要讨论一下给出的两种种解法。

法一:

令\(S_{n}=\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n} \right )^{2}+\cdots + \left ( \frac{1}{n-1}+\frac{1}{n} \right )^{2}+\left ( \frac{1}{n} \right )^{2}\)。

则\[S_{n}-S_{n-1}=\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n} \right )^{2}+\cdots + \left ( \frac{1}{n-1}+\frac{1}{n} \right )^{2}+\left ( \frac{1}{n} \right )^{2} \right ]\\-\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )^{2}+\cdots + \left ( \frac{1}{n-2}+\frac{1}{n-1} \right )^{2}+\left ( \frac{1}{n-1} \right )^{2} \right ].\]整理得\[S_{n}-S_{n-1}=\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )^{2}+2\cdot\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )\cdot\left ( \frac{1}{n} \right )+\left ( \frac{1}{n} \right )^{2} \right ]\\ + \left [ \left ( \frac{1}{2}+\frac{1}{3}+\cdots + \frac{1}{n-1} \right )^{2}+2\cdot\left ( \frac{1}{2}+\frac{1}{3}+\cdots + \frac{1}{n-1} \right )\cdot\left ( \frac{1}{n} \right )+\left ( \frac{1}{n} \right )^{2} \right ]\\ + \cdots + \left [ \left ( \frac{1}{n-1} \right )^{2}+2\cdot\left ( \frac{1}{n-1} \right )\cdot\left ( \frac{1}{n} \right )+\left ( \frac{1}{n} \right )^{2} \right ]+\left [ \left ( \frac{1}{n} \right )^{2} \right ]\\-\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )^{2}+\cdots + \left ( \frac{1}{n-2}+\frac{1}{n-1} \right )^{2}+\left ( \frac{1}{n-1} \right )^{2} \right ].\]化简得\[S_{n}-S_{n-1}=n\cdot\left ( \frac{1}{n} \right )^{2}+2\cdot\frac{1}{n}\cdot\left [ 1+2\cdot\frac{1}{2}+3\cdot\frac{1}{3}+\cdots +\left ( n-1 \right )\cdot\frac{1}{n-1} \right ].\]即\[S_{n}-S_{n-1}=\frac{1}{n}+\frac{2\left ( n-1 \right )}{n}=2-\frac{1}{n}.\]运用累加法求和即可得到\[S_{n}=2n-H_{n}.\]其中\(H_{n}=1+\frac{1}{2}+\frac{1}{2}+\cdots +\frac{1}{n}.\)

法二:

这种方法比第一种方法高明很多,它需要用到一个引理——Iverson Bracket。简单的介绍一下这个引理,它的符号是中括号,当且仅当中括号里的表达式成立时,其值为\(1\),否则为\(0\)。例如\(\left [ 1 < 2 \right ]=1\),而\(\left [ 1 > 2 \right ]=0\)。

下面我们就用Iverson Bracket来求解这个问题\[S_{n}=\sum_{k}\left ( \sum_{i}\frac{1}{i}\cdot\left [ k \leq i \right ] \right )^{2}=\sum_{k}\sum_{i,j}\frac{1}{ij}\cdot\left [ k \leq i, k \leq j \right ]=\sum_{i,j}\frac{1}{ij}\sum_{k}\left [ k \leq \min\left ( i,j \right ) \right ].\]即\[S_{n}=\sum_{i,j}\frac{1}{ij}\cdot\min\left ( i,j \right )=\sum_{i,j}\frac{1}{\max\left ( i,j \right )}=\sum_{m}\frac{1}{m}\sum_{i,j}\left [ \max\left ( i,j \right )=m \right ].\]即\[S_{n}=\sum_{m}\frac{1}{m}\cdot\left ( 2m-1 \right )=2n-\sum_{m}\frac{1}{m}=2-H_{n}.\]