《具体数学》Lesson 2 SUMS | Study Note（1）

Summation factor

To solve this equation :

$a_nT_n=b_nT_{n-1}+c_n$

We have to construct $s_n$ that satisfied : $s_nb_n=s_{n-1}a_{n-1}$ (1). And in here, $s_n$ is the summation factor.

so if we define $S_n=s_na_nT_n$ . And when we multiple $s_n$ , thus the original expression becomes :

$S_n=S_{n-1}+s_nc_n$

This can be solved easily.

Yet how can we find $s_n$ ?

From the definiton (1), we know that $s_n=s_{n-1}\cdot \dfrac {a_{n-1}}{b_n}$ , therefore :

$s_n=k\cdot \dfrac{a_{n-1}a_{n-2}\cdots a_1}{b_nb_{n-1}\cdots b_2}$

Harmonic number

Definition :

$H_n = \sum_{k=1}^n\dfrac 1 k$

The summation of harmonic number :

$\sum_{0 \le k < n}H_k=nH_k-n$

Proof :

$\begin{align*} \sum_{0 \le k \le n} \sum_{1 \le i \le k} \frac{1}{i} &= \sum_{i=1}^{n} \sum_{k=i}^{n-1} \frac{1}{i} \\ &= \sum_{i=1}^{n} \frac{n-i}{i} = \sum_{i=1}^{n} \left( \frac{n}{i} - 1 \right) \\ &= n \sum_{i=1}^{n} \frac{1}{i} - n = n H_n - n \end{align*}$

The methods are multiple, any ways you choose can get the answer easily.

In fact, the most interesting feature of this problem is that when we arrange the numbers in a grid :

Summing the numbers along rows or columns proves difficult, yet calculating along the diagnonals is straightforward.

Perturbation method

Suppose we are given the sequence term $a_n$ , and we aim to compute its partial sum $S_n$ , defined as:

$S_n=\sum_{k=0}^na_k$

Adding $a_{n+1}$ to both sides, we derive the following identity step by step :

$S_n+a_{n+1}=a_0+\sum_{k=0}^na_{k+1}$

If we possess a recurrence relationship linking $a_k$ and $a_{k+1}$ , the summation $\sum_{k=0}^na_{k+1}$ may be rewritten directly in terms of $S_n$ .