Let $a_1, a_2, a_3, . . . , a_n, . . . $ be an infinite sequence of natural numbers in which $a_1$ is not divisible by $5$. Suppose $a_{n+1} = a_n + b_n$ where bn is the last digit of $a_n$, for every $n$. Prove that the sequence $\{a_n\}$ contains infinitely many powers of 2.
Problem
Source: Indian Postal Coaching 2009 set 3 p1
Tags: Sequence, power of 2, recurrence relation, algebra
jelena_ivanchic
25.02.2021 19:35
A really nice problem, I think the idea was pretty cute, executing it was a bit bashy :p
For now consider only the last digit , if $a_1$ is odd then look at $a_2.$ Notice the digits are repeating in period $4$ cycle.
For example:- $a_1=12 $ then $ a_2= 24, a_3=28, a_4=56 , a_5=62$, so the unit digit is like $2\rightarrow 4 \rightarrow 8 \rightarrow 6 \rightarrow 2 \cdots$ and the cycle continues.
If $a_1$ is odd, then $a_2$ is even and the cycle will continue, like $a_1=7 \rightarrow a_2 =14 \rightarrow a_3=18 \rightarrow 26 \rightarrow 32 \cdots$ and the cycle continues.
So what we can say is if we have an even number $k$ in the sequence then we will also have $20+k$ too because of the cycle happening.
So if we can show that there are infinitely many powers of two which are $\{02,04,06,08,12,14,16,18\} \mod 100$ we will be done, because of the observation we got, every sequence will have at least one term of the set in the sequence infinitely times.
Now here come's the bashy part , we will show that the sequence will have infinitely many powers of $2,$ if at least one term of the set is there.
Case1: If in the sequence we have a term $02 \mod 100$ then by construction, the sequence will contain all the term $ 02 \mod 100$ in the sequence. But then powers of two $\mod 100$ will eventually start repeating in period , so there are infinitely many powers of $2$ of the form $ 02 \mod 100.$ And we have $2^1\equiv 02 \mod 100.$
Similarly for $04,08,12,16 \mod 100$ as all of these are $2^2,2^3,2^9,2^4 \mod 100.$
Case2: If in the sequence we have a term $06 \mod 100$ then by construction, the sequence will contain all the term $ 06 \mod 100$ in the sequence. Hence the sequence will contain all the terms $ 12\mod 100$ in the sequence, which we showed have infinitely many powers of $2.$
Similarly, we can proceed with $14,18.$
And we are done!