Maths Olympiad Prep

Library / /19 of 40

Algebra Difficulty 6.0 AIME, harder Prove it China

Suppose that the sequence {an}\{a_n\} defined by a1=a2=1a_1 = a_2 = 1, an=7an1an2a_n = 7a_{n-1} - a_{n-2}, n3n \ge 3. Prove that an+an+1+2a_n + a_{n+1} + 2 is a perfect square for any positive integer nn. (posed by Tao Pingsheng)

Solution

It is well known that the solution of the sequence can be obtained by solving two geometric sequences. We get an=C1λ1n+C2λ2na_n = C_1\lambda_1^n + C_2\lambda_2^n, where
λ1=7+452=(3+52)2,λ2=7452=(352)2, \lambda_1 = \frac{7 + \sqrt{45}}{2} = \left( \frac{3 + \sqrt{5}}{2} \right)^2, \quad \lambda_2 = \frac{7 - \sqrt{45}}{2} = \left( \frac{3 - \sqrt{5}}{2} \right)^2,
λ1\lambda_1 and λ2\lambda_2 are solutions of the equation λ27λ+1=0\lambda^2 - 7\lambda + 1 = 0, a1=1=C1λ1+C2λ2a_1 = 1 = C_1\lambda_1 + C_2\lambda_2, a2=1=C1λ12+C2λ22a_2 = 1 = C_1\lambda_1^2 + C_2\lambda_2^2.
Therefore,
an+an+1+2=λ1n1C1(λ1+λ12)+λ2n1C2(λ2+λ22)+2=λ1n1+λ2n1+2=((3+52)n1)2+((352)n1)2+2=[(3+52)n1+(352)n1]2=xn2, \begin{aligned} a_n + a_{n+1} + 2 &= \lambda_1^{n-1}C_1(\lambda_1 + \lambda_1^2) + \lambda_2^{n-1}C_2(\lambda_2 + \lambda_2^2) + 2 \\ &= \lambda_1^{n-1} + \lambda_2^{n-1} + 2 \\ &= \left( \left( \frac{3+\sqrt{5}}{2} \right)^{n-1} \right)^2 + \left( \left( \frac{3-\sqrt{5}}{2} \right)^{n-1} \right)^2 + 2 \\ &= \left[ \left( \frac{3+\sqrt{5}}{2} \right)^{n-1} + \left( \frac{3-\sqrt{5}}{2} \right)^{n-1} \right]^2 = x_n^2, \end{aligned}
where xn=(3+52)n1+(352)n1x_n = \left(\frac{3+\sqrt{5}}{2}\right)^{n-1} + \left(\frac{3-\sqrt{5}}{2}\right)^{n-1} is the solution of the sequence {xn}\{x_n\} of positive integers x1=2,x2=3,xn=3xn1xn2x_1 = 2, x_2 = 3, x_n = 3x_{n-1} - x_{n-2}, n3n \ge 3. \square

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.