Maths Olympiad Prep

Library / /3 of 4

Algebra Difficulty 6.4 National olympiad Prove it North Macedonia

Determine whether there exists an infinite sequence a1,a2,a3,a_1, a_2, a_3, \dots of positive integers which satisfies the equality
an+2=an+1+an+1+an a_{n+2} = a_{n+1} + \sqrt{a_{n+1} + a_n}
for every positive integer nn.

Solutions — 4

Solution 1

The answer is no.
Suppose that there exist a sequence (an)(a_n) of positive integers satisfying the given condition. We will show that this will lead to a contradiction.
For each n2n \ge 2 define bn=an+1anb_n = a_{n+1} - a_n. Then, by assumption, for n2n \ge 2 we get bn=an+an1b_n = \sqrt{a_n + a_{n-1}} so that we have
bn+12bn2=(an+1+an)(an+an1)=(an+1an)+(anan1)=bn+bn1. b_{n+1}^2 - b_n^2 = (a_{n+1} + a_n) - (a_n + a_{n-1}) = (a_{n+1} - a_n) + (a_n - a_{n-1}) = b_n + b_{n-1}.
Since each ana_n is a positive integer we see that bnb_n is positive integer for n2n \ge 2 and the sequence (bn)(b_n) is strictly increasing for n3n \ge 3. Thus bn+bn1=(bnbn1)(bn+bn1)(bn+1+bn)b_n + b_{n-1} = (b_n - b_{n-1})(b_n + b_{n-1}) \ge (b_{n+1} + b_n), whence bn1bn+1b_{n-1} \ge b_{n+1} - a contradiction to increasing of the sequence (bi)(b_i).
Thus we conclude that there exists no sequence (an)(a_n) of positive integers satisfying the given condition of the problem.

Solution 2

Suppose that such a sequence exists. We will calculate its members one by one and get a contradiction.
From the equality a3=a2+a2+a1a_3 = a_2 + \sqrt{a_2 + a_1} it follows that a3>a2a_3 > a_2. Denote positive integers a3+a2\sqrt{a_3 + a_2} by bb and a3a_3 by aa, then we have 2a>b\sqrt{2a} > b. Since a4=a+ba_4 = a + b and a5=a+b+2a+ba_5 = a + b + \sqrt{2a + b} are positive integers, then 2a+b\sqrt{2a + b} is positive integer.
Consider a6=a+b+2a+b+2a+2b+2a+ba_6 = a+b+\sqrt{2a+b}+\sqrt{2a+2b+\sqrt{2a+b}}. Number c=2a+2b+2a+bc = \sqrt{2a+2b+\sqrt{2a+b}} must be positive integer, obviously it is greater than 2a+b\sqrt{2a+b}. But
(2a+b+1)2=2a+b+22a+b+1=2a+2b+2a+b+(2a+bb)+1>c2. (\sqrt{2a+b}+1)^2 = 2a+b+2\sqrt{2a+b}+1 = 2a+2b+\sqrt{2a+b}+(\sqrt{2a+b}-b)+1 > c^2.
So 2a+b<c<2a+b+1\sqrt{2a+b} < c < \sqrt{2a+b} + 1 which is impossible.

Solution 3

