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+2nn−1nn+2n+3​ if n≡0(mod6) if n≡1(mod6) if n≡2(mod6) if n≡3(mod6) if n≡4(mod6) 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=(B)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=(B)2017​.
The problems on this page are the property of the MAA's American Mathematics Competitions