Problem 1 (yau-contest 2014)
Section: Combinatorics

Ming Antu (1692–1763) is one of the greatest Chinese/Mongolian mathematicians. In the 1730s, he first established and used what was later to be known as Catalan numbers (Euler (1707–1763) rediscovered them around 1756; Belgian mathematician Eugene Catalan (1814–1894) “rediscovered” them again in 1838),

$$c_n = \frac{1}{n+1}\binom{2n}{n},\quad n=0,1,2,\dots$$

and Ming Antu derived the following half-angle formula in 1730:

$$\sin^2 \frac{\theta}{2} = \sum_{n=1}^{\infty} c_{n-1}\left( \frac{\sin \theta}{2} \right)^{2n}.$$

Prove this formula.

Hint: you may use generating function

$$F(z) = \sum_{n=0}^{\infty} c_n z^n$$

and show that $\sum_{m+k=n} c_m c_k = c_{n+1}$ and then show $zF(z)^2 = F(z) - 1.$

Problem 2 (yau-contest 2014)
Section: Algebra

Many algorithms, including polynomial factorisation in finite fields, require to compute $\gcd\big(f(X), X^N - 1\big)$ for a polynomial $f$ of reasonably small degree $n$ and a binomial $X^N - 1$ of very large degree $N$. Since $N$ is very large the direct application of the Euclid algorithm is very inefficient.

Questions:

(i) Suggest a more efficient approach to the direct computation of $\gcd\big(f(X), X^N - 1\big)$ via the Euclid algorithm.

(ii) Generalise it to $\gcd\big(f(X), A_1 X^{N_1} + \dots + A_m X^{N_m} + A_{m+1}\big)$.

Hint: If for three polynomials $f$, $g$ and $h$ we have $g \equiv h \pmod f$ then $\gcd(f, g) = \gcd(f, h)$.

Problem 3 (yau-contest 2014)
Section: Numerical Analysis

For solving the following partial differential equation

$$u_t + f(u)_x = 0,\qquad 0 \le x \le 1 \tag{1}$$

where $f'(u) \ge 0$, with periodic boundary condition, we can use the following semi-discrete upwind scheme

$$\frac{d}{dt} u_j + \frac{f(u_j) - f(u_{j-1})}{\Delta x} = 0,\qquad j = 1,2,\dots,N, \tag{2}$$

with periodic boundary condition

$$u_0 = u_N, \tag{3}$$

where $u_j = u_j(t)$ approximates $u(x_j,t)$ at the grid point $x = x_j = j\Delta x$, with $\Delta x = \frac{1}{N}$.

(i) Prove the following $L^2$ stability of the scheme

$$\frac{d}{dt} E(t) \le 0 \tag{4}$$

where $E(t) = \sum_{j=1}^N |u_j|^2 \Delta x$.

(ii) Do you believe (4) is true for $E(t) = \sum_{j=1}^N |u_j|^{2p} \Delta x$ for arbitrary integer $p \ge 1$? If yes, prove the result. If not, give a counter example.

Problem 4 (yau-contest 2014)
Section: Numerical Linear Algebra

Let $A$ be an $n \times n$ matrix with real and positive eigenvalues and $b$ be a given vector. Consider the solution of $Ax = b$ by the following Richardson’s iteration

$$x^{(k+1)} = (I - \omega A) x^{(k)} + \omega b$$

where $\omega$ is a damping coefficient. Let $\lambda_1$ and $\lambda_n$ be the smallest and the largest eigenvalues of $A$. Let $G_\omega = I - \omega A$.

(i) Prove that the Richardson’s iteration converges if and only if

$$0 < \omega < \frac{2}{\lambda_n}.$$

(ii) Prove that the optimal choice of $\omega$ is given by

$$\omega_{\mathrm{opt}} = \frac{2}{\lambda_1 + \lambda_n}.$$

Prove also that

$$\rho(G_\omega) = \begin{cases}
1 - \omega\lambda_1, & \omega \le \omega_{\mathrm{opt}}, \\
(\lambda_n - \lambda_1)/(\lambda_n + \lambda_1), & \omega = \omega_{\mathrm{opt}}, \\
\omega\lambda_n - 1, & \omega \ge \omega_{\mathrm{opt}},
\end{cases}$$

where $\rho(G_\omega)$ is the spectral radius of $G_\omega$.

Problem (iii) (yau-contest 2014)

(iii) (8 points) Prove that, if $A$ is symmetric and positive definite, then
$$
\rho\big(G_{\omega_{\mathrm{opt}}}\big)=\frac{\kappa_2(A)-1}{\kappa_2(A)+1}
$$
where $\kappa_2(A)$ is the spectral condition number of $A$.

Problem 5 (yau-contest 2014)

5. (10 pts) For solving the following heat equation on interval
$$u_t=u_{xx},\quad 0\le x\le 1$$
with boundary condition
$$u(0)=u_0,\quad u(1)=u_1,$$
we first discretize the interval $[0,1]$ into $N$ subintervals uniformly, that is, the mesh size $h=1/N$. We choose a temporal step size $k$ and approximate the solution $u(jh,nk)$ by $U_j^n$, $j=1,\ldots,N-1$, $n=0,1,2,\ldots$ Using the backward Euler method in time and central finite difference in space, the discrete function $U_j^n$ satisfies:
$$U_j^{n+1}-U_j^n=\lambda( U_{j-1}^{n+1}-2U_j^{n+1}+U_{j+1}^{n+1}),\quad j=1,\ldots,N-1,$$
where $\lambda=k/h^2$, and
$$U_0^{n+1}=u_0,\quad U_N^{n+1}=u_1.$$
Show that
$$\frac12\sum_{j=1}^{N-1}\big((U_j^{n+1})^2-(U_j^n)^2\big)\le -\lambda\sum_{j=1}^{N-2}(U_{j+1}^{n+1}-U_j^{n+1})^2-\frac{\lambda}{2}\big((U_1^{n+1})^2+(U_{N-1}^{n+1})^2\big)+\frac{\lambda}{2}(u_0^2+u_1^2).$$