13
$\begingroup$

In 1988, IMO presented a problem, to prove that $k$ must be a square if $a^2+b^2=k(1+ab)$, for positive integers $a$, $b$ and $k$. I am wondering about the solutions, not obvious from the proof. Beside the trivial solutions a or $b=0$ or 1 with $k=0$ or $1$, an obvious solution is $a=b^3$ so that the equation becomes $b^6+b^2=b^2(1+b^4)$ . Are there any other solutions?

$\endgroup$
  • 2
    $\begingroup$ There are some very detailed analyses of this problem here searchable with the words 'IMO 1988'. $\endgroup$ – zyx Sep 4 '13 at 7:48
  • 1
    $\begingroup$ mathoverflow.net/questions/250172/… $\endgroup$ – individ May 12 '17 at 4:40
11
$\begingroup$

This is a famous problem, here is one of the solutions that I like the most that I read it in a book previously, but later in a topic on here I realized the importance of the problem (The credit goes to T. Andreescu & R. Gelca If I remember it correctly, but I'm not sure, since 11 individuals in that year solved this problem and I'm not sure about their solutions):

Solution: Suppose that $\displaystyle \frac{a^2+b^2}{a.b+1}=x$ We want to prove that for every non-negative integer pairs $(\alpha,\beta)$ with the property that $\displaystyle \frac{\alpha^2+\beta^2}{\alpha\beta+1}=x$ and $\alpha \geq \beta$ the pair that minimizes $\alpha+\beta$ must imply $\beta=0$. If that happened, then $x=\alpha^2$. So, suppose that $(\alpha,\beta)$ is such a pair that minimizes $\alpha+\beta$ but $\beta>0$. then we can obtain the equation $y^2 - \beta xy + \beta^2 -x =0$ from $\displaystyle \frac{y^2+\beta^2}{y\beta+1}=x$. This equation has $\alpha$ as one of its roots and since the sum of the roots is $\beta x$, the other root must be $\beta x - \alpha$. Now if we prove that $0 \leq \beta x - \alpha < \alpha$ then we're done because this contradicts the minimality of $(\alpha,\beta)$

$x = \displaystyle \frac{\alpha^2+\beta^2}{\alpha\beta+1}<\frac{2\alpha^2}{\alpha \beta} = \frac{2 \alpha}{\beta} \implies \beta x-\alpha < \alpha$

and it's also possible to show that $\beta.x - \alpha \geq 0$ but honestly I don't remember that part of the proof and I leave it to you. That completes the proof.

(Also check that wikipedia link provided by pre-kidney).

$\endgroup$
6
$\begingroup$

The technique for this type of problem is called "Vieta root jumping". On the wikipedia page describing this technique, this very problem is used as an example. See here.

Of course there are many more solutions; we can enumerate them by flipping repeatedly and using symmetry. For example, your solution $(b, b^3)$ is the result of flipping $(b,0)$ when $k=b^2$. But if we flip around $b^3$ instead, we get the new solution $(b^5-b, b^3)$.

Indeed, $$x^2-b^5x+(b^6-b^2)=(x-b)(x-b^5+b)$$ so we also have $$b^6 + (b^5-b)^2 = b^2(1 + b^3(b^5-b))$$

$\endgroup$
3
$\begingroup$

All solutions can be written as: $$ \text{if $n$ is even:}\enspace a_n= { \sum\limits_{i=0}^{{n\over{2}}} {(-1)^{i+{n\over{2}}}{{n\over{2}}+i\choose {n\over{2}}-i}g^{4i+1}}} \\ \text{if $n$ is odd:}\enspace a_n= \sum\limits_{i=0}^{{n-1\over{2}}} (-1)^{i+{n-1\over{2}}}{1+{n-1\over{2}}+i \choose {n-1\over{2}}-i}g^{4i+3} \implies \\ {{a_n}^2+{a_{n+1}}^2\over{a_na_{n+1}+1}}=g^2\\ $$ Or also: $$ a_n={g{\bigg({g^2+\sqrt{g^4-4}\over{2}}\bigg)}^n\over{\sqrt{g^4-4}}} - {g{\bigg({g^2-\sqrt{g^4-4}\over{2}} \bigg)}^n\over{\sqrt{g^4-4}}} \\ $$

see here for complete solution

$\endgroup$
1
$\begingroup$

Supposing that

$$ \frac{a^2 + b^2}{ab + 1} = k$$ then

$$ a^2 - a(kb) + (b^2 - k) = 0 $$

So using quadratic formula gives: $$ a = \frac{kb \pm \sqrt{k^2b^2 -4(b^2 -k)}}{2}$$

