Maths Olympiad Prep

Track / Stage 7 / 284 of 300 #1684 of 1964

Problem 1684

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.8 Prove it

The sequence {xn} \{x_{n}\} is defined by x1\equal2,x2\equal12 x_{1} \equal{} 2,x_{2} \equal{} 12, and xn\plus2\equal6xn\plus1\minusxn x_{n \plus{} 2} \equal{} 6x_{n \plus{} 1} \minus{} x_{n}, (n\equal1,2,…) (n \equal{} 1,2,\ldots). Let p p be an odd prime number, let q q be a prime divisor of xp x_{p}. Prove that if q≠2,3, q\neq2,3, then q≥2p\minus1 q\geq 2p \minus{} 1.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Define the sequence and initial conditions:
The sequence {xn}\{x_n\} is defined by:
x1=2,x2=12,andxn+2=6xn+1−xnforn=1,2,… x_1 = 2, \quad x_2 = 12, \quad \text{and} \quad x_{n+2} = 6x_{n+1} - x_n \quad \text{for} \quad n = 1, 2, \ldots

2. Find the general form of the sequence:
We claim that the general form of the sequence is:
xn=122((3+22)n−(3−22)n) x_n = \frac{1}{2\sqrt{2}} \left( (3 + 2\sqrt{2})^n - (3 - 2\sqrt{2})^n \right)
We will prove this by induction.

3. Base Case:
For n=1n = 1:
x1=2=122((3+22)1−(3−22)1)=122(3+22−3+22)=2 x_1 = 2 = \frac{1}{2\sqrt{2}} \left( (3 + 2\sqrt{2})^1 - (3 - 2\sqrt{2})^1 \right) = \frac{1}{2\sqrt{2}} \left( 3 + 2\sqrt{2} - 3 + 2\sqrt{2} \right) = 2
For n=2n = 2:
x2=12=122((3+22)2−(3−22)2) x_2 = 12 = \frac{1}{2\sqrt{2}} \left( (3 + 2\sqrt{2})^2 - (3 - 2\sqrt{2})^2 \right)
Calculate (3+22)2(3 + 2\sqrt{2})^2 and (3−22)2(3 - 2\sqrt{2})^2:
(3+22)2=9+122+8=17+122 (3 + 2\sqrt{2})^2 = 9 + 12\sqrt{2} + 8 = 17 + 12\sqrt{2}
(3−22)2=9−122+8=17−122 (3 - 2\sqrt{2})^2 = 9 - 12\sqrt{2} + 8 = 17 - 12\sqrt{2}
Thus,
x2=122((17+122)−(17−122))=122(242)=12 x_2 = \frac{1}{2\sqrt{2}} \left( (17 + 12\sqrt{2}) - (17 - 12\sqrt{2}) \right) = \frac{1}{2\sqrt{2}} \left( 24\sqrt{2} \right) = 12

4. Induction Hypothesis:
Assume the result holds for n=kn = k and n=k−1n = k-1:
xk=122((3+22)k−(3−22)k) x_k = \frac{1}{2\sqrt{2}} \left( (3 + 2\sqrt{2})^k - (3 - 2\sqrt{2})^k \right)
xk−1=122((3+22)k−1−(3−22)k−1) x_{k-1} = \frac{1}{2\sqrt{2}} \left( (3 + 2\sqrt{2})^{k-1} - (3 - 2\sqrt{2})^{k-1} \right)

5. Induction Step:
We need to show it holds for n=k+1n = k+1:
xk+1=6xk−xk−1 x_{k+1} = 6x_k - x_{k-1}
Using the induction hypothesis:
xk+1=6⋅122((3+22)k−(3−22)k)−122((3+22)k−1−(3−22)k−1) x_{k+1} = 6 \cdot \frac{1}{2\sqrt{2}} \left( (3 + 2\sqrt{2})^k - (3 - 2\sqrt{2})^k \right) - \frac{1}{2\sqrt{2}} \left( (3 + 2\sqrt{2})^{k-1} - (3 - 2\sqrt{2})^{k-1} \right)
Simplify:
xk+1=122(6(3+22)k−6(3−22)k−(3+22)k−1+(3−22)k−1) x_{k+1} = \frac{1}{2\sqrt{2}} \left( 6(3 + 2\sqrt{2})^k - 6(3 - 2\sqrt{2})^k - (3 + 2\sqrt{2})^{k-1} + (3 - 2\sqrt{2})^{k-1} \right)
Using the recurrence relation:
(3+22)k+1=6(3+22)k−(3+22)k−1 (3 + 2\sqrt{2})^{k+1} = 6(3 + 2\sqrt{2})^k - (3 + 2\sqrt{2})^{k-1}
(3−22)k+1=6(3−22)k−(3−22)k−1 (3 - 2\sqrt{2})^{k+1} = 6(3 - 2\sqrt{2})^k - (3 - 2\sqrt{2})^{k-1}
Therefore,
xk+1=122((3+22)k+1−(3−22)k+1) x_{k+1} = \frac{1}{2\sqrt{2}} \left( (3 + 2\sqrt{2})^{k+1} - (3 - 2\sqrt{2})^{k+1} \right)
This completes the induction step.

6. Conclusion:
We have shown that:
xn=122((3+22)n−(3−22)n) x_n = \frac{1}{2\sqrt{2}} \left( (3 + 2\sqrt{2})^n - (3 - 2\sqrt{2})^n \right)

7. Prime divisor analysis:
Let pp be an odd prime number, and let qq be a prime divisor of xpx_p. We need to show that if q≠2,3q \neq 2, 3, then q≥2p−1q \geq 2p - 1.

8. Case analysis based on Legendre symbol:
- If (2p)=1\left( \frac{2}{p} \right) = 1, then 3±22=(1±2)2∈Fp3 \pm 2\sqrt{2} = (1 \pm \sqrt{2})^2 \in \mathbb{F}_p. By Fermat's Little Theorem:
xp−12=122((3+22)p−12−(3−22)p−12)≡0(modp) x_{\frac{p-1}{2}} = \frac{1}{2\sqrt{2}} \left( (3 + 2\sqrt{2})^{\frac{p-1}{2}} - (3 - 2\sqrt{2})^{\frac{p-1}{2}} \right) \equiv 0 \pmod{p}
- If (2p)=−1\left( \frac{2}{p} \right) = -1, then:
(1±2)p≡1±2(modp) (1 \pm \sqrt{2})^p \equiv 1 \pm \sqrt{2} \pmod{p}
Thus,
xp+12=122((3+22)p+12−(3−22)p+12)≡0(modp) x_{\frac{p+1}{2}} = \frac{1}{2\sqrt{2}} \left( (3 + 2\sqrt{2})^{\frac{p+1}{2}} - (3 - 2\sqrt{2})^{\frac{p+1}{2}} \right) \equiv 0 \pmod{p}

9. Conclusion:
If q≠2,3q \neq 2, 3, then q≥2p−1q \geq 2p - 1.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.