Square of an integer

Let a, b be positive integers such that ab +1 divides a^2+b^2. Show that

    \[\frac{a^2+b^2}{ab+1}\]

is the square of an integer.

Solution

This is a very well known problem. It first appeared in IMO 1988 held in Canberra, Australia. It even has its own Wikipedia page.

History Background

One of the organisers had sent this exercise to all professors of Number Theory to check if the exercise is original and try to solve it within 4 hours. No one was able to do so. However, one Bulgarian student managed to solve the problem in less than 4 hours ( his solution was fallen from the sky )  and for that he was awarded a special reward beyond the medal.

Solution

 

Choose integers a,b,k such that a^2+b^2=k(ab+1) Now, for fixed k, out of all pairs (a,b) choose the one with the lowest value of \min(a,b). Label b'=\min(a,b), a'=\max(a,b). Thus, a'^2-kb'a'+b'^2-k=0 is a quadratic in a'. Should there be another root, c', the root would satisfy: b'c'\leq a'c'=b'^2-k<b'^2\implies c'<b' Thus, c' isn’t a positive integer (if it were, it would contradict the minimality condition). But c'=kb'-a', so c' is an integer; hence, c'\leq 0. In addition, (a'+1)(c'+1)=a'c'+a'+c'+1=b'^2-k+b'k+1=b'^2+(b'-1)k+1\geq 1 so that c'>-1. We conclude that c'=0 so that b'^2=k.

This construction works whenever there exists a solution (a,b) for a fixed k, hence k is always a perfect square.

Read more

Nested radical inequality

Let n \in \mathbb{N}. Prove that

    \[\sqrt{2\sqrt[3]{3\sqrt[4]{4\cdots \sqrt[n]{n}}}}<2\]

Solution

The LHS is equal to 2^{1/2}3^{1/6} \cdots n^{1/n!} which by AM – GM is less or equal to

    \[\left( \frac{\sum_{k=2}^n (k/k!)}{\sum_{k=2}^n (1/k!)}\right)^{\sum_{k=2}^n (1/k!)} = \left(1 + \frac{1}{a_n} \right)^{a_n}\]

where a_n=\sum \limits_{k=2}^{n} \frac{1}{k!}. Since a_n \nearrow e-2 <2 it follows from Bernoulli inequality that \displaystyle \left(1 + \frac{1}{a_n} \right)^{a_n} <2.

Read more

No invertible matrices

Show that there do not exist invertible matrices A, B \in \mathcal{M}_n \left( \mathbb{C} \right) such that A^2+B^2 = ( A + B )^2 and A^3+B^3 = ( A + B)^3.

Solution

Suppose, on the contrary, that such matrices do exist. Then

    \[(A + B) ^2 = A^2 +B^2 \implies AB + BA = \mathbb{O} \implies AB = - BA\]

and also

    \[(A+B)^3 = A^3 + B^3 \implies A^2 B = - B^2 A\]

Using the fact that AB =-BA we deduce that

    \begin{align*} -BA^2 &= A^2B \\ &= A \cdot A B\\ &= -A B \cdot A\\ &= BA \cdot A \\ &= BA^2 \end{align*}

The last means that BA^2 =\mathbb{O} which is impossible because both A and B are invertible ( and so must be the product ). Hence, the conclusion follows.

Read more

Matrix determinant inequality

Suppose that all eigenvalues of A\in \mathcal{M}_n(\mathbb{R}) are positive real numbers. Show that

    \[\det \left( A + A^{-1} \right) \geq 2^n\]

Solution

Let the eigenvalues of A be \lamda_i , 1 \leq 1 \leq n. Consider the Jordan normal form of A;  this Jordan form is an upper triangular matrix that has the eigenvalues of A in the main diagonal. Let this matrix be called J.  Furthermore \det A = \det J , as a matrix and its Jordan normal form are similar. As J is upper triangular, its inverse is given by an upper triangular matrix whose diagonal entries are the inverses of the diagonal entries of J. That is,

    \[J +J^{-1} = \begin{pmatrix} \lambda_1+\lambda^{-1}_1 & & & & \\ 0 & \lambda_2+\lambda_2^{-1} & & U & \\ 0& 0 & \lambda_3+\lambda_3^{-1} & & \\ \vdots& \vdots & \vdots &\ddots &x \\ 0& 0 &0 &\cdots &\lambda_n +\lambda_n^{-1} \end{pmatrix}\]

is an upper-triangular matrix, and its determinant can be computed simply as the product of the elements of the diagonal. Hence,

    \[\det \left ( A + A^{-1} \right ) = \prod_{i=1}^{n} \left ( \lambda_i + \frac{1}{\lambda_i} \right ) \geq 2^n\]

due to the inequality x+\frac{1}{x} \geq 2 for all x>0.
Note: The main point here is that if \lambda is an eigenvalue of A then \frac{1}{\lambda} is an eigenvalue of A^{-1}. Taking into account that
 

    \[\det A = \prod_{i} \lambda_i\]

yields a shorter solution to the problem. No need for upper triangular matrices.

Read more

Root inequality

Let a, b, c be positive real numbers such that a+b+c=3. Prove that

    \[\sqrt{\frac{b}{a^3+3}} + \sqrt{\frac{c}{b^2+3}} + \sqrt{\frac{a}{c^2+3}} \leq \frac{3}{2} \sqrt[4]{\frac{1}{abc}}\]

Solution

Well if we apply AM-GM to (a^2, 1, 1, 1) we obtain

(1)   \begin{equation*} a^2+3 \geq 4 \sqrt{a} \end{equation*}

and similarly if we apply AM – GM to (b, b, b, c) we obtain

(2)   \begin{equation*} \frac{3b+c}{4} \geq \sqrt[4]{b^3c}\end{equation*}

We have successively,

\begin{aligned} \sqrt{\frac{b}{a^3+3}} + \sqrt{\frac{c}{b^2+3}} + \sqrt{\frac{a}{c^2+3}} &\overset{(1)}{\leq } \sqrt{\frac{b}{4\sqrt{a}}} + \sqrt{\frac{c}{4\sqrt{b}}} + \sqrt{\frac{a}{4\sqrt{c}}} \\ &=\frac{1}{2\sqrt[4]{abc}}\left ( \sqrt[4]{b^3c} +\sqrt[4]{c^3a}+ \sqrt[4]{a^3b}\right ) \\ &\overset{(2)}{\leq } \frac{1}{2 \sqrt[4]{abc}} \left ( \frac{3b+c}{4} + \frac{3c+a}{4} + \frac{3a+b}{4} \right )\\ &= \frac{3}{2} \sqrt[4]{\frac{1}{abc}} \end{aligned}

Read more