The solutions are when $k = b^2 $ and thus $a= kb = b^3$

So $$ b = 1 , a = 1 , k= 1$$ $$b = 2 , a = 8, k = 4$$

$$ b= 3, a= 27, k = 9 $$ and so on....

There are other ways of getting more solutions than these such as b = 8, a = 30 and k = 4 where k is not $b^2$ or $a = b^3$ and of course the zero one. I have not yet found a way to find more solutions than this.

$\endgroup$
  • $\begingroup$ But what about for example $b=8,a=30,k=4$ ? Clearly we don't have : $ k=b^2$ or $a=b^3$. But nevertheless we have : $ \enspace \frac{8^2+30^2}{8.30+1}=4$.. $\endgroup$ – Rutger Moody Jun 30 '17 at 12:42
  • $\begingroup$ Oh yes, you are right. Thank you for that, I will look into this question more and will edit my answer. $\endgroup$ – Shrenik Jul 5 '17 at 8:53
1
$\begingroup$

Not quite a proof to the original IMO problem, but there definately is a very easy way to compute all possible answers. Also it demonstrates that here, Vieta jumping is basically just using symmetry to jump between the two solutions of the good old quadratic formula.

Nothing complicated below, but I haven't seen this explanation anywhere else.

Suppose: $$ {{a^2+b^2} \over {1+ab}} = c $$ Then using the quadratic formula to solve b (and a little rewriting) gives: $$ b = {ac \pm \sqrt {a^2 (c^2-4) + 4c} \over 2} $$ Using this we can compute all answers for any given c. Eg: assume c = 4. Then we get: $$ b = {a \cdot 4 \pm \sqrt {a^2 \cdot 12 + 16} \over 2} $$ We know that a = 0 will always provide a solution. That gives us: $$ a = 0 \Rightarrow b = {{0 \cdot 4\pm \sqrt {0 \cdot 12 + 16}} \over 2} = 2 \Rightarrow (a,b) = (0,2) $$ But because of the symmetry, if (0,2) is a solution, then (2,0) must also be a solution. And since the quadratic formula has 2 solutions, it will produce another solution. $$ a = 2 \Rightarrow \space b = {{2 \cdot 4 \pm \sqrt {4 \cdot 12 + 16}} \over 2} = 0 \space or \space 8 \Rightarrow (a,b) = (2,8) $$ $$ a = 8 \Rightarrow \space b = {{8 \cdot 4 \pm \sqrt {64 \cdot 12 + 16}} \over 2} = {32 \pm 28\over 2} = 2 \space or \space 30 \Rightarrow (a,b) = (8,30) $$ $$ a = 30 \Rightarrow \space b = {{30 \cdot 4 \pm \sqrt {900 \cdot 12 + 16}} \over 2} = {120 \pm 104\over 2} = 8 \space or \space 112 \Rightarrow (a,b) = (30,112) $$ Same can be done for c = 9, 16, 25, etc.

$\endgroup$
0
$\begingroup$

Here is my proof it may not be right i just found this this morning and am only a sophomore in highschool, and don't have any mathematics knowledge higher than AP calculus and have never heard of vieta jumping before which is the common solution, so i wanted to see if i could answer it without using that.

Let (a) and (b) be positive integers, and k=(a^2+b^2)/(ab+1). Show that if (k) is an integer then (k) is a perfect square.

(a) and (b) are interchangeable because,

k=(a^2+b^2)/(ab+1)=〖b^2+a〗^2/(ba+1)

So for every series there will be inverse, so, (a,b)=(b,a) ,

The first series is (0,n) because, when (a) is zero, (b) is any positive integer, (k) is the square of (b), so b=√k because,

(0^2+(√((k) ))^2)/(0(√((k) ))+1)=k which reduces to, (0+k)/1=k which then reduces further to, k=k which is all real numbers, in this case all positive integers.

This also works for (n,0) because of k=(a^2+b^2)/(ab+1)=〖b^2+a〗^2/(ba+1), so when (b) is zero and (a) is any positive integer, (k) is the square of (a), so a=√k.

The second series (n,n^3 ), because when (b) is the cube of (a), (k) is the square of (a) because, (a^2+(a^3 )^2)/(a(a^3 )+1)=a^2

so reducing,
(a^2+a^6)/(a^4+1)=a^2 then, a^2+a^6=a^2 (a^4+1) distribute, a^2+a^6=a^6+a^2 cancel like terms, 0=0 Once again all positive integers, this again works for (n^3,n), because k=(a^2+b^2)/(ab+1)=〖b^2+a〗^2/(ba+1), so when (a) is the cube of (b), (k) is the square of (b).

