---
###### tags: `Algorithm`
---
Exercises: Review of Mathematics
===

## Mathematical Induction

:::info
**Example 1:**
We show, for all positive integers $n$, that
$$
1+2+...+n=\frac{n(n+1)}{2}
$$

* **Induction base:**
For $n = 1$,
$$
1 = \frac{1(1+1)}{2}
$$
* **Induction hypothesis:**
Assume, for an arbitrary positive integer n, that
$$
1+2+..+n=\frac{n(n+1)}{2}
$$

* **Induction step:**
We need to show that
$$
1+2+...+(n+1)=\frac{(n+1)[(n+1)+1]}{2}
$$
To that end,
$$
\begin{split}
1+2+...+(n+1)&=1+2+...+n+n+1 \\
&=\frac{n(n+1)}{2}+n+1 \\
&=\frac{n(n+1)+2(n+1)}{2} \\
&=\frac{(n+1)(n+2)}{2} \\
&=\frac{(n+1)[(n+1)+1]}{2}
\end{split}
$$
:::

:::info
**Example 2:**
We show, for all positive integers $n$, that
$$
1^2 + 2^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}
$$

* **Induction base:**
For $n = 1$,
$$
1^2 = 1 = \frac{1(n+1)[2 \times 1 + 1]}{6}
$$

* **Induction hypothesis:**
Assume, for an arbitrary positive integer n, that
$$
1^2 + 2^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}
$$

* **Induction step:**
We need to show that
$$
1^2 + 2^2 + ... + n^2 + (n+1)^2 = \frac{(n+1)[(n+1)+1][(2n+1)+1]}{6}
$$
To that end,
$$
\begin{split}
1^2 + 2^2 + ... + (n+1)^2 &= 1^2 + 2^2 + ... + n^2 + (n+1)^2 \\
&=\frac{n(n+1)(2n+1)}{6} + (n+1)^2 \\
&=\frac{n(n+1)(2n+1) + 6(n+1)^2}{6} \\
&=\frac{(n+1)(2n^2+7n+6)}{6} \\
&=\frac{(n+1)(n+2)(2n+3)}{6} \\
&=\frac{(n+1)[(n+1)+1][2(n+1)+1]}{6}
\end{split}
$$
:::

:::info
**Example 3:**
We show, for all nonnegative integers $n$, that
$$
2^0+2^1+2^2+...+2^n=2^{n+1}-1
$$

In summation notation, this equality is
$$
\sum_{i=0}^n 2^i = 2^{n+1} - 1
$$

* **Induction base:**
For $n = 0$,
$$
2^0 = 1 = 2^{0+1} - 1
$$

* **Induction hypothesis:**
Assume, for an arbitrary nonnegative integer n, that
$$
2^0 + 2^1 + 2^2 + ... + 2^n = 2^{n+1} - 1
$$

* **Induction step:**
We need to show that
$$
2^0+2^1+2^2+ ... +2^{n+1} = 2^{(n+1)+1}-1
$$
To that end,
$$
\begin{split}
2^0+2^1+2^2+...+2^{n+1}
=& 2^0+2^1+2^2+...+2^n+2^{n+1} \\
=& 2^{n+1} - 1 + 2^{n+1} \\
=& 2(2^{n+1}) - 1 \\
=& 2^{(n+1) + 1} -1
\end{split}
$$
:::

:::info
**Example 4:**
We show, for all nonnegative integers $n$ and real numbers $r \neq 1$, that
$$
\sum_{i=0}^n r^i = \frac{r^{n+1} - 1}{r - 1}
$$

The terms in this sum are called a geometric progression.

* **Induction base:**
For $n = 0$,
$$
r^0 = 1 = \frac{r^{0+1}-1}{r-1}
$$

* **Induction hypothesis:**
Assume, for an arbitrary nonnegative integer n, that
$$
\sum_{i=0}^n r^i = \frac{r^{n+1} - 1}{r - 1}
$$

