⚠️THIS NOTE IS NOT FINISHED YET TODO: stirling number definitions stirling number of the first and the second type bell number Question Can you find a closed formula for the sum of the $p$-th powers of the first $n$ positive integers? That is, we need a closed formulat for the sequence: $$ h_n=a_p n^p+a_{p-1} n^{p-1}+\cdots+a_1 n+a_0, \quad(n \geq 0) $$ Solution The method is to use difference sequences. We already know the following: ...
Example sums of cubes Solve $h_n=h_{n-1}+n^3,(n \geq 1)$ and $h_0=0$. Solution Note that this is not a homegenous recurrence relation. Unrolling gives us: $$ \begin{align*} h_{n-1} &= (n-1)^3 + h_{n-2}\\ \implies h_n &= n^3 + (n-1)^3 + h_{n-2} \end{align*} $$ And we can keep doing this. Using this as the intuition, we guess the closed form: $$ h_n = n^3 + (n-1)^3 + \ldots + 2^3 + 1 $$ To formally prove this, we can use induction! Assume it holds for some $n \geq 1$, we want to show that $h_{n+1} = h_n + (n+1)^3 = 1 + 2^3 + \ldots + (n+1)^3$. ...
Generating Functions Generating functions can be regarded as algebraic objects whose formal manipulation allows us to count the number of possibilities for a problem by means of algebra. Definition Let $h_0, h_1, h_2, h_3, \ldots$ be an infinite sequence of numbers. Its generating function is defined to be the infinite series: $$ g(x) = h_0 + h_1x + h_2x^2 + \cdots + h_nx^n + \cdots $$ Example 1 The generating function of the infinite sequence $1, 1, 1, \ldots$ is: $$ g(x) = 1 + x + x^2 + x^3 + \cdots $$ for $|x| < 1$. This generating function $g(x)$ is the sum of a geometric series with value: $$ g(x) = \frac{1}{1-x} $$ Solution ...
Definition A multinomial coefficient is: $$ \binom{n}{n_1 n_2 \cdots n_t} =\frac{n !}{n_{1} ! n_{2} ! \cdots n_{t} !} $$ Here, $n_1, n_2, \ldots, n_t$ are nonnegative integers with $$ n_1+n_2+\cdots+n_t=n $$ Pascal’s theorem for multinomial coefficients Pascal’s theorem for Let $n, k \in \mathbb{N}$ and $(n)_{i=1}^k$ be natural numbers so that $$ n_1+\cdots+n_k=n $$ Then, $$ \binom{n}{n_1, n_2, \ldots, n_k} = \binom{n-1}{n_1-1, n_2, \ldots, n_k} + \ldots + \binom{n-1}{n_1, n_2, \ldots, n_k-1} $$ ...
Unimodality of Binomial Coefficients and Sperner’s Theorem If we examine the binomial coefficients in a row of Pascal’s triangle, we notice that the numbers increase for a while and then decrease. A sequence of numbers with this property is called unimodal. Theorem Let $n$ be a positive integer. The sequence of binomial coefficients $$ {{n} \choose {0}}, {{n} \choose {1}}, \ldots, {{n} \choose {n}} $$ is a unimodal sequence. Mor precisely, $$ {{n} \choose {0}} < {{n} \choose {1}} < \ldots < {{n} \choose {\lfloor n/2\rfloor}} $$ and $$ {{n} \choose {\lceil n/2 \rceil}} > \ldots {{n} \choose {n-1}} > {{n} \choose {n}} $$ ...
Theorem $$ \text{For every } k \in \mathbb{N}, \text{we have } R(k)\ge 2^{k/2} $$ Before we start the proof, let’s look at 3 ingredients we need: The probabilistic method The union bound The binomial estimate The probabilistic method Let $\Omega$ be the set of all possible outcomes of an experiment. Suppose that each outcome is equally likely. Let $A \subseteq \Omega$ be an event. $$ \text{If } \operatorname{Prob}(A) < 1 \text{, then } \operatorname{Prob}(A^c) > 0 $$ ...
General Ramsey on normal graph Notation General notation for Ramsey theory: $K_n \to (K_s,K_t)$ is the assertion that for any coloring of the edges of $K_n$ with red and blue, we can always find a red $K_s$ or a blue $K_t$. $K_n \not \to (K_s,K_t)$ is the assertion that there exists a coloring of the edges of $K_n$ with red and blue with no red $K_s$ nor blue $K_t$. Notation Off-diagonal Ramsey numbers: ...
Erdos-Szekeres Theorem Given $r, s$ any sequence of distinct real numbers with length at least $(r-1)(s-1)+1$ contains a monotonically increasing subsequence of length $r$ or a monotonically decreasing subsequece of length $s$. That is, given the subsequence: $a_1, a_2, …, a_{(s-1)(r-1)+1}$, we can find: Indicies $i_1 < i_2 < …< i_r$ so that $a_{i1} < a_{i2} < …< a_{ir}$ OR Indicies $j_1 < j_2 < …< j_r$ so that $a_{j1} > a_{j2} > … > a_{jr}$ Example: $s = 3, r = 3$, Sequence: $10, 11, 7, 8$ has no such property. ...
Permutation of Sets Definition permutation A permutation of a set $S$ can be thought of as a listing of the elements $S$ in some order. $P(n, r)$ denotes the number of $r$-permutations of an $n$-element set. Definition $r$-permutation An $r$-permutation of a set $S$ is a string $a_1, a_2, … a_r$ where $a_i \in S, \forall i \in [r]$ and $a_i \neq a_j$ for $i \neq j$. Note: $[r] = {1, 2, …, r}$ ...
Pigeonhole Principle If $n+1$ objects are distributed into $n$ boxes, then at least one box contains two or more of the objects. Proof For each $i\in \set{1, …, n}$, let $a_i = $ number of objects in box $i$. Then, $a_1 + … + a_n = n+1$ Let $a_j = \text{max } a_i$. Then, \begin{align*} n+1 &\leq n\cdot a_j \\ \frac{n+1}{n} &\leq a_j \\ 1 < \frac{n+1}{n} &\leq a_j\\ 1 &< a_j \end{align*} Note that this conclusion doesn’t hole if you have $n$ objects or less. ...