Intro to Probability - YAQ Week 4

Question

Show that $\sum _{j=0}^\infty x^j=\frac{1}{1-x}$ for $|x|<1$.

Notice first that $$ (1-x)\sum_{j=1}^nx^j=(1-x)(1+x+\dots+x^n)=(1+x+\dots+x^n)-(x+x^2+\dots x^{n+1})= 1-x^{n+1} $$ for any $x\in\mathbb{R}$. This clearly gives that $$ \sum_{j=1}^nx^j=\frac{1-x^{n+1}}{1-x}\text{ for }x\in \mathbb{R}. $$ Letting $n$ go to infinity $$ \sum_{j=1}^\infty x^j=\lim _{n\to\infty}\sum _{j=1}^n x^j= \lim _{n\to\infty}\frac{1-x^{n+1}}{1-x}=\frac{1}{1-x} $$ for $|x|<1$ since $x^{n+1}\to 0$ as $n\to\infty$ for such $|x|<1$.

Question

For $n=1,2,3,...$ and $k\leq n$, let $T_n(k)$ denote the number of ways in which the set $N_n=\{1,2,\dots,n\}$ can be partitioned into $k$ subsets $S_1,\dots,S_k$. Partitioned means that the sets are non-empty, pairwise disjoint and satisfy $\bigcup_{j=1}^kS_j=N_n$ . Argue that it must hold that $$ T_n(k)=T_{n-1}(k-1)+k\, T_{n-1}(k) $$

A partition of $N_n$ will be such that it either contains the set $S=\{n\}$ or it wil not contain it. So, if we account for all partitions for which, say $S_1=\{n\}$, and for all those for which $S_j\neq\{ n\}$ for all $j=1,\dots,k$, then we will have accounted for all possible partitions.

Partitions of the first type will correspond to partitions of $N_{n-1}$ into $k-1$ subsets (consisting of $S_2,\dots,S_k$) for a total of $T_{n-1}(k-1)$.

Partitions of the second kind will be such that $n\in S_j$ for some $j\in\{1,\dots,k\}$ and that $S_j\neq\{ n\}$. The latter implies that, removing $n$ from $S_j$ still leaves us with a non-empty set. Now $$ S_1,\dots, S_{j-1},S_j\setminus\{ n\},S_{j+1},\dots, S_k $$ is a partition of $N_{n-1}$. This means that there are $k\,T_{n-1}(k)$ partitions of the second type. You can also think of this as follows: any partition into $k$ subsets of $N_{n-1}$ will give us a partition of the second kind for $N_n$ by simply choosing one of the sets in the partition ($k$ choices) and placing $n$ in that set.

Question

Why is it that $$ \frac{1}{2}-\frac{1}{3!}+\frac{1}{4!}-\dots+\frac{(-1)^n}{n!}= \sum_{j=0}^n \frac{(-1)^j}{j!}\simeq \frac{1}{e} $$ for $n$ large?

The exponential function is defined by $$ e^x=\sum _{j=0}^\infty \frac{x^j}{j!}=\lim_{n\to\infty}\sum_{j=0}^n \frac{x^j}{j!}, $$ which means that $$ \sum_{j=0}^n\frac{x^j}{j!}\simeq e^x $$ for large $n$. Taking $x=-1$ we get $$ \frac{1}{e}=e^{-1}=1-1+\frac{1}{2}-\frac{1}{3!}+\frac{1}{4!}\mp\dots $$ as stated in Lecture 4.