AMC12 2018 B

AMC12 2018 B · Q18

AMC12 2018 B · Q18. It mainly tests Sequences & recursion (algebra).

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$ 和对于所有整数 $n \geq 3$，$f(n) = f(n-1) - f(n-2) + n$ 递归定义。$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

AL.012 Sequences & recursion (algebra)