---
tags: Algorithm
---

<style>
font {
color: red;
font-weight: bold;
}
</style>

# Review of Mathematics

- ==歸納法== (==小考==)
- Exp: 證明 $\displaystyle\sum_{i=1}^n i = 1 + 2 + ... + n = \cfrac{n(n+1)}{2}$
- Theorems and Lemmas
- Logarithms
1. $\log_a 1 = 0$
2. $a^{\log_ax} = x$
3. $\log_a(xy) = log_a x + log_a y$
4. $\log_a \cfrac{x}{y} = \log_a x - \log_a y$
5. $\log_a x^y = y \log_a x$
6. $x^{\log_a y} = y^{\log_a x}$
7. $\log_a x = \cfrac{\log_b x}{\log_b a}$
- Sets
- 交集、聯集、元素不重複
- Permutations(排列) and Combinations
- $P^n_m = \cfrac{n!}{(n-m)!} = C^n_m \times m!=n \times (n-1) \times ... (n-m+1)$
- E.g., abc 可以排列出 abc, acb, bac, bca, cab, cba $\Rightarrow P^3_3 = 3 \times 2 \times 1 = 6$
- $C^n_m = \cfrac{n!}{m!(n-m)!}$
- Probability

可能會用到的級數和:
- 平方: $\displaystyle\sum_{i=1}^n i^2 = \cfrac{n(n+1)(2n+1)}{6}$
- 立方: $\displaystyle\sum_{i=1}^n i^3 = \left(\cfrac{n(n+1)}{2}\right)^2$
- 等比級數: $\cfrac{a(1-r^n)}{1-r}$ or $\cfrac{a(r^n-1)}{r-1}$