2013年全国高中数学联赛山西省预赛

$2^{200}-1$

采用数学归纳法．为此，将问题一般化，将具体数 $99$ 改为非负整数 $k$，考虑数列$$1,1,3,3,3^{2},3^{2},\cdots,3^{k},3^{k},$$其和为 $S_{k}$，今计算 $F_{k}=f(0)+f(1)+\cdots+f(S_{k})$ 的值．
下面通过计算猜想 $F_k$ 的递推公式．
$k=0$ 时数列有两项：$1,1$，则$$S_{0}=1+1+2.$$因为$$f(0)=1 , f(1)=2 , f(2)=1,$$所以\[F(0)=f(0)+f(1)+f(2)=4.\]$k=1$ 时数列有四项：$1,1,3,3$，则 $S_{1}=8$，而\[f(0)=1,f(1)=2,f(2)=1,f(3)=2,f(4)=4,f(5)=2,f(6)=1,f(7)=2,f(8)=1,\]于是$$F_{1}=f(0)+f(1)+\cdots+f(8)=16=4^{2}.$$据此猜想，对于数列 $1,1,3,3,3^{2},3^{2},\cdots,3^{k},3^{k}$（其和为 $S_{k}$），有\[F_{k}=f(0)+f(1)+\cdots+f(S_{k})=4^{k+1}.\cdots\cdots\text{ ① }\]下面用数学归纳法证明此猜想．
归纳基础 ① 式在 $k=0,1$ 时已验证．
递推证明假定 ① 式对于 $k$ 成立，即$$F_k=f(0)+f(1)+\cdots+f(s_k)=4^{k+1}.$$对 $k+1$，数列 $1,1,3,3,3^{2},3^{2},\cdots,3^{k},3^{k},3^{k+1},3^{k+1}$ 的和为 $S_{k+1}$，将集合 $A=\{0,1,\cdots,S_{k+1}\}$ 中的每个数 $n$ 表示成三进制形式：\[\begin{split}n&=a_{0}+a_{1}\cdot 3+a_{2}\cdot 3^{2}+\cdots+a_{k}\cdot 3^{k}+a_{k+1}\cdot 3^{k+1}\\&=n_{1}+a_{k+1}\cdots 3^{k+1},\cdots\cdots\text{ ② }\end{split}\]其中 $n_{1}=a_{0}+a_{1}\cdot 3+a_{2}\cdot 3^{2}+\cdots+a_{k}\cdot 3^{k},a_{j}\in\{0,1,2\}$．
情形一 $a_{k+1}=0$．
此时有$$n=n_{1},$$利用归纳假设，有 $F_{k}=4^{k+1}$ 种选法；
情形二 $a_{k+1}=1$．
此时有$$n=n_{1}+3^{k+1},$$从两个 $3^{k+1}$ 中取其一，有两种取法，对前段表达式 $n_{1}$ 用归纳假设，有 $2F_{k}=2\cdot 4^{k+1}$ 种选法；
情形三 $a_{k+1}=2$．
此时有$$n=n_{1}+2\cdot 3^{k-1},$$两个 $3^{k+1}$ 全取，有一种取法，对前段表达式 $n_{1}$ 用归纳假设，有 $F_{k}=4^{k+1}$ 种选法．
因此$$F_{k+1}=F_{k}+2F_{k}+F_{k}=4F_{k}=4^{k+2},$$即\[F_{k+1}=f(0)+f(1)+\cdots+f(S_{k+1})=4^{k+2},\]故 ① 式对于任何非负整数 $k$ 成立，因此有\[f(1)+\cdots+f(S_{k})=4^{k+1}-f(0)=4^{k+1}-1.\]取 $k=99$，得\[f(1)+f(2)+\cdots+f(S)=2^{200}-1.\]