【附】为方便编辑，特附“纯文本”如下。另外，文末提供有PPT照片版。
跃峰奥数PPT1代数组合3-3
（研究特例建立递归之分段递归）
【代数3-3】设f（n）是定义在正整数集上的函数，且对任何正整数n，有
f（1）=f（2）=1，f（3n）=f（n）+2016，
f（3n+1）=3f（n）+2017，f（3n+2）=2017f（n）。
令An={i|1≤i≤n，f（i）为奇}，Bn={i|1≤i≤n，f（i）为偶}。
（1）求证：对任何正整数n，有|An|>|Bn|；
（2）试确定f（2019）的奇偶性。（冯跃峰编题）
【题感】从目标看，本题属于计数不等式问题，先应理解|An|的意义，它是序列{f（n）}的前n项中为奇的项的个数。由此可见，本题实际上是证明：序列{f（n）}的前n项中为奇的项多于为偶的项。
由于目标中只关心数列{f（n）}各项的奇偶性，从而可用模2来处理题给的递归关系，使其变得简单。
【命题转换】在模2的意义下，我们有
f（1）=f（2）=1，f（3n）≡f（n），
f（3n+1）≡f（n）+1，f（3n+2）≡f（n）。
为了证明|An|>|Bn|，自然的想法是，先明确为奇（偶）的项有何特征，这可从初值试验开始。
【研究特例】当n=1，2，…，18时，f（n）的奇偶性如下表所示，其中1表示奇数，0表示偶数：
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
f（n）1 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 1
由于“0”出现次数较少，我们观察“0”子列在整个数列中的分布，你有何发现？
直观感觉：“0”的分布很“稀疏”——
【充分条件】任何两个“0”不相邻，由此很容易证明|An|>|Bn|。
如何证明上述结论？我们需要知道究竟是哪些项为偶。
为此，观察使f（n）为偶的n构成的子列：
4，7，10，12，14，16，18，…
似乎难以发现该子列各项的共同特征，可换一种进制来试试。
换哪种进制好呢？这自然要依赖于题给的递归关系。
——宜用3进制，因为题给的递归关系是以模3分类的！
那么，这里的“模3分类”与“3进制数”这两个“3”是纯属某种巧合，还是有必然联系？它们是有紧密联系的：将“n”用3进制表示后，可方便选择使用哪个“递归分支”。这是因为，若n=（akak-1…a1a0）（3），则n≡a0（mod3）。
此外，相关计算也很方便：
3n=（akak-1…a1a00）（3），3n+1=（akak-1…a1a01）（3），3n+2=（akak-1…a1a02）（3）。
【换系观察】现在，我们将上表中的数都用3进制表示，看能否有新的发现：
n 1 2 10 11 12 20 21 22 100 101 102 110 111 112
f（n）1 1 1 0 1 1 0 1 1 0 1 0 1 0
同样，只观察那些使f（n）为偶的三进制数n构成的子列：
n=11，21，101，110，112，
你能否发现它们的共同特征？
先看前面3个数：11、21与101的共同点是个位数相同。但第4个数110却不具备这一特点，从而个位相同的特征不是普适的，需要拓广。
【特征拓广】我们将101与110比较，其共同点是：首位相同。我们期望末两位“能看成相同”！这就要拓广“相同”的意义——末两位所含数字的集合相同（都是0、1的一个排列）。
由“一个排列”，想到考察整体求和。这样，性质可拓展到“末两位数字和相同”。下面再看其性质如何拓展到第5项。
考察101、110、112的末两位数字，尽管它们末两位数字和不尽相同，但其和的奇偶性相同。
【概括】后几位数字之和同奇偶，等价于“去掉首尾后”数字之和同奇偶。
【整体思考】使f（n）为偶的三进制数n，其三进制“去掉首位后”，各数字和都是奇数。
进一步发现，上述性质也适用使f（n）为奇的三进制数n：其三进制除首位后，各数字和都是偶数。
统一表述为：f（n）与S（n'）（n的3进制剔除首位后数字之和）不同奇偶。
实际上，将上表中的3进制数的第一个数码划掉，得到如下简化数表，则一目了然：
n' 0 0 0 1 2 0 1 2 0 1 2 10 11 12
f（n） 1 1 1 0 1 1 0 1 1 0 1 0 1 0
【整体函数】对于n的三进制数：n=（akak-1…a1a0）（3），其中ak≠0，定义整体函数：S-（n）=ak-1+ak-2+…+a1+a0（剔除了首位）。
其中规定，当k=0（n为一位三进制数）时，S-（n）=0。
这样，上述发现可表述为下面的引理。
引理1：对任何正整数n，f（n）≡S-（n）+1（mod2）。
证明：当n=1时，结论显然成立。设结论对小于n的正整数成立，考虑n的情形。
从目标等式f（n）≡S-（n）+1（mod2）看，可分别计算f（n）、S-（n）。其中S-（n）是已知的：S-（n）=ak-1+ak-2+…+a1+a0，关键是如何计算f（n）（mod2），为了利用归纳假设，只需先利用递归关系，将n化为小于n的情形即可。
为了利用分段递归关系，需要将n的三进制表示：n=（akak-1…a1a0）（3）（ak≠0）模3分类，即化成3m+r的形式——这只需将其末位数字单独分离出来即可！
因为n=（akak-1…a1a0）（3）=（akak-1…a10）（3）+a0≡a0（mod3），所以只需对a0的值分类运用递归关系。
（1）若a0=0，则n=（akak-1…a10）（3）=3（akak-1…a1）（3），此时，
f（n）=f（3（akak-1…a1）（3））
f（（akak-1…a1）（3））
S-（（akak-1…a1）（3））+1=ak-1+ak-2+…+a1+1≡S-（n）+1（mod2），结论成立。
（2）若a0=1，则n=（akak-1…a11）（3）=3（akak-1…a11）（3）+1，此时，
f（n）=f（3（akak-1…a1）（3）+1）
f（（akak-1…a1）（3））+1
S-（（akak-1…a1）（3））+1+1=ak-1+ak-2+…+a1+2≡S-（n）+1（mod2），结论成立。
（3）若a0=2，则n=（akak-1…a12）（3）=3（akak-1…a1）（3）+2，此时，
f（n）=f（3（akak-1…a1）（3）+2）
f（（akak-1…a1）（3））
S-（（akak-1…a1）（3））+1=ak-1+ak-2+…+a1+1≡S-（n）+1（mod2），结论成立。
综合（1）（2）（3），引理1获证。
注：递归关系可合并为f（3n+r）≡f（n）+r（0≤r≤2），可避免分类，证明更简洁。
由引理1，不难证明前面发现的如下结论：
引理2：对任何正整数n，每相邻两个项f（n）、f（n+1）中至少有一个为奇数。
证明：由引理1可知，f（n）、f（n+1）中至少有一个为奇数，等价于S-（n）、S-（n+1）中至少有一个为偶数。
对于这种“多可能性”的结论（或者S-（n）为偶、或者S-（n+1）为偶），可假定其中一个成立，则结论显然成立。但其中一个未必成立，可以此为标准分类讨论。
【充分条件分类】如果S-（n）为偶数，则结论成立。
下设S-（n）为奇数。如何利用这一“增设条件”？
——由S-（n）的定义，可先设出n的三进制表示。
设n=（akak-1…a1a0）（3）（ak≠0），则S-（n）=ak-1+ak-2+…+a1+a0为奇数。
以下只需将S-（n+1）也用ak-1，ak-2，…，a0来表示，然后证明其为偶数。
注意到n=（akak-1…a1a0）（3）（ak≠0），我们关心n=（akak-1…a1a0）（3）与1相加时，在三进制加法中是否有进位，这分a0是否大于1讨论即可。
（1）如果a0≤1，则n与1相加没有进位，此时
n+1=（akak-1…a1（a0+1））（3），所以
S-（n+1）= ak-1+ak-2+…+a1+（a0+1）为偶数，结论成立。
（2）如果a0=2，则n与1相加有进位。此时由S-（n）=ak-1+ak-2+…+a1+a0为奇数可知，ak-1，ak-2，…，a1，a0中至少有一个不为2，不妨设i是使ai≠2的最小下标（1≤i≤k-1），即n=（akak-1…ai22…2）（3）（ai≠2，1≤i≤k-1），此时
n+1=（akak-1…ai（ai+1）00…0）（3）（有进位），
S-（n+1）=ak-1+ak-2+…+（ai+1）+0+…+0
≡ak-1+ak-2+…+（ai+1）+2+…+2=S-（n）+1≡0（mod2），
所以S-（n+1）为偶，结论成立，引理2获证。
以下解答原题则轻而易举。
【解答原题】（1）采用跨度为2的归纳法。
如果n=1、2，由f（1）=f（2）=1，知结论成立。
设结论对n成立，即|An|>|Bn|，考虑n+2的情形。
由引理2，|An+2|≥|An|+1，|Bn+2|≤|Bn|+1，所以
|An+2|≥|An|+1>|Bn|+1≥|Bn+2|，结论成立。
（2）因为2019=2×36+2×35+2×33+2×32+1×31=（2202210）（3），S-（2019）= 2+2+2+1为奇数，所以f（2019）为偶数。
思考：对给定的正整数n，|An|-|Bn|=？希望同学们能得到一般结论。
它等价于计算有多少个a∈[1，n]，使f（a）、f（a+1）都为奇。
容易证明|A2015|-|B2015|=13。
【新写】在模2的意义下，我们有f（1）=f（2）=1，f（3n）≡f（n），
f（3n+1）≡f（n）+1，f（3n+2）≡f（n）。
将n表成三进制数：n=（akak-1…a1a0）（3），其中ak≠0，定义
S-（n）=ak-1+ak-2+…+a1+a0。其中规定，当k=0时，S-（n）=0。
引理1：对任何正整数n，f（n）≡S-（n）+1（mod2）。
证明：当n=1时，结论显然成立。设结论对小于n的正整数成立，考虑n的情形。
（i）若a0=0，则n=（akak-1…a10）（3）=3（akak-1…a1）（3），此时，
f（n）=f（3（akak-1…a1）（3））
f（（akak-1…a1）（3））
S-（（akak-1…a1）（3））+1=ak-1+ak-2+…+a1+1≡S-（n）+1（mod2），结论成立。
（ii）若a0=1，则n=（akak-1…a11）（3）=3（akak-1…a11）（3）+1，此时，
f（n）=f（3（akak-1…a1）（3）+1）
f（（akak-1…a1）（3））+1
S-（（akak-1…a1）（3））+1+1=ak-1+ak-2+…+a1+2≡S-（n）+1（mod2），结论成立。
（iii）若a0=2，则n=（akak-1…a12）（3）=3（akak-1…a1）（3）+2，此时，
f（n）=f（3（akak-1…a1）（3）+2）
f（（akak-1…a1）（3））
S-（（akak-1…a1）（3））+1=ak-1+ak-2+…+a1+1≡S-（n）+1（mod2），结论成立。
综合（i）（ii）（iii），引理1获证。
引理2：对任何正整数n，每相邻两个项f（n）、f（n+1）中至少有一个为奇数。
证明：由引理1可知，f（n）、f（n+1）中至少有一个为奇数，等价于S-（n）、S-（n+1）中至少有一个为偶数。
如果S-（n）为偶数，则结论成立。下设S-（n）为奇数。
如果a0≤1，则n与1相加没有进位，此时n+1=（akak-1…a1（a0+1））（3），所以S-（n+1）= ak-1+ak-2+…+a1+（a0+1）为偶数，结论成立。
如果a0=2，则n与1相加有进位。此时由S-（n）=ak-1+ak-2+…+a1+a0为奇数可知，ak-1，ak-2，…，a1，a0中至少有一个不为2，不妨设i是使ai≠2的最小下标（1≤i≤k-1），即n=（akak-1…ai22…2）（3）（ai≠2，1≤i≤k-1），此时
n+1=（akak-1…ai（ai+1）00…0）（3）（有进位），
S-（n+1）=ak-1+ak-2+…+（ai+1）+0+…+0≡ak-1+ak-2+…+（ai+1）+2+…+2=S-（n）+1≡0（mod2），所以S-（n+1）为偶，结论成立，引理2获证。
解答原题：（1）如果n=1、2，由f（1）=f（2）=1，知结论成立。
设结论对n成立，即|An|>|Bn|，考虑n+2的情形。由引理2，|An+2|≥|An|+1，|Bn+2|≤|Bn|+1，所以|An+2|≥|An|+1>|Bn|+1≥|Bn+2|，结论成立。
（2）因为2019=2×36+2×35+2×33+2×32+1×31=（2202210）（3），S-（2019）= 2+2+2+1为奇数，所以f（2019）为偶数。