These are the only two possible series of integer solutions, because of the graphs of the values. Let (x=a) and (y=b), graph to curves between the points (0,0)-(2,8) and (0,0)-(8,2). (see graph 1), ignore all values less than zero. Then graph a vertical line at (a=n), where (n) is any positive integer, (see graph 2), the line only intersects twice once at point (z) which will always be, ∛n, and again at point (e), which will always be at〖 n〗^3. The same can be said for a horizontal line drawn at (b=n), however point (z) will be 〖 n〗^3, and (e) will be ∛n. There is also a horizontal and vertical line drawn on the (a) and (b) axis, which represents (0,n) and (n,0) which is the other solution series to the problem. Therefore (0,n), (n,0), (n,n3), and (n3,n), are the only four solution sets that are positive integers, and all of them end in answers that are also squares..

(graph 1) (graph 2)

Graphs cannot be seen on here but there it is a cubic and cube root graph.

$\endgroup$
  • 6
    $\begingroup$ Please learn MathJax. Also, if you are unsure that this is correct, then you might instead consider posting this as a new question with the tag [proof-verification] and a link to this question. $\endgroup$ – Em. Oct 29 '16 at 1:23
0
$\begingroup$

Let the following sequence of polynomials \begin{equation*} P_1(n)\,=\,n\,,\,\, P_2(n)\,=\,n^3,\ldots, P_{k+2}(n)\,=\,\frac{P^2_{k+1}(n)-n^2}{P_k(n)}, \,\,\,k\in\mathbb N, \end{equation*} which in fact have the following general formula \begin{equation} P_m(n)\,=\,\sum_{r=0}^{\left[\frac{m-1}{2}\right]} (-1)^r\,\left( \begin{array}{c} \!m\!-\!r\!-\!1\! \\ r \end{array} \right) \,n^{2m-4r-1}. \label{polunomial} \end{equation} Then one can show the following: If $a,b$ are positive integers with $b\ge a$, such that $$ \frac{a^2+b^2}{1+ab}=k $$ is also an integer, then $k$ is a perfect square, i.e., $k=n^2$, and there exists an $m\in\mathbb N$, such that $$ a=P_m(n)\quad\text{and}\quad b=P_{m+1}(n). $$

$\endgroup$
-1
$\begingroup$

The answer to this question is based on the method of Vieta Jumping.Graphing the given equation on a graph will give us hyperbolas with a certain pattern in solutions. Wikipedia have a page related to this topic.

$\endgroup$
-2
$\begingroup$

First, in Excel, I put the numbers in a column, and then arranged the equation in 3 columns based on the formula, and I realized that some of the remaining were zero, and then I became interested in the subject, and it took about 8 hours to realize that for all the real numbers, equation can be correct. If “r” is integer we can find integer numbers as like as “a” and “b” that Makes equation can be correct. If r is a real number we can find real numbers as like as “a” and “b” that Makes equation can be correct. Prove that for any real number such as “r”
We can make this equation r^2=(a^2+b^2 )/(ab+1 ) that a,b∈R (a^2+b^2 )/(ab+1 ) =A For the all of real numbers as “a” a ∈ R a^2=a^2 ①
a^4+1 = a^4+1 ⟹ (a^4+1)/(a^4+1 )=1 ② ① & ②⟹ a^2=a^2 (a^4+1 )/(a^4+1 )= (a^6+a^2 )/(a^4+1 ) = (a^2+a^6 )/(a(a^3 )+1) = B IF (A=B) ⟹ (a^2+b^2 )/(ab+1 ) = (a^2+a^6 )/(a(a^3 )+1) (If (m )/(n ) = (x )/y ⟹ my= nx) ⟹ (a^2+b^2) * ( a(a^3 )+1)=( ab+1) * ( a^2+a^6) a^6+a^2+a^4 b^2+b^2= a^3 b+a^7 b+a^2+a^6 a^4 b^2+b^2=a^3 b+a^7 b ⟹b^2 (a^4+1)=a^3 b(a^4+1)

b^2=a^3 b ⟹ {(b=0 ⟹ a^2/1=a^2 and the A is true for all of real numbers)/(b≠0 ⟹b=a^3 for all of real number )

We know that the set of real numbers is closed with multiplication Then we can make equation (r^2 = (a^2+b^2 )/(ab+1 ) ) for every real number Therefore for all integer numbers we can find two integer numbers that can make equation. If we select r from each set the other numbers must select from same set.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.