Chapter 002

Series

Example 2.1: Evaluate: $S &= 1 + x + x^2 + x^3 + ... + x^n$

The idea is to write $S$ in terms of a shorter version of $S$ without using $n$ and the find $S$.

$\begin{align*} S & = 1 + x + x^2 + x^3 + ... + x^n \\ & = x(S - x^n) + 1 \\ (1 - x)S & = 1 - x^{n + 1} \\ S & = \frac{1 - x^{n + 1}}{1 - x} \\ \end{align*}$

(this is equivalent as multiply both side by $(1 - x)$)

Example 2.2: Evaluate: $S &= 1 + x + x^2 + x^3 + ...$ for $|x| < 1$ (WARNING: this is infinite series)

The idea is the same, you get $S = \lim_{n \rightarrow \infty} \frac{1 - x^{n + 1}}{1 - x}= \frac{1}{1 - x}$. Be careful, if $|x| \geq 1$, then the series diverge.

Example 2.3: Evaluate $S = 1 + 2x + 3x^2 + 4x^3 + ... + nx^{n - 1}$

This is the derivative of a known sum.

$\begin{align*} S & = \frac{d}{dx}(1 + x + x^2 + x^3 + .. + x^n) \\ & = \frac{d}{dx} \frac{1 - x^{n - 1}}{1 - xe} \\ & = \frac{1 - (n + 1)n^x + nx^{n+1}}{(1 - x)^2} \\ \end{align*}$

The above assumes $x \neq 1$. When $x = 1$, $S = \frac{n(n + 1)}{2}$

Integration

Integration by parts:

We have $\int_a^b f'' g dx = |_a^b f' g - \int_a^b f' g' dx$

where $du = u'(x) dx$ and $dv = v'(x) dx$

Change of variable: Change variable dependency in dimensional integration. Please draw a picture.

Fundemental Theory of Calculus: $\frac{d}{dx}\int_a^{g(x)} f(t) dt = f(g(x)) \cdot g'(x)$ (The change of the value $\int_a^{g(x)} f(t) dt$ by tweaking $x$ in $g(x)$ is $f(g(x)) \cdot g'(x)$)

Taylor Series and Other Limits

The definition of $e$: $e = \lim_{n \rightarrow \infty}(1+\frac{1}{n})^n$

$e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + ...$

n-th Harmonic Number: $H_n = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n}$

Therefore, we have:

1. $H_n > \int_1^{x+1} \frac{1}{x} dx = ln(n+1)$
2. $H_n - \frac{1}{1} < \int_1^n \frac{1}{x} dx$

Conclusion:

• $\ln (x + 1) < H_n < 1 + \ln (n)$

• $H_n \simeq \ln(n)$

• $\lim_{n \rightarrow \infty} H_n = \infty$

Combinatorics

Permutation: $n(n-1)(n-2)...(n-(k-1)) = \frac{n!}{(n - k)!}$

Combination: $C_k^n = {n \choose k} = \frac{n!}{(n - k)! \cdot k!}$

${n \choose 0} + {n \choose 1} + {n \choose 2} + ... + {n \choose n} = 2^n$ for number of elements in power set.

${n \choose 0}y^n + {n \choose 1}xy^{n - 1} + {n \choose 2}x^2y^{n - 2} + ... + {n \choose n}x^n = (x + y)^n$ for binomial expansion.

${n \choose 0} + {n \choose 1}x + {n \choose 2}x^2+ ... + {n \choose n}x^n = (x + 1)^n$ for special case of binomial expansion when $y = 1$.

Simple bounds on ${n \choose k}$: $(\frac{n}{k})^k \leq {n \choose k} \leq (\frac{ne}{k})^k$ // TODO: proof

Vandermonde's Identity ${m + n \choose r} = \sum_{k = 0}^r {m \choose k} \cdot {n \choose r-k}$ (choosing $r$ many stuff in mixed $m+n$ population is the same as choosing $k$ in first population and then choosing $r - k$ in second population.)

Stirling Bounds: For all positive integer $n$, $\sqrt{2\pi n}(\frac{n}{e})^n \leq n! \leq e\sqrt{n}(\frac{n}{e})^n$

• The upper and lower bounds above differ by a multplicative constant of less than 1.1

Asymptotic Notation

$O$: $\leq$ smaller, either significantly or by constant factor

• $f(n) \in O(g(n)) \iff \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = c$ for some constant $c \geq 0$

$o$: $<$ significantly smaller

• $f(n) \in o(g(n)) \iff \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = 0$

$\Omega$: $\Omega$ bigger, either significantly or by constant factor

• $f(n) \in \Omega(g(n)) \iff \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} > 0$

$\omega$: $>$ significantly bigger

• $f(n) \in \omega(g(n)) \iff \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = \infty$

$\Theta$: $=$ is $O$ and $\Omega$