Mathematics Blog

Probability Mass Functions A box contains $N$ balls labeled $1,2,\dots,N$. One ball is selected uniformly at random. Let $X$ denote the label of the selected ball. Find the PMF, CDF, expected value, and variance of $X$. Since the total sum of all probabilities must equal \(1\) and each label is equally likely to be selected, the uniform PMF of \(X\) written \(P:\{1,\ldots,N\}\to[0,1]\) is defined by: $ P(x)=\frac1N $ for all \(x\in\{1,\ldots,N\}\). The CDF of \(X\) is \(F_X:\mathbb{R}\to[0,1]\) defined by $ F_X(x)=P(X\le x) $ for all \(x\in\mathbb{R}\). If \(1\le x uniform CDF of \(X\) is defined as: \[ F_X(x)= \begin{cases} 0 & \text{if } x The expected value of \(X\) is $ E[X] = \sum_{x=1}^{N} xP(x). $ Since $ P(x)=\dfrac1N $ for all \(x\in\{1,\dots,N\}\), $ E[X] = \dfrac1N\sum_{x=1}^{N} x. $ Using the triangle number summation $ 1+2+\cdots+N=\dfrac{N(N+1)}{2}, $ one obtains $ E[X] = \dfrac1N\cdot\dfrac{N(N+1)}{2} = \dfrac{N+1}{2}. $...

The Twelvefold Way How many functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements? By definition, a function assigns each of the \(N\) domain elements to exactly one of the \(K\) codomain elements. Thus, each domain element has \(K\) choices for its image, giving $ K^N $ total functions. This is a permutation with repetition, since we make \(N\) ordered choices from \(K\) possibilities, allowing repetition. How many injective functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements? By definition, an injective function assigns each of the \(N\) domain elements to a distinct element of the codomain. Thus, the first domain element has \(K\) choices, the second has \(K-1\) choices, the third has \(K-2\) choices, and so on. Therefore, the number of injective functions is $ K(K-1)(K-2)\cdots(K-N+1) = \frac{K!}{(K-N)!} $ provided that \(N \leq K\). This is a permutation w...

Principle of Mathematical Induction Triangular Numbers (Sum of First \(n\) Positive Integers): \[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \] Base Case: Let \(n=1\). Then $ 1 = \frac{1(1+1)}{2}. $ Since $ \frac{2}{2} = 1, $ the statement holds for \(n=1\). Inductive Step: Assume that for some \(n \ge 1\), $ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}. $ We must show that $ 1 + 2 + 3 + \cdots + n + (n+1) = \frac{(n+1)(n+2)}{2}. $ Starting from the left-hand side: $ 1 + 2 + 3 + \cdots + n + (n+1) $ Using the inductive hypothesis, substitute: $ \frac{n(n+1)}{2} + (n+1). $ Factor: $ (n+1)\left(\frac{n}{2} + 1\right) = (n+1)\left(\frac{n+2}{2}\right). $ Thus, $ = \frac{(n+1)(n+2)}{2}. $ Hence the statement holds for \(n+1\). By mathematical induction, the formula holds for all \(n \ge 1\). Sum of Odd Numbers: \[ 1 + 3 + 5 + \cdots + (2n-1) = n^2 \] Base Case: Let \(n=1\). Then $ 1 = 1^2. $ Since $ 1 = 1, $ the statement holds for \(n...

Injective and Surjective Functions If \(g\circ f\) is injective, then \(f\) is injective. Proof. Assume that \(g\circ f\) is injective. To show that \(f\) is injective, suppose that \(f(x_1)=f(x_2)\) for some \(x_1,x_2 \in X\). Applying \(g\) to both sides gives $g(f(x_1)) = g(f(x_2))$, so \((g\circ f)(x_1) = (g\circ f)(x_2)\). Since \(g\circ f\) is injective, it follows that \(x_1=x_2\). Therefore \(f\) is injective. A function \(f:X\to Y\) is injective if and only if, for any functions \(g,h:W\to X\), if \(f\circ g=f\circ h\), then \(g=h\). Proof. ($\Rightarrow$) First assume that \(f\) is injective and suppose that \(f\circ g=f\circ h\). Let \(w\in W\). Then \((f\circ g)(w)=(f\circ h)(w)\), so \(f(g(w))=f(h(w))\). Since \(f\) is injective, we get \(g(w)=h(w)\). Because this holds for all \(w\in W\), we conclude \(g=h\). ($\Leftarrow$) Conversely, assume that for all functions \(g,h:W\to X\), the condition \(f\circ g=f\circ h\) implies \(...

Set Differences, Unions, And Intersections $$A \setminus (B \setminus C) = (A \setminus B) \setminus C$$ False . Let \( A = \{1,2\}, \; B = \{1\}, \; C = \{1\} \). Then \( B \setminus C = \varnothing \), so \( A \setminus (B \setminus C) = A = \{1,2\} \). On the other hand, \( A \setminus B = \{2\} \), and thus \( (A \setminus B)\setminus C = \{2\} \). Therefore, \( A \setminus (B \setminus C) \ne (A \setminus B)\setminus C \). However, we can show that $A \setminus (B \setminus C) \subseteq (A \setminus B) \setminus C$. Let \(x \in (A \setminus B)\setminus C\). Then \(x \in A\), \(x \notin B\), and \(x \notin C\). We want to show \(x \in A \setminus (B \setminus C)\), meaning that \(x \in A\) and \(x \notin (B \setminus C)\). We already have \(x \in A\). Now, \(x \in (B \setminus C)\) would require \(x \in B\), but we know that \(x \notin B\). So \(x \notin (B \setminus C)\). Therefore, \(x \in A \setminus (B \setminus C)\), which proves that \( (A \setm...