Last Updated: 2024-04-14 13:38:30 Sunday
-- TOC --
研究算法理论，需要用数学工具来证明的。在一众可能会用到的数学工具中，数列必不可少，我们常常通过数列和，证明时间或空间复杂度。
计算机科学中遇到的很多都不是级数，只是有限项的数列和。
$$\sum_{k=1}^n(2k-1)=n^2$$
可以用Induction的方法证明，可以更直接的用Picture Proof的方法证明，一图胜千言，没办法，人类就进化成这样了。关于奇数和的这个公式的证明，如下图：
$$\sum_{i=1}^ni=\cfrac{n(n+1)}{2}=\Theta(n^2)$$
$$\begin{align} \sum_{k=1}^n{k^2} &= 1^2+2^2+3^2+...+n^2\notag \\ &= \cfrac{2 n^3 + 3 n^2 + n}{6}\notag \\ &= \cfrac{n(n+1)(2n+1)}{6}\notag \end{align}$$
可用Induction证明，但不知道最初是怎么得到这个结果的...?
$$\sum_{i=1}^ni^3=\cfrac{n^2(n+1)^2}{4}$$
$$\sum_{k=0}^n a^k = 1+ a + a^2 + ... + a^n = \frac{1-a^{n+1}}{1-a},(a\neq1) $$
The sum of any geometric series is a constant times its largest term. （找出最大项，这本就是得到asymptotic notation的方法，更是不是geometric seires貌似没关系）
推导方法
设\(S=\sum_{k=0}^{n}\)，然后计算\(S-aS\)。
这种方法对于计算有限项数列和是OK的，如果是无限项，S就成了无穷级数的部分和，S必须要收敛！否则计算结果会很荒谬...
Picture Proof
$$a=\cfrac{1}{2}$$
当\(a=2\)时
$$\sum_{k=0}^n2^k=2^{n+1}-1$$
此时如果是无穷级数，S发散，是无法计算的。
For positive integer n, the
nth harmonic numberis:
$$H_n=\sum_{i=1}^n\cfrac{1}{i} = \ln{n} + O(1)$$
调和级数是发散的...
$$\sum_{i,j}a_ia_j=\left(\sum_ia_i\right)^2$$
大量的乘法就这样消散，用加法取代，计算速度极快！从\(\Theta(n^2)\)到\(\Theta(n)\)。
示例1：
$$\begin{aligned} \sum_{i,j}a_ia_j(j-i)^2 &= \sum_{i,j}a_ia_j(j^2-2ija_ia_j+i^2)\\ &=\sum_{i,j}a_ia_jj^2 - 2\sum_{i,j}ij\cdot a_ia_j + \sum_{i,j}a_ja_ii^2\\ &=2\left(\sum_{i}a_i\cdot\sum_{i}a_i\cdot i^2 - \left(\sum_ia_i\cdot i\right)^2\right) \end{aligned}$$
对应算法代码：
示例2：
$$\begin{aligned} \sum_{i}\sum_{m}a_ia_me^{i+m}&=\sum_{i,m}a_ie^i\cdot a_me^m \\ &=\left(\sum_{i}a_ie^i\right)^2 \end{aligned}$$
本文链接：https://cs.pynote.net/math/202401316/
-- EOF --
-- MORE --