[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


题目是这么说的,计算\[\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}.\]

CC BY-SA 4.0 [Dr.Lib]Note:Math – Iverson bracket by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.


电子邮件地址不会被公开。 必填项已用*标注