Home > Uncategorized > IMC 2017 – Day 2 – Solutions

IMC 2017 – Day 2 – Solutions

See the previous post for the statements of the problems.

Problem 6. We have that

$\displaystyle \int_0^1 f(nx) dx = \frac{1}{n} \int_0^n f(x)dx$

Suppose ${f(x) \geq L}$ for ${x > M}$. Then for ${n \gg M}$ we have

$\displaystyle \frac{1}{n} \int_0^n f(x) = \frac{1}{n} \int_0^M f(x) dx + \frac{1}{n}\int_M^n f(x) dx \geq \frac{1}{n} \int_0^M f(x)dx + \frac{n-M}{n}L.$

This shows that ${\displaystyle \liminf\limits_{n \rightarrow \infty} \frac{1}{n} \int_0^n f(x) dx \geq L}$. In the same way, having ${f(x) \leq L}$ for ${x>M}$ leads to ${\displaystyle \limsup_{n \rightarrow \infty} \frac{1}{n} \int_0^n f(x)dx \leq L}$.

Now all we need to do is to apply the above procedure to inequalities of the form ${f(x) \leq L+\delta}$ for ${x>M}$ and ${f(x) \geq L-\delta}$ for ${x>M}$, which come from the definition of the limit when ${x \rightarrow \infty}$. The case ${L}$ infinite is similar.

Problem 7. If all roots of ${q_n}$ are real then the sum of their square is non-negative. Suppose ${p}$ is a polynomial of degree ${d>0}$. If we denote ${w_1,...,w_{n+d}}$ are the roots of ${q_n}$ then

$\displaystyle 0 \leq \sum w_i^2 = \left(\sum w_i\right)^2-2\sum_{i

If ${q_n(x) = ax^{n+d}+bx^{n+d-1}+cx^{n+d-2}+...}$ then the previous inequality translates to

$\displaystyle 0 \leq \sum w_i^2 = \left( \frac{b}{a}\right)^2 - 2 \frac{c}{a},$

which is equivalent to ${b^2 - 2ac \geq 0}$. Now if we compute the coefficients ${a,b,c}$ for ${q_n}$ we find something which for ${n \rightarrow \infty}$ contradicts the previous inequality.

Problem 8. We start by observing that the eigenvalues of ${A_1}$ are ${1}$ and ${-1}$. Next, using the properties of block matrix determinants, we have the following equalities

$\displaystyle \det(A_{n+1}-\lambda I) = \det\begin{pmatrix} A_n-\lambda I & I \\ I & A_n-\lambda I \end{pmatrix} = \det((A_n-\lambda I)^2-I)$

$\displaystyle = \det(A_n-(\lambda+1)I)\det(A_n-(\lambda-1)I)$

The block determinant formula holds if ${(A_n-\lambda I)}$ is invertible. This happens for all but finitely many values of ${\lambda}$ (the eigenvalues of ${A_n)}$). Moreover, since the above equalities are polynomial equalities, this implies equality for every ${\lambda}$. Therefore, for each eigenvalue ${\lambda}$ of ${A_n}$ (multiplicity accounted) we have ${\lambda+1}$ and ${\lambda-1}$ as eigenvalues for ${A_{n+1}}$.

Therefore the eigenvalues of ${A_n}$ are

• ${A_2: \ \{-2,0,0,2\}}$
• ${A_3: \ \{-3,-1,-1,-1,1,1,1,3 \}}$
• ${A_4: \ \{-4,-2,-2,-2,-2,0,0,0,0,0,0,2,2,2,2,4\}}$

Note that a phenomenon similar to the Pascal triangle appears, which makes that adjacent eigenvalues of ${A_n}$ (which have a difference equal to ${2}$) with multiplicities ${{n\choose k}}$ and ${{n\choose k+1}}$ generate an eigenvalue of ${A_{n+1}}$ with multiplicity ${{n\choose k}+{n\choose k+1}={n+1 \choose k+1}}$

Problem 9. Elementary techniques in ODE show that ${\displaystyle f_{n+1}(x) = \exp(\int_0^x f_n(t)dt)}$. We note that ${f_1 = 1}$ and ${f_2(x) = e^x}$. Therefore ${f_1\leq f_2}$ on ${[0,1]}$. This implies, using a recurrence argument, that ${f_n(x) \leq f_{n+1}(x)}$. This shows that ${\lim_{n \rightarrow \infty} f_n(x)}$ exists for ${x\in [0,1]}$, but, for now, might be infinite.

In order to find an upper bound we may look what is the equation satisfied by an eventual limit ${F}$ of ${f_n}$ as ${n \rightarrow \infty}$. We arrive at the ODE ${F' = F^2,\ F(0)=1}$. It is immediate to see that ${F(x) = \frac{1}{1-x}}$. Now we would like to prove that ${f_n \leq F}$ on ${[0,1)}$, and for this we define ${g_n = f_n-F}$. Using ${f_n \leq f_{n+1}}$ and the hypothesis we get ${f_{n+1}' \leq f_{n+1}^2}$. Using this we have

$\displaystyle g_n' = f_n'-F' \leq f_n^2 - F^2=g_n(f_n+F)$

and ${g_n(0)=0}$. This implies that

$\displaystyle \left( g_n \exp(-\int_0^x (f_n+F)) \right)'\leq 0$

This implies easily that ${g_n \leq 0}$ on ${[0,1)}$, which means that ${f_n \leq F}$ on ${[0,1)}$. Thus the pointwise limit of ${f_n}$ exists. Let’s denote it by ${G}$. Since ${f_n \leq f_{n+1}}$ using the monotone convergence theorem we have the convergence of integrals ${\int_0^x f_n(t)dt = \int_0^x G(t)dt}$. Thus the limit satisfies

$\displaystyle G(x) = \exp\left(\int_0^x G(t)dt\right).$

Therefore ${G}$ satisfies ${G'=G^2}$ and ${G(0)=1}$ which means that the limit is indeed ${G(x) = 1/(1-x)}$ for ${x \in [0,1)}$.