We will show that there is no sequence (an)(a_n) of positive integers which consists of N>5N > 5 members and satisfies
an+2=an+1+an+1+an(1) a_{n+2} = a_{n+1} + \sqrt{a_{n+1} + a_n} \quad (1)
for all n=1,2,,N2n = 1, 2, \dots, N-2. Moreover, we will describe all such sequences with five members.
Since every aia_i is a positive integer it follows from (1) that there exists such positive integer kk (obviously kk depends on nn) that
an+1+an=k2(2) a_{n+1} + a_n = k^2 \quad (2)
From (1) we have (an+2an+1)2=an+1+an(a_{n+2} - a_{n+1})^2 = a_{n+1} + a_n, consider this equality as a quadratic equation with respect to an+1a_{n+1},
an+12(2an+2+1)an+1+an+22an=0. a_{n+1}^2 - (2a_{n+2} + 1)a_{n+1} + a_{n+2}^2 - a_n = 0.
Obviously its solutions are (an+1)1/2=2an+2+1±D2(a_{n+1})_{1/2} = \frac{2a_{n+2}+1\pm\sqrt{D}}{2}, where
D=4(an+an+2)+1.(3) D = 4(a_n + a_{n+2}) + 1. \quad (3)
Since an+2>an+1a_{n+2} > a_{n+1} we have
an+1=2an+2+1D2. a_{n+1} = \frac{2a_{n+2} + 1 - \sqrt{D}}{2}.
From the last equality, using that an+1a_{n+1} and an+2a_{n+2} are positive integers, we conclude that DD is a square of some odd number i.e. D=(2m+1)2D = (2m+1)^2 for some positive integer mNm \in \mathbb{N}, substitute this into (3):
an+an+2=m(m+1).(4) a_n + a_{n+2} = m(m+1). \quad (4)
Now adding ana_n to both sides of (1) and using (2) and (4) we get m(m+1)=k2+km(m+1) = k^2 + k whence m=km = k. So
{an+an+1=k2an+an+2=k2+k(5) \begin{cases} a_n + a_{n+1} = k^2 \\ a_n + a_{n+2} = k^2 + k \end{cases} \quad (5)
for some positive integer kk (recall that kk depends on nn).
Write equations (5) for n=2n=2 and n=3n=3, then for some positive integers kk and ll we get
{a2+a3=k2a2+a4=k2+ka3+a4=l2a3+a5=l2+l.(6) \left\{ \begin{array}{l} a_2 + a_3 = k^2 \\ a_2 + a_4 = k^2 + k \\ a_3 + a_4 = l^2 \\ a_3 + a_5 = l^2 + l \end{array} \right. . \quad (6)
Solution of this linear system is
a2=2k2l2+k2,a3=l2k2,a4=l2+k2,a5=l2+2l+k2.(7) a_2 = \frac{2k^2 - l^2 + k}{2}, \quad a_3 = \frac{l^2 - k}{2}, \quad a_4 = \frac{l^2 + k}{2}, \quad a_5 = \frac{l^2 + 2l + k}{2}. \quad (7)
From a2<a4a_2 < a_4 we obtain k2<l2k^2 < l^2 hence k<lk < l.
Consider a6a_6:
a6=a5+a5+a4=a5+l2+l+k. a_6 = a_5 + \sqrt{a_5 + a_4} = a_5 + \sqrt{l^2 + l + k}.
Since 0<k<l0 < k < l we have l2<l2+l+k<(l+1)2l^2 < l^2 + l + k < (l+1)^2. So a6a_6 cannot be integer i.e. there is no such sequence with six or more members.
To find all required sequences with five members we must find positive integers a2,a3,a4a_2, a_3, a_4 and a5a_5 which satisfy (7) for some positive integers k<lk < l. Its clear that kk and ll must be of the same parity. Vice versa, let positive integers k,lk,l be of the same parity and satisfy k<lk<l then from (7) we get integers a2,a3,a4a_2, a_3, a_4 and a5a_5 then a1=(a3a2)2a2a_1=(a_3-a_2)^2-a_2 and it remains to verify that a1a_1 and a2a_2 are positive i.e. 2k2+k>l22k^2+k>l^2 and 2(l2k2k)2>2k2l2+k2(l^2-k^2-k)^2>2k^2-l^2+k.

Solution 4

It is easy to see that (an)(a_n) is increasing for large enough nn. Hence
an+1<an+2an(1) a_{n+1} < a_n + \sqrt{2a_n} \qquad (1)
and
an<an1+2an1(2) a_n < a_{n-1} + \sqrt{2a_{n-1}} \qquad (2)
Lets define bn=an+an1b_n = a_n + a_{n-1}. Using AM-QM inequality we have
2an+2an122an+2an12(3) \frac{\sqrt{2a_n} + \sqrt{2a_{n-1}}}{2} \le \sqrt{\frac{2a_n + 2a_{n-1}}{2}} \qquad (3)
Adding (1), (2) and (3):
bn+1<bn+2an+2an1bn+2bn. b_{n+1} < b_n + \sqrt{2a_n} + \sqrt{2a_{n-1}} \le b_n + 2\sqrt{b_n}.
Let bn=m2b_n = m^2. Since (bn)(b_n) is increasing for large enough nn we have:
m2<bn+1<m2+2m<(m+1)2. m^2 < b_{n+1} < m^2 + 2m < (m+1)^2.
So, bn+1b_{n+1} can't be a perfect square, so we get contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.