AMC10 2018 B

AMC10 2018 B · Q20

AMC10 2018 B · Q20. It mainly tests Sequences & recursion (algebra), Patterns & sequences (misc).

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 \geq 3$. What is $f(2018)$?

函数 $f$ 通过如下递推定义：$f(1) = f(2) = 1$，且 \[f(n) = f(n-1) - f(n-2) + n\] 对所有整数 $n \geq 3$。求 $f(2018)$？

(A) 2016 2016

(B) 2017 2017

(D) 2019 2019

(E) 2020 2020

Answer

Correct choice: (B)

正确答案：（B）

Solution

Answer (B): Applying the recursion for several steps leads to the conjecture that $$ f(n)= \begin{cases} n+2 & \text{if } n\equiv 0\pmod{6},\\ n & \text{if } n\equiv 1\pmod{6},\\ n-1 & \text{if } n\equiv 2\pmod{6},\\ n & \text{if } n\equiv 3\pmod{6},\\ n+2 & \text{if } n\equiv 4\pmod{6},\\ n+3 & \text{if } n\equiv 5\pmod{6}. \end{cases} $$ The conjecture can be verified using the strong form of mathematical induction with two base cases and six inductive steps. For example, if $n\equiv 2\pmod{6}$, then $n=6k+2$ for some nonnegative integer $k$ and $$ \begin{aligned} f(n) &= f(6k+2)\\ &= f(6k+1)-f(6k)+6k+2\\ &= (6k+1)-(6k+2)+6k+2\\ &= 6k+1\\ &= n-1. \end{aligned} $$ Therefore $f(2018)=f(6\cdot 336+2)=2018-1=2017.$

答案（B）：将递推式应用若干步可得到如下猜想： $$ f(n)= \begin{cases} n+2 & \text{若 } n\equiv 0\pmod{6},\\ n & \text{若 } n\equiv 1\pmod{6},\\ n-1 & \text{若 } n\equiv 2\pmod{6},\\ n & \text{若 } n\equiv 3\pmod{6},\\ n+2 & \text{若 } n\equiv 4\pmod{6},\\ n+3 & \text{若 } n\equiv 5\pmod{6}. \end{cases} $$ 该猜想可用强数学归纳法验证：需要两个基例和六个归纳步骤。例如，若 $n\equiv 2\pmod{6}$，则对某个非负整数 $k$ 有 $n=6k+2$，并且 $$ \begin{aligned} f(n) &= f(6k+2)\\ &= f(6k+1)-f(6k)+6k+2\\ &= (6k+1)-(6k+2)+6k+2\\ &= 6k+1\\ &= n-1. \end{aligned} $$ 因此 $f(2018)=f(6\cdot 336+2)=2018-1=2017.$

Topics