Fall 2015

1. Lemma: \(f\) is injective \(\iff f\) has a left inverse \(\inverseof{f}\) satisfying \(\inverseof{f} f(a) = a\).

   Suppose \(f,g: A \to A\) are injective and \(x,y \in A\), we want to show that \((f\circ g)(x) = (f\circ g)(y) \implies x = y\). So suppose \(f(g(x)) = f(g(y))\). Since \(f\) is injective, \(f\) has a left inverse, so \(g(x) = g(y)\), and since \(g\) is injective \(x = y\). \(\qed\)

Goal: Prove that if \(A\) is a set and \(f, g: A \to A\) are injective functions, then their composition \(f \circ g: A \to A\) is injective.

<1>1. Definition: A function \(h: A \to A\) is injective if for all \(x, y \in A\), \(h(x) = h(y) \implies x = y\).

<1>2. Assume \(f: A \to A\) and \(g: A \to A\) are injective functions. Let \(x, y \in A\) and assume \((f \circ g)(x) = (f \circ g)(y)\).

<1>3. \(f(g(x)) = f(g(y))\).

<1>4. \(g(x) = g(y)\).

Applying the definition of injectivity to the elements \(g(x), g(y) \in A\) with \(f(g(x)) = f(g(y))\) from <1>3 yields \(g(x) = g(y)\).

<1>5. \(x = y\).

Applying the definition of injectivity to \(x, y \in A\) with \(g(x) = g(y)\) from <1>4 yields \(x = y\).

<1>6. Conclusion: \(f \circ g\) is injective.

By <1>1, \(f \circ g\) is injective. Q.E.D.

Let \(\varepsilon>0\) and choose \[ \delta=\min\left\{1,\frac{2\varepsilon}{5}\right\}. \] If \(0<|x-2|<\delta\), then \(1<x<3\). Hence \(|x|>1\) and \(|2x-1|<5\). Therefore \[ \left|x+\frac1x-\frac52\right| =\frac{|2x-1|\,|x-2|}{2|x|} <\frac52|x-2| <\frac52\delta \leq\varepsilon. \]

1. Denoting \(D^n f \definedas \dd{^n f}{x^n}\) and noting that \(D^1 D^n f = D^{n+1}f\), we have \[\begin{align*} D^0f &= xe^{2x} \\ D^1f &= e^{2x} + 2D^0f \\ D^2f &= 2e^{2x} + 2D^1f \\ D^3f &= 4e^{2x} + 2D^2f \\ \end{align*}\]

   and (claim) so we find that \[D^n f = 2^{n-1}e^{2x} + 2D^{n-1}f.\]

   This holds for \(n=1\): we have \(D^1 f = e^{2x} + 2xe^{2x} = 2^0e^{2x} + 2D^0 f\), and the inductive step holds exactly because \[ D^{n+1}f = DD^{n}f \\ = D(2^{n-1}e^{2x} + 2D^{n-1}f) \\ =2^n e^{2x} + 2D^n f. \] \(\qed\)

Goal: Find a closed formula for the \(n\)-th derivative \(f^{(n)}(x)\) of \(f(x) = x e^{2x}\) for all integers \(n \ge 0\), and prove it by induction.

<1>1. Claim: For all \(n \ge 0\), \(f^{(n)}(x) = (2^n x + n 2^{n-1}) e^{2x}\).

<1>2. Base Case (\(n = 0\)): \(f^{(0)}(x) = f(x) = (2^0 x + 0 \cdot 2^{-1}) e^{2x} = x e^{2x}\).

<1>3. Inductive Step: Assume the statement holds for some integer \(k \ge 0\), i.e., \(f^{(k)}(x) = (2^k x + k 2^{k-1}) e^{2x}\). Then it holds for \(k+1\). Proof: <2>1. Differentiating \(f^{(k)}(x)\) using the product rule: \[f^{(k+1)}(x) = \frac{d}{dx}\left[(2^k x + k 2^{k-1}) e^{2x}\right] = \left(\frac{d}{dx}(2^k x + k 2^{k-1})\right) e^{2x} + (2^k x + k 2^{k-1}) \left(\frac{d}{dx} e^{2x}\right).\] <2>2. Compute the components: \[\frac{d}{dx}(2^k x + k 2^{k-1}) = 2^k, \qquad \frac{d}{dx} e^{2x} = 2 e^{2x}.\] <2>3. Combine and factor out \(e^{2x}\): \[f^{(k+1)}(x) = 2^k e^{2x} + 2(2^k x + k 2^{k-1}) e^{2x} = \left(2 \cdot 2^k x + 2^k + 2 k 2^{k-1}\right) e^{2x}\] \[= \left(2^{k+1} x + 2^k(1 + k)\right) e^{2x} = \left(2^{k+1} x + (k+1) 2^{(k+1)-1}\right) e^{2x}.\] This matches the formula for \(n = k+1\).

