Maths Olympiad Prep

Library / Baltic Way Problem Shortlist /7 of 31

Baltic Way Problem Shortlist, 2011

Algebra Difficulty 7.6 National Olympiad, round 2 Prove it Baltic Way

Let {xn}\{x_n\} be a sequence of integers such that x0=ax_0 = a, x1=3x_1 = 3 and
xn=2xn−1−4xn−2+3 for all n>1. x_n = 2x_{n-1} - 4x_{n-2} + 3 \text{ for all } n > 1.
Determine the largest integer kk for which there exists a prime pp such that pkp^k divides x2011−1x_{2011} - 1.

Solution

Let yn=xn−1y_n = x_n - 1. Hence
yn=xn−1=2(yn−1+1)−4(yn−2+1)+3−1=2yn−1−4yn−2=2(2yn−2−4yn−3)−4yn−2=−8yn−3 y_n = x_n - 1 = 2(y_{n-1}+1)-4(y_{n-2}+1)+3-1 = 2y_{n-1}-4y_{n-2} = 2(2y_{n-2}-4y_{n-3})-4y_{n-2} = -8y_{n-3}
for all n>2n > 2. Hence
x2011−1=y2011=−8y2008=⋯=(−8)670y1=22011. x_{2011}-1=y_{2011}=-8y_{2008}=\cdots=(-8)^{670}y_1=2^{2011}.
Hence k=2011k = 2011.

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.