《具体数学》2 Sum Study Note (2)

Repertoire method

If we want to calculate : $\sum_{i=1}^n i^2$, we can construct a recursion :

$$\begin{cases} R_0 = \alpha \\ R_n = R_{n-1} + \beta + \gamma n + \delta n^2 \end{cases}$$

And it must satisfy :

$$R_n = A(n)\alpha + B(n)\beta + C(n)\gamma + D(n)\delta$$

Consider that we have already known $A(n),B(n),C(n)$, now I will demonstrate to you how to calculate $D(n)$ :

Let $R_n = n^3$ , so $\alpha = 0$, and :

$$\begin{align*} n^3 - (n-1)^3 &= 3n^2 - 3n + 1\\ \\ \beta = 1 ,\; \gamma &= -3 ,\; \delta = 3 \end{align*}$$

Therefore :

$$R_n = n^3 = A(n) \cdot \alpha + B(n)\beta + C(n)\gamma + D(n)\delta$$

Since only $D(n)$ remains unknown, we may solve for it directly !

Expansion method

For calculating $\sum_{k=1}^n k^2$, this is a one-fold sum, yet we may rewrite it as a double sum :

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

That is easy.

Difference

Definition :

$$g(x) = \Delta f(x) \quad \Longleftrightarrow \quad \sum g(x) \, dx = f(x) + C$$

For example :

$$\sum_{0 \le k < n} k^{\underline{m}} = \left. \frac{k^{\underline{m+1}}}{m+1} \right|_{0}^{n} = \frac{n^{\underline{m+1}}}{m+1}-\frac{0^{\underline{m+1}}}{m+1}=\frac{n^{\underline{m+1}}}{m+1}$$

Proof :

As :

$$\begin{align*} \Delta(x^{\underline{m}}) &= (x+1)^{\underline{m}} - x^{\underline{m}}\\ &= (x+1) \cdot x \cdot (x-1) \cdots (x - m + 2) - x \cdot (x-1) \cdots (x - m + 1)\\ &= m \cdot x^{\underline{m-1}} \end{align*}$$

So :

$$x^{\underline{m}} = \frac{\Delta\left(x^{\underline{m+1}}\right)}{m+1}$$

Below are more common differences :

• $x^{\underline {m}}$ is like $x^m$ in finite
• $2^x$ is like $e^x$ in finite
• $H_x$ is like $\ln x$ in finite

So the whole calculation of $x^{\underline m}$ is :

$$\sum_{a}^{b} x^{\underline{m}} \delta x= \begin{cases} \left.\displaystyle \frac{x^{\underline{m+1}}}{m+1}\right|_{a}^{b}, & m \neq -1,\\[6pt] \left.H_x\right|_{a}^{b}, & m = -1. \end{cases}$$

$$\begin{align*} \Delta\big(u(x)v(x)\big) &= u(x+1)v(x+1) - u(x)v(x) \\ &= u(x+1)v(x+1) - u(x)v(x+1) \\ &\quad + u(x)v(x+1) - u(x)v(x) \\ &= u(x)\Delta v(x) + v(x+1)\Delta u(x) \end{align*}$$

Here, $Ef(x)=f(x+1)$. We refer to E as the shift operator.

Give you an example :

*English improve

1. And it must have to be -> And it must satisfy
2. Only $D(n)$ is unknown, so we can get it easily ! -> Since only $D(n)$ remains unknown, we may solve for it directly !
3. but we can change it -> yet we may rewrite it as
4. Here's -> Below are
5. we called it -> we refer to E as