Maths Olympiad Prep

Library / Hellenic Mathematical Olympiad /28 of 57

Hellenic Mathematical Olympiad

Algebra Difficulty 6.1 National Olympiad Prove it Greece

The sequence αv\alpha_v satisfies the recurrence relation: α1=1\alpha_1 = 1 and αv=5αv−1+3v−1\alpha_v = 5\alpha_{v-1} + 3^{v-1}, v≥2v \ge 2. Determine the general term αv\alpha_v and the greatest power of 22 which divides the term aka_k, where k=22019k=2^{2019}.

Solution

αv=5v−1⋅[1+35+(35)2+⋯+(35)v−1]=12(5v−3v), v=1,2,… \alpha_v = 5^{v-1} \cdot \left[ 1 + \frac{3}{5} + \left(\frac{3}{5}\right)^2 + \dots + \left(\frac{3}{5}\right)^{v-1} \right] = \frac{1}{2}(5^v - 3^v),\ v = 1, 2, \dots
Now for k=22019k=2^{2019}, we have: 2ak=52019−32019=2⋅(5+3)(52+32)…(52018+32018)2a_k = 5^{2019} - 3^{2019} = 2 \cdot (5+3)(5^2+3^2) \dots (5^{2018} + 3^{2018}), and hence:
ak=(5+3)(52+32)…(52018+32018). a_k = (5+3)(5^2+3^2)\dots(5^{2018}+3^{2018}).
We observe that the first factor is divided by 88 and all the others are divided by 22 and are not divided by 44. In fact, we have:
52v≡1(mod4) and 32v≡1(mod4)⇒52v+32v≡2(mod4), for all v≥1. 5^{2v} \equiv 1 \pmod{4} \text{ and } 3^{2v} \equiv 1 \pmod{4} \Rightarrow 5^{2v} + 3^{2v} \equiv 2 \pmod{4}, \text{ for all } v \ge 1.

The factors from 52+325^2 + 3^2 to (522018+322018)(5^{2^{2018}} + 3^{2^{2018}}), are totally 20182018, and therefore the greatest power of 22 dividing aka_k is 220212^{2021}.

Alternatively, we can use a special form of the Lifting the Exponent Lemma concerning the greatest power of 22 dividing a difference of powers of integers. We denote by vp(α)v_p(\alpha) the greatest exponent of power of a prime number pp which divide the integer α\alpha, that is: pvp(α)∣αp^{v_p(\alpha)}|\alpha and pvp(α)+1∤αp^{v_p(\alpha)+1} \nmid \alpha. We have the following:

Lemma: Let α,β\alpha, \beta two odd integers and vv an even positive integer. Then:
v2(αv−βv)=v2(α−β)+v2(α+β)+v2(v)−1. v_2(\alpha^v - \beta^v) = v_2(\alpha - \beta) + v_2(\alpha + \beta) + v_2(v) - 1.
By applying the lemma to the integer 2a22019=522019−3220192a_{2^{2019}} = 5^{2^{2019}} - 3^{2^{2019}} we find:
v2(2a22019)=v2(522019−322019)=v2(5−3)+v2(5+3)+v2(22019)−1=1+3+2019−1=2022, v_2(2a_{2^{2019}}) = v_2(5^{2^{2019}} - 3^{2^{2019}}) = v_2(5-3) + v_2(5+3) + v_2(2^{2019}) - 1 = 1 + 3 + 2019 - 1 = 2022,
and hence: v2(ak)=2021v_2(a_k) = 2021.

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.