Given a sequence of of natural numbers a1, a2, a3, ... such that a1 is not a multiple of 5 and a(n+1)=a(n)+(the last digit of a(n)).

Prove that this sequence contains infinitely many integer powers of 2.
Ex: 33,36,42,44,48,56,62, 64,....128,.....256 etc

1.  only a1 can be odd.   a2,... will always be even.
2.  we only need to consider sequences starting with an even.
3.  no number in a sequence ever ends in zero.
4.  any sequence increases

5.  any starting number ends up becoming one of two sequences:  one has a1=2 and the other has a1=6.

proof:
the last digit of the sequence with a1=2 follows the cycle 2,4,8,6
call this sequence X
the last digit of the sequence with a1=6 follows the cycle 6,2,4,8
call this sequence Y
each cycle advances increases by 20, they do not contain the same number and they don't miss any even numbers (except those ending in 0)

6.  what is left to prove is that sequences X and Y each contain infinitely many powers of 2.

Looking closer at the digit in the tens place of the sequences.
With sequence X if the last digit is 2, 4 or 8 the tens place is even, odd if the last is 6.
With sequence Y if the last digit is 6 the tens place is even, odd if the last is 2,4,8.

Looking at the powers of 2.
The last digit cycles 2,4,8,6.
If the last digit is 4 or 8 the tens place is even, odd if the last is 2 or 6.

Specifically the powers of 2 cycle as follows
Ends in 2, 10s place is odd.  Sequence Y contains it.
Ends in 4, 10s place is even.  Sequence X contains it.
Ends in 8, 10s place is even.  Sequence X contains it.
Ends in 6, 10s place is odd.  Sequence X contains it.

Therefore,
If a sequence becomes sequence X it will contain 3/4 of the powers of 2 higher than a1.
If a sequence becomes sequence Y it will contain 1/4 of the powers of 2 higher than a1.

Posted by Jer on 2010-05-12 15:26:52