2016 AMC 12B Problems/Problem 25
The sequence is defined recursively by , , and for . What is the smallest positive integer such that the product is an integer?
Let . Then and for all . The characteristic polynomial of this linear recurrence is , which has roots and .
Therefore, for constants to be determined . Using the fact that we can solve a pair of linear equations for :
Thus , , and .
Now, , so we are looking for the least value of so that
Note that we can multiply all by three for convenience, as the are always integers, and it does not affect divisibility by .
Now, for all even the sum (adjusted by a factor of three) is . The smallest for which this is a multiple of is by Fermat's Little Theorem, as it is seen with further testing that is a primitive root .
Now, assume is odd. Then the sum (again adjusted by a factor of three) is . The smallest for which this is a multiple of is , by the same reasons. Thus, the minimal value of is .
Since the product is an integer, the sum of the logarithms must be an integer. Multiply all of these logarithms by , so that the sum must be a multiple of . We take these vales modulo to save calculation time. Using the recursion : Listing the numbers out is expedited if you notice . Notice that . The cycle repeats every terms. Since and , we only need the first terms to sum up to a multiple of : . (NOTE: This solution proves 17 is the upper bound, but since 17 is the lowest answer choice, it is correct. To rigorously prove it, you will have to add up the mods listed until you get .
We are trying to find the given product, i.e. the sum of the powers should be an integer. Another way of thinking is that if we take only the numerators and sum it should be divisible by 19. So if we generate the first few terms, we get the sequence which is the Catalan sequence given by . Now we expand out the factorial:
So or .
|2016 AMC 12B (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25|
|All AMC 12 Problems and Solutions|