<1>4. Alternative derivation using Leibniz’s Rule: Proof: <2>1. Leibniz’s Rule states that \((u v)^{(n)} = \sum_{k=0}^n \binom{n}{k} u^{(n-k)} v^{(k)}\). <2>2. Let \(u(x) = x\) and \(v(x) = e^{2x}\). Then \(u^{(0)}(x) = x\), \(u^{(1)}(x) = 1\), and \(u^{(j)}(x) = 0\) for all \(j \ge 2\). Also \(v^{(k)}(x) = 2^k e^{2x}\) for all \(k \ge 0\). <2>3. The sum has only two non-zero terms (\(k=n\) and \(k=n-1\) for \(u^{(0)}\) and \(u^{(1)}\)): \[f^{(n)}(x) = \binom{n}{0} x (2^n e^{2x}) + \binom{n}{1} (1) (2^{n-1} e^{2x}) = (2^n x + n 2^{n-1}) e^{2x}.\]

<1>5. Conclusion: \(f^{(n)}(x) = (2^n x + n 2^{n-1}) e^{2x} = 2^{n-1}(2x + n)e^{2x}\) for all \(n \ge 0\).

1. It will exactly be the row space of \[ A = \left(\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 3 & 4 & 6 & 7 \\ 5 & 6 & 8 & 9 \end{array}\right), \] where we note that \(R_3 = 2R_1 + R_2\) but \(R_1 \neq \lambda R_2\) and so the first two rows span the correct subspace. We can also compute the RREF, which has the same rowspace, \[\tilde A = \left(\begin{array}{rrrr} 1 & 0 & -2 & -3 \\ 0 & 1 & 3 & 4 \\ 0 & 0 & 0 & 0 \end{array}\right)\] from which we find that \(\vector v_1 = \thevector{1,0,-2,-3}\) and \(\vector v_2 = \thevector{0,1,3,4}\) also do the job. \(\qed\)

Goal: Find a basis for the subspace \(W = \operatorname{span}\{(1,1,1,1), \, (3,4,6,7), \, (5,6,8,9)\} \subseteq \mathbb{R}^4\).

<1>1. Let \(v_1 = (1,1,1,1)\), \(v_2 = (3,4,6,7)\), and \(v_3 = (5,6,8,9)\). The subspace \(W\) equals the row space \(\operatorname{Row}(A)\) of the matrix: \[A = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 3 & 4 & 6 & 7 \\ 5 & 6 & 8 & 9 \end{pmatrix}.\]

<1>2. The reduced row echelon form (RREF) of \(A\) is: \[R = \begin{pmatrix} 1 & 0 & -2 & -3 \\ 0 & 1 & 3 & 4 \\ 0 & 0 & 0 & 0 \end{pmatrix}.\] Proof: <2>1. Apply elementary row operations: \(R_2 \gets R_2 - 3R_1\) and \(R_3 \gets R_3 - 5R_1\): \[\begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 3 & 4 \\ 0 & 1 & 3 & 4 \end{pmatrix}.\] <2>2. Apply \(R_3 \gets R_3 - R_2\) and \(R_1 \gets R_1 - R_2\): \[\begin{pmatrix} 1 & 0 & -2 & -3 \\ 0 & 1 & 3 & 4 \\ 0 & 0 & 0 & 0 \end{pmatrix}.\] This matrix is in RREF.

<1>3. Elementary row operations preserve the row space, so \(\operatorname{Row}(A) = \operatorname{Row}(R)\).

<1>4. The nonzero rows of \(R\), namely \(w_1 = (1, 0, -2, -3)\) and \(w_2 = (0, 1, 3, 4)\), form a basis for \(W\). Proof: <2>1. \(w_1\) and \(w_2\) span \(\operatorname{Row}(R) = W\) since the third row is zero. <2>2. \(w_1\) and \(w_2\) are linearly independent because their leading 1s occur in distinct columns (columns 1 and 2): \(c_1 w_1 + c_2 w_2 = (c_1, c_2, -2c_1+3c_2, -3c_1+4c_2) = (0,0,0,0) \implies c_1 = 0\) and \(c_2 = 0\). <2>3. Alternatively, the first two rows \(\{v_1, v_2\}\) of the original matrix also form a basis for \(W\) since \(\rank(A) = 2\) and \(v_1, v_2\) are linearly independent with \(v_3 = 2v_1 + v_2\). Hence \(\dim(W) = 2\) and \(\{(1,0,-2,-3), (0,1,3,4)\}\) is a basis for \(W\). Q.E.D.

<1>1. The characteristic polynomial of \(A\) is \(p_A(x)=x^3-x\).

<1>2. \(A^3=A\).

1. We first need the derivatives of \(\arctan\), since \[ T(p, x) = \sum_{n=0}^\infty \frac{f^{(n)}(p)}{n!}(x-p)^n \implies T(0, x) = \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!}x^n \]

   Starting with \(y=\arctan x\), we can write \(\tan y - x = 0 \implies \sec^2y~dy - 1~dx = 0\) by implicit differentiation and the chain rule, and so \(\dd{y}{x} = y' = \sec^{-2}y = \cos^2(\arctan x))\). Embed this in a triangle with angle \(y\) to find that \[y' = (1+x^2)^{-1}.\]

   Computing higher derivatives of \(\arctan\) directly is tedious, so instead we’ll take a power series of \(y'\) and differentiate that instead:

   \[\begin{align*} f'(x) = \inverseof{(1+x^2)} & =1 - x^2 + x^4 - x^6 + x^8 - x^{10} + \cdots = \sum_{i=0} (-1)^{i}x^{2i} \\ \implies f''(x) = \dd{}{x} \inverseof{(1+x^2)} &= -2x + 4x^3 - 6x^5 + \cdots = \sum_{i=1}^\infty (2i)(-1)^{i}x^{2i-1} \\ \implies f^{(3)}(x) = \dd{^2}{x^2} \inverseof{(1+x^2)} &= -2 + 12x^2 - 30x^4 + \cdots = \sum_{i=1}^\infty (2i )(2i-1)(-1)^{i}x^{2i-2} \\ \implies f^{(4)}(x) = \dd{^3}{x^3} \inverseof{(1+x^2)} &= 24x - 120x^3 + \cdots = \sum_{i=2}^\infty (2i)(2i-1)(2i-2)(-1)^{i}x^{2i-3} \\ \implies f^{(5)}(x) = \dd{^4}{x^4} \inverseof{(1+x^2)} &= 24 - 360x^2 + \cdots = \sum_{i=2}^\infty (2i)(2i-1)(2i-2)(2i-3)(-1)^{i}x^{2i-4} \\ \end{align*}\]

   so recalling that we’ll be evaluating at \(x=0\), we can notice that whenever \(n+1\) is even (and thus \(n\) is odd), there is no constant term. So for \(n+1\) odd, we can extract the general pattern: \[\begin{align*} f^{(n)}(0) &= \restrictionof{ \dd{^{n}}{x^{n}} \inverseof{(1+x^2)}}{x = 0} &= \begin{cases} (n-1)! & n-1 \equiv 0 \mod 4 \\ -(n-1)! & n -1 \equiv 2 \mod 4 \end{cases} \end{align*}\]

   Thus the desired Taylor expansion will be \[ T(0, x) = \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!}x^n \\ = \arctan(0) + \sum_{n>0\text{ odd}} \sigma_n \frac{(n-1)!}{n!} x^n \\ =\sum_{n>0\text{ odd}} \frac{\sigma_nx^n}{n} \]

   where \(\sigma_n = -1 \iff n \equiv 3 \mod 4\).

   We can then start writing this out: \[ T(0, x) = x - \frac 1 3 x^3 + + \frac{1}{5}x^5 - \frac 1 7 x^7 \]

   We then want an \(n\) such that \[\frac{(\frac{n-1}{2})!}{(n-1)!} (\frac 1 {10^2})^n \leq \frac 1 {10^5}.\]

   Checking manually, \(i=1\) does not work, but \(i=2\) does, so we take the approximation \[\widehat f(x) = x - \frac 1 3 x^3.\] \(\qed\)

Goal: Derive the Maclaurin series expansion of \(f(x) = \arctan(x)\) and determine a polynomial approximation accurate within \(10^{-5}\) for small \(|x| \le 10^{-2}\).

<1>1. For all \(x \in (-1, 1)\), \(f'(x) = \frac{1}{1+x^2} = \sum_{k=0}^\infty (-1)^k x^{2k}\).

<1>2. The Maclaurin series of \(\arctan(x)\) is \(T(0, x) = \sum_{k=0}^\infty \frac{(-1)^k}{2k+1} x^{2k+1} = x - \frac{x^3}{3} + \frac{x^5}{5} - \frac{x^7}{7} + \cdots\) for \(|x| < 1\).

<1>3. The derivatives of \(f\) at \(x=0\) satisfy: \[f^{(n)}(0) = \begin{cases} 0 & \text{if } n \text{ is even}, \\ (-1)^k (2k)! & \text{if } n = 2k+1 \text{ is odd}.\end{cases}\]

<1>4. For \(|x| \le 10^{-2}\), the polynomial approximation \(\widehat{f}(x) = x - \frac{x^3}{3}\) approximates \(\arctan(x)\) with error bounded by \(\frac{1}{5 \cdot 10^{10}} < 10^{-5}\).

1. Suppose \(f_n \rightrightarrows g\) with each \(f_n\) bounded; we want to show that all of the \(f_n\) are uniformly bounded by some \(M\), i.e. \[ \exists M \suchthat \forall x\in \RR, \forall n\in \NN, \quad \abs{f_n(x)} \leq M. \]

• Since each \(f_n\) is bounded, we can produce some \(M_n\) such that \(\abs{f_n(x)} \leq M < \infty\).
• Since \(f_n \rightrightarrows g\), we can give ourselves an epsilon of room and get an \(N\) such that \(n\geq N \implies \abs{f_n(x) - g(x)} < \varepsilon\). We then write \[ f_n(x) = f_n(x) - g(x) + g(x) - f_N(x) + f_N(x) \\ \implies \abs{f_n(x)} \leq \abs{f_n(x) - g(x)} + \abs{g(x) - f_N(x)} + \abs{f_N(x)} \\ \leq \varepsilon + \varepsilon + M_N \]

by the above two statements. But \(N<\infty\), so we can choose \(M = \max\theset{M_1, M_2, \cdots M_{N-1}, 2\varepsilon + M_N}\) as a uniform bound. Then just take \(\varepsilon \to 0\). (Maybe not necessary?)

Goal: Let \(E\) be a set, and let \((f_n)_{n=1}^\infty\) be a sequence of functions \(f_n: E \to \mathbb{R}\) such that each \(f_n\) is bounded on \(E\). Suppose \(f_n \to g\) uniformly on \(E\). Prove that the sequence \((f_n)_{n=1}^\infty\) is uniformly bounded on \(E\), i.e., there exists a constant \(M > 0\) such that \(|f_n(x)| \le M\) for all \(n \in \mathbb{N}\) and all \(x \in E\).

<1>1. Definition of uniform convergence: There exists an integer \(N \ge 1\) such that for all \(n \ge N\) and all \(x \in E\), \(|f_n(x) - g(x)| < 1\).

<1>2. For all \(n \ge N\) and all \(x \in E\), \(|f_n(x)| \le |f_N(x)| + 2\). Proof: <2>1. By the triangle inequality: \[|f_n(x) - f_N(x)| \le |f_n(x) - g(x)| + |g(x) - f_N(x)|.\] <2>2. For any \(n \ge N\), applying <1>1 gives \(|f_n(x) - g(x)| < 1\) and \(|f_N(x) - g(x)| < 1\). Thus \(|f_n(x) - f_N(x)| < 1 + 1 = 2\). <2>3. Again by the triangle inequality: \[|f_n(x)| \le |f_N(x)| + |f_n(x) - f_N(x)| < |f_N(x)| + 2.\]

<1>3. For each \(k \in \{1, 2, \dots, N\}\), there exists a constant \(M_k < \infty\) such that \(|f_k(x)| \le M_k\) for all \(x \in E\).

<1>4. Define \(M = \max\{M_1, M_2, \dots, M_{N-1}, M_N + 2\}\). Then \(|f_n(x)| \le M\) for all \(n \in \mathbb{N}\) and all \(x \in E\). Proof: <2>1. If \(1 \le n < N\), then for all \(x \in E\), \(|f_n(x)| \le M_n \le M\) by <1>3 and definition of \(M\). <2>2. If \(n \ge N\), then by <1>2 and <1>3: \[|f_n(x)| < |f_N(x)| + 2 \le M_N + 2 \le M.\] <2>3. In all cases, \(|f_n(x)| \le M\) for all \(n \in \mathbb{N}\) and all \(x \in E\).

<1>5. Conclusion: \((f_n)_{n=1}^\infty\) is uniformly bounded on \(E\).

Continuity of \(f_x\) and \(f_y\) at \((0,0)\) presupposes that both partial derivatives exist on some open disc \(B\) about \((0,0)\). Fix a direction \(\mathbf u=(u_1,u_2)\in\mathbb R^2\).

<1>1. For every sufficiently small \(h\neq0\) there are points \(\xi_h\) between \(0\) and \(hu_1\) and \(\eta_h\) between \(0\) and \(hu_2\) such that \[ f(hu_1,hu_2)-f(0,0)=f_x(\xi_h,hu_2)\,hu_1+f_y(0,\eta_h)\,hu_2. \]

<1>2. \(D_{\mathbf u}f(0,0)\) exists and equals \(f_x(0,0)u_1+f_y(0,0)u_2\).

<1>3. Q.E.D.

1. Note that \(8=2^3\) is a prime power \(p^n\), so we can get this as a quotient of a polynomial algebra. In particular, since \(p=2\), we’ll want to look at \(\FF_2[t]\), and we’ll want to quotient it by a polynomial of degree \(n=3\) that is irreducible in the base field \(\FF_2\).

   We could use Rabin’s test: \(f\) is irreducible over \(F\) iff \[ x^{p^n} - x \equiv 0 \mod f \quad\text{ and }\quad \left( f , x ^ { p ^ { n / q } } - x \right) = 1 ~~\forall \text{ prime $q$ dividing $n$} \]

   But I’m bad at polynomial division. With some work, we can brute force by listing out all of the \(2^4 = 16\) polynomials over \(\FF_2\) of degree at most 3. Then start multiplying together low-degree terms to cross off higher degree terms; using degree arguments you can show that the irreducible polynomials are: \[ x \\ x+1 \\ x^2 + x + 1 \\ x^3 + x + 1 \\ x^3 + x^2 + 1. \]

   So we can pick one of the degree 3 ones to obtain our desired field: \[ GF(8) = \frac{\FF_2[t]}{\generators{t^3+t+1}}. \qed \] General Principle Trinomials of the form \(x^n + ax^{<n} + b\) with \(a,b \in \FF_p\) are usually irreducible.

Goal: Construct a finite field with 8 elements, \(\mathbb{F}_8\), as a quotient of the polynomial ring \(\mathbb{F}_2[t]\).

<1>1. A field of order \(8 = 2^3\) can be constructed as \(\mathbb{F}_2[t]/\langle p(t)\rangle\), where \(p(t) \in \mathbb{F}_2[t]\) is an irreducible polynomial of degree \(3\). Proof: <2>1. \(\mathbb{F}_2[t]\) is a principal ideal domain because \(\mathbb{F}_2\) is a field. <2>2. For any irreducible polynomial \(p(t) \in \mathbb{F}_2[t]\), the ideal \(\langle p(t)\rangle\) is maximal. <2>3. Hence the quotient ring \(K = \mathbb{F}_2[t]/\langle p(t)\rangle\) is a field. <2>4. The dimension of \(K\) as an \(\mathbb{F}_2\)-vector space is \(\deg(p(t)) = 3\), so \(|K| = |\mathbb{F}_2|^3 = 2^3 = 8\).

<1>2. The polynomial \(p(t) = t^3 + t + 1 \in \mathbb{F}_2[t]\) is irreducible over \(\mathbb{F}_2\). Proof: <2>1. A polynomial of degree \(2\) or \(3\) over a field is reducible if and only if it has a root in the field. <2>2. The elements of \(\mathbb{F}_2\) are \(0\) and \(1\). <2>3. Evaluating \(p(t)\) at these points: \[p(0) = 0^3 + 0 + 1 = 1 \neq 0 \pmod 2,\] \[p(1) = 1^3 + 1 + 1 = 3 \equiv 1 \neq 0 \pmod 2.\] <2>4. Since \(p(t)\) has degree \(3\) and has no roots in \(\mathbb{F}_2\), \(p(t)\) is irreducible over \(\mathbb{F}_2\).

<1>3. Construction of \(\mathbb{F}_8\): \[\mathbb{F}_8 \cong \mathbb{F}_2[t]/\langle t^3 + t + 1\rangle = \{a_0 + a_1 \alpha + a_2 \alpha^2 \mid a_0, a_1, a_2 \in \mathbb{F}_2\},\] where \(\alpha = t \pmod{t^3+t+1}\) satisfies \(\alpha^3 = \alpha + 1\).