Maths Olympiad Prep

Library / IRL ABooklet /150 of 191

IRL ABooklet

Algebra Difficulty 6.7 National Olympiad Prove it Ireland

Let kk be a positive integer and let x0,x1,x2,…x_0, x_1, x_2, \dots be an infinite sequence defined by the relationship
x0=0x1=1xn+1=kxn+xn−1for all n≥1. \begin{align*} x_0 &= 0 \\ x_1 &= 1 \\ x_{n+1} &= kx_n + x_{n-1} \quad \text{for all } n \ge 1. \end{align*}

a. For the special case k=1k = 1, prove that xn−1xn+1x_{n-1}x_{n+1} is never a perfect square for n≥2n \ge 2.

b. For the general case of integers k≥1k \ge 1, prove that xn−1xn+1x_{n-1}x_{n+1} is never a perfect square for n≥2n \ge 2.

Solution

We claim that, for all n≥1n \ge 1,
xn−1xn+1=xn2+(−1)n.(10) x_{n-1}x_{n+1} = x_n^2 + (-1)^n. \qquad (10)
Based on this, if k>1k > 1 we then have xn=kxn−1+xn−2≥kxn−2≥k≥2x_n = kx_{n-1} + x_{n-2} \ge kx_{n-2} \ge k \ge 2 for n≥2n \ge 2, so xn2±1x_n^2 \pm 1 cannot be a square number. If k=1k = 1 then x2=2x_2 = 2 and xn=xn−1+xn−2≥xn−2≥2x_n = x_{n-1} + x_{n-2} \ge x_{n-2} \ge 2 for n≥3n \ge 3 and the same conclusion holds. With k=1k = 1 and n=2n = 2 we have xn−1xn+1=x1x3=2x_{n-1}x_{n+1} = x_1x_3 = 2 which is not a square number.

To prove (10) by induction, we first settle the base case n=1n = 1:
x0x2−x12=−1=(−1)1. x_0x_2 - x_1^2 = -1 = (-1)^1.
We now suppose that xn−1xn+1=xn2+(−1)nx_{n-1}x_{n+1} = x_n^2 + (-1)^n for some n≥1n \ge 1 and use the
recurrence relation xn+2=kxn+1+xnx_{n+2} = kx_{n+1} + x_n and kxn=xn+1−xn−1kx_n = x_{n+1} - x_{n-1} to find
xnxn+2=xn(kxn+1+xn)=kxnxn+1+xn2=(xn+1−xn−1)xn+1+xn2=xn+12−xn−1xn+1+xn2=xn+12−(xn2+(−1)n)+xn2=xn+12+(−1)n+1. \begin{align*} x_n x_{n+2} &= x_n (kx_{n+1} + x_n) \\ &= kx_n x_{n+1} + x_n^2 \\ &= (x_{n+1} - x_{n-1}) x_{n+1} + x_n^2 \\ &= x_{n+1}^2 - x_{n-1}x_{n+1} + x_n^2 \\ &= x_{n+1}^2 - (x_n^2 + (-1)^n) + x_n^2 \\ &= x_{n+1}^2 + (-1)^{n+1}. \end{align*}
This completes the proof by induction.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.