Home > Numbers > Sequences
Integers only (Posted on 2014-03-31 )

What is the smallest pair (a_{1} ,a_{2} ) of integers (a_{1} , less than a_{2} ) to provide a list of 24 integers using a recurrent function a_{(n)} =(a_{(n-1)} +a_{(n-2)} )/2 ?

Generalised approach
| Comment 6 of 7 |

Assuming a_{n} proportional to m^{n} , the equation a_{n} = (a_{n-1} + a_{n-2} )/2 yields the auxiliary equation m^{2} = m/2 + ½ with roots 1 and -1/2, giving the general solution: a_{n} = A(1)^{n} + B(-1/2)^{n} where A and B are constants. Using the first two terms gives a_{1} = A – B/2 and a_{2} = A + B/4, so that A = (a_{1} + 2a_{2} )/3, B = 4(a_{2} – a_{1} )/3 and the general solution is: a_{n} = (a_{1} + 2a_{2} )/3 + 4(a_{2 } – a_{1} )/(3*(-2)^{n} ) Thus a_{24} = (1/3)[a_{1} + 2a_{2} + 4(a_{2} – a_{1} )/2^{24} ] = (1/3)[a_{1} + 2a_{2} + (a_{2} – a_{1} )/2^{22} ] So for a_{24} to be an integer, (a_{2} – a_{1} ) must be divisible by 2^{22} , and for a_{1} and a_{2} to be as close together as possible, we need a_{2} – a_{1} = 2^{22} , which gives a_{24} = (a_{1} + 2a_{2} + 1)/3 = (a_{1} + 2(a_{1} + 2^{22} ) + 1)/3 = (3a_{1} + 2*2^{22} + 1)/3 (1) Now, 2^{2} = 1 (mod 3), so 2*2^{22} = 2*(2^{2} )^{11} = 2*1^{11} = 2 (mod 3) and this makes the numerator in (1) a multiple of 3, showing that a_{2} – a_{1} = 2^{22} is a sufficient condition for a_{24} to be an integer. If only positive integers are allowed for (a_{1} , a_{2} ) then choose (1, 2^{22} + 1). If zero is allowed then (0, 2^{22} ) is best, as Jer recommended. If all integers are allowed then (-2^{21} , 2^{21} ) have the smallest abs. values, but (-2796202, -2796202 + 2^{22} ) will also work as tomarken found.
Posted by Harry
on 2014-03-31 21:53:28

Please log in:
Forums (5)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox: