Consider a sequence defined recursively for in the above manner.
What is the smallest positive integer value such that the product is an integer?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Relevant wiki: Induction - Recurrence Relations
First, you start with the first part of the sequence: 1 , 1 9 2 , 1 9 2 , 1 9 2 3 ⋯
That's too much to write (for most of us, at least). If you keep going on, the exponent inside the square root is going to get larger and larger. Let's convert this to exponential form.
2 0 , 2 1 9 1 , 2 1 9 1 , 2 1 9 3 , 2 1 9 5 ⋯
Still too much to write for most of us. Let's drop out the 2 and list only the exponents. And let's drop out the first term, because we don't need it anyway.
Multiply the exponents by 19 while you're at it. After all this, we get the sequence of:
1 , 1 , 3 , 5 , 1 1 , 2 1 , 4 3 , 8 5 , ⋯
To see how many terms of the sequence we need to multiply to get an integer, you must add that many terms of the sequence above and check whether it is divisible by 19. Given the answer choices, you should find out 15 of the terms before you start doing that.
The equations for finding the next terms are:
2 a n + 1 = a n + 1 for all n ∈ the set of all odd numbers.
2 a n − 1 = a n + 1 for all n ∈ the set of all even numbers.
To find the sum of all terms before that, use these equations:
i = 1 ∑ n = 2 a n − 1 for all n ∈ the set of all odd numbers.
i = 1 ∑ n = 2 a n for all n ∈ the set of all even numbers.
So, we can find the terms of this sequence up to a 2 0 :
1 , 1 , 3 , 5 , 1 1 , 2 1 , 4 3 , 8 5 , 1 7 1 , 3 4 1 , 6 8 3 , 1 3 6 5 , 2 7 3 1 , 5 4 6 1 , 1 0 9 2 3 , 2 1 8 2 5 , 4 3 6 5 1 , 8 7 3 0 1 , 1 7 4 6 0 3 , 3 4 9 2 0 5
The sum of the first 15 terms is 2 ( 1 0 9 2 3 ) − 1 = 2 1 8 2 5 , which is NOT divisible by 19. (The divisibility rule for 19 is to add two times the digit [opposite of 7, which is to subtract] to the remaining number).
The sum of the first 16 terms is 2 ( 2 1 8 2 5 ) = 4 3 6 5 0 , which is NOT divisible by 19 (as you saw in the last example).
The sum of the first 17 terms is 2 ( 4 3 6 5 1 ) − 1 = 8 7 3 0 1 , which IS divisible by 19.
Therefore, 17 is the smallest positive integer, k .