* **Induction step:**
We need to show that
$$
\sum_{i=0}^{n+1} r^i = \frac{r^{(n+1)+1} - 1}{r - 1}
$$
To that end,
$$
\begin{split}
\sum_{i=0}^{n+1} =& r^{n+1} + \sum_{i=0}^n r^i \\
=& r^{n+1}+\frac{r^{n+1}-1}{r-1} \\
=& \frac{r^{n+1}(r-1)+r^{n+1}-1}{r-1} \\
=& \frac{r^{n+2}-1}{r-1}
= \frac{r^{(n+1)+1}-1}{r-1}
\end{split}
$$
:::

:::info
**Example 5:**
We show, for all positive integers n, that
$$
\sum_{i=1}^n = (n-1)2^{n+1}+2
$$

* **Induction base:**
For $n = 1$,
$$
1 \times 2^1 = 2 = (1-1)2^{1+1}+2
$$

* **Induction hypothesis:**
Assume, for an arbitrary positive integer n, that
$$
\sum_{i=1}^2 i2^i = (n-1)2^{n+1}+2
$$

* **Induction step:**
We need to show that
$$
\sum_{i=1}^{n+1}[(n+1)-1]2^{(n+1)+1}+2
$$
To that end,
$$
\begin{split}
\sum_{i=1}^{n+1} i2^i =& \sum_{i=1}^n i2^i+(n+1)2^{n+1} \\
=& (n-1)2^{n+1}+2+(n+1)2^{n+1} \\
=& 2n2^{n+1}+2 \\
=& [(n+1)-1]2^{(n+1)+1}+2
\end{split}
$$
:::

:::success
**Exercises 1:**
Use mathematical induction to show that, for all integers $n > 0$,
$$
\sum_{k=1}^n k(k!) = (n+1)! - 1
$$

* **Induction base:**
For $n = 1$,
$$
1(1)! = (1 + 1)! - 1 = 1
$$

* **Induction hypothesis:**
Assume, for an arbitrary positive integer n, that
$$
\sum_{k=1}^n k(k!) = (n+1)! - 1
$$

* **Induction step:**
We need to show that

$$
\displaystyle\sum_{i=1}^{n+1} k(k)! = ((n + 1) + 1)! - 1
$$

To that end,

$$
\begin{split}
\sum_{i=1}^{n+1} k(k)! =& (n + 1)! - 1 + (n + 1)(n + 1)! \\
=& (1 + n + 1)(n + 1)! - 1 \\
=& (n + 2)(n + 1)! - 1 \\
=& (n + 2)! - 1 \\
=& ((n + 1) + 1)! - 1
\end{split}
$$
:::

:::success
**Exercises 2:**
Use mathematical induction to show that $n^2 − n$ is even for any positive integer $n$.

* **Induction base:**
For $n = 1$,
$$
1^2 - 1 = 0
$$

* **Induction hypothesis:**
Assume, for an arbitrary positive integer n, that
$$
n^2 − n = 2k
$$
$k$ is any positive integer.

* **Induction step:**
We need to show that

$$
(n+1)^2 − (n+1) = 2k
$$

$k$ is any positive integer.

To that end,

$$
\begin{split}
(n + 1)^2 - (n + 1) =&\ n^2 + 2n + 1 - n - 1 \\
=&\ 2k + 2n \\
=&\ 2(k + n)
\end{split}
$$
:::

:::success
**Exercises 3:**
Use mathematical induction to show that, for all integers $n > 4$,
$$
2^n > n^2
$$

* **Induction base:**
For $n = 5$,
$$
2^5 = 32 > 5^2 = 25
$$

* **Induction hypothesis:**
Assume, for an arbitrary positive integer $n$, that
$$
2^n > n^2
$$

* **Induction step:**
We need to show that

$$
2^{n+1} > {(n+1)}^2
$$

To that end,

$$
2^{n+1} = 2^n2 > 2n^2 > n^2 + 2n + 1 = (n + 1)^2
$$
:::

## Properties of 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}$

:::info


:::


## 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)!}$