Problem:
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≥3. What is f(2018) ?
Answer Choices:
A. 2016
B. 2017
C. 2018
D. 2019
E. 2020
Solution:
Applying the recursion for several steps leads to the conjecture that
f(n)=⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧n+2 if n≡0(mod6)n if n≡1(mod6)n−1 if n≡2(mod6)n if n≡3(mod6)n+2 if n≡4(mod6)n+3 if n≡5(mod6)
The conjecture can be verified using the strong form of mathematical induction with two base cases and six inductive steps. For example, if n≡2(mod6), then n=6k+2 for some nonnegative integer k and
f(n)=f(6k+2)=f(6k+1)−f(6k)+6k+2=(6k+1)−(6k+2)+6k+2=6k+1=n−1.
Therefore f(2018)=f(6⋅336+2)=2018−1=2017.
OR
Note that
f(n)=f(n−1)−f(n−2)+n=[f(n−2)−f(n−3)+(n−1)]−f(n−2)+n=−[f(n−4)−f(n−5)+(n−3)]+2n−1=−[f(n−5)−f(n−6)+(n−4)]+f(n−5)+n+2=f(n−6)+6.
It follows that f(2018)=f(2)+2016=2017.
The problems on this page are the property of the MAA's American Mathematics Competitions