2018 AMC 10B Problem 20

Question

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)?

2016

2017

2018

2019

2020

Look for a particular solution of the form

f(n) = n + c;

subtracting it leaves

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

That homogeneous recursion is periodic with period

6;

reduce

2018

modulo

6

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,

so

f(2018) = 2019 - 2 = 2017.

Therefore, the answer is B.

Problem 20 in other years