2018 AMC 10B Problem 20

A function

f

is defined recursively by

f(1) = f(2) = 1

and

f(n) = f(n - 1) - f(n - 2) + n

for all integers

n \ge 3.

What is

f(2018)?

Show solution

Solution

Notice

f(n) = n + 1

solves the recurrence on its own, so write

f(n) = (n + 1) + g(n).

Then

g

satisfies the homogeneous version

g(n) = g(n-1) - g(n-2).

With

g(1) = -1

and

g(2) = -2,

it cycles with period

6

-1, -2, -1, 1, 2, 1, \ldots.

Since

2018 \equiv 2 \pmod 6,

we get

g(2018) = -2,

f(2018) = 2019 - 2 = 2017.

Therefore, the answer is B.

Tagged: recursion · pattern recognition