Olympiad Maths Prep

Library / /3 of 5

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αv1+3v1\alpha_v = 5\alpha_{v-1} + 3^{v-1}, v2v \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=5v1[1+35+(35)2++(35)v1]=12(5v3v), 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=5201932019=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:
52v1(mod4) and 32v1(mod4)52v+32v2(mod4), for all v1. 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=5220193220192a_{2^{2019}} = 5^{2^{2019}} - 3^{2^{2019}} we find:
v2(2a22019)=v2(522019322019)=v2(53)+v2(5+3)+v2(22019)1=1+3+20191=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.

Looking for a route rather than 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.