2016 AMC 12B Problem 25

Relevant wiki: Induction - Recurrence Relations

First, you start with the first part of the sequence: $1,\quad \sqrt[19]{2},\quad \sqrt[19]{2},\quad \sqrt[19]{2^3}\dotsm$

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,\quad 2^{\frac{1}{19}},\quad 2^{\frac{1}{19}},\quad 2^{\frac{3}{19}},\quad 2^{\frac{5}{19}}\dotsm$

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,\quad 1,\quad 3,\quad 5,\quad 11,\quad 21,\quad 43,\quad 85,\quad \dotsm$

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:

$2a_{n}+1=a_{n+1}\quad$ for all $n\in$ the set of all odd numbers.

$2a_{n}-1=a_{n+1}\quad$ for all $n\in$ the set of all even numbers.

To find the sum of all terms before that, use these equations:

$\sum \limits_{i=1}^{n} = 2a_{n}-1$ for all $n\in$ the set of all odd numbers.

$\sum \limits_{i=1}^{n} = 2a_n$ for all $n\in$ the set of all even numbers.

So, we can find the terms of this sequence up to $a_{20}$ :

$1,\quad 1,\quad 3,\quad 5,\quad 11,\quad 21,\quad 43,\quad 85,\quad 171,\quad 341,\quad 683,\quad 1365,\quad 2731,\quad 5461,\quad 10923, \\ 21825,\quad 43651,\quad 87301,\quad 174603,\quad 349205$

The sum of the first 15 terms is $2(10923)-1 = 21825$ , 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(21825) = 43650$ , which is NOT divisible by 19 (as you saw in the last example).

The sum of the first 17 terms is $2(43651)-1 = 87301$ , which IS divisible by 19.

Therefore, 17 is the smallest positive integer, $k$ .