小白吃樱桃

这是早年间的自主招生试题了：

小白吃$n$个樱桃，每两天至少吃一个，问有多少种吃法？

以下四种作法均属于凌落蓝：

解法1

不妨设小白吃樱桃期间，其中有$i(i=1,2,3,\cdots,n$天真正吃到了樱桃，即把$n$个樱桃分为$i$堆．

用插空法，有$\mathrm C_{n-1}^{i-1}$种方案．

下面考虑把没有吃到樱桃的那些天加进去，可以设想在这$i$堆樱桃每堆前面插入$0$或者不插，于是所有的选择方案共有

$$\sum_{i=1}^n2^i\mathrm C_{n-1}^{i-1}=2\sum_{i=1}^n2^{i-1}\mathrm C_{n-1}^{i-1}=2\cdot (1+2)^{n-1}=2\cdot 3^{n-1}.$$

---

解法2

设小白吃$n$个樱桃，每两天至少吃一个的方法数是$a_n$，则

小白第一天吃$x(1\leqslant x \leqslant n-1)$个樱桃对应的方法数是$a_{n-x}$；

小白第一天不吃樱桃，那么第二天必然要吃若干个樱桃，对应的方法数是

$$a_{n-1}+a_{n-2}+\cdots+a_1+1,$$

于是

$$a_n=2(a_{n-1}+a_{n-2}+\cdots+a_1+1),$$

而

$$a_{n-1}=2(a_{n-2}+\cdots+a_1+1),$$

从而

$$a_n-a_{n-1}=2a_{n-1},$$ 也即 $$a_n=3a_{n-1}.$$

又$a_1=2$，从而

$$a_n=3^{n-1}\cdot a_1=2\cdot 3^{n-1}.$$

---

解法3

设小白吃$n$个樱桃，每两天至少吃一个时，小白第一天不吃樱桃对应的方法数与小白第一天吃樱桃对应的方法数相等，设小白吃$n$个樱桃，每两条至少吃一个，且第一天必吃若干个樱桃的方法数为$a_n$，则$2a_n$为所求，且记$[a_n]$为对应的一个方案．

若小白第一天只吃一个樱桃，那么有两种情形：$1\qquad[a_{n-1}]$以及$1\qquad 0\qquad [a_{n-1}];$

若小白第一天吃一个以上的樱桃，那么对应情形为$[a_{n-1}]$的首项加$1$，对应方法数为$a_{n-1}$；

综上，$a_n=3a_{n-1}$，而$a_1=1$，所以$a_n=3^{n-1}a_1=a^{n-1}$．

故$2a_n=2\cdot 3^{n-1}$为所求．

---

解法4

设小白吃$n$个樱桃，每两天至少吃一个的方法数是$a_n$，且记$[a_n]$为对应的一个方案，则从$n$个樱桃的情形到$n+1$个樱桃的情形可以为$[a_n],1$；$[a_n],0,1$以及$[a_n]$的末项加$1$，故$a_{n+1}=3a_n$．又$a_1=2$，所以$a_n=2\cdot 3^{n-1}$．

---

注    文解法4详细证明了从$n$个樱桃的情形到$n+1$个樱桃的情形．