[Ex.6.6-6]
某人上一共有 $n$ 级台阶的楼梯. 如果规定他每步只能上一级台阶或三级台阶, 问有多少种不同的上楼梯方法?
记号:
$f(n)$ 指对于 $n$ 级台阶上楼梯的方案总数.
[分析]
当 $n=6$ 时, 上楼梯的方案有 $f(6)=6$ 种:
- 1,1,1,1,1,1
- 1,1,1,3
- 1,1,3,1
- 1,3,1,1
- 3,1,1,1
- 3,3
当 $n=5$ 时, 上楼梯的方案有以下 $f(5)=4$ 种:
- 1,1,1,1,1
- 1,1,3
- 1,3,1
- 3,1,1
当 $n=4$ 时, 上楼梯的方案有以下 $f(4)=3$ 种:
- 1,1,1,1
- 1,3
- 3,1
当 $n=3$ 时, 上楼梯的方案有以下 $f(3)=2$ 种:
- 1,1,1
- 3
因此, 一种办法是可以按有几个3来分类.
例如: 当 $n=7$ 时, $n\equiv 1\pmod 3$, 此时 $[\frac{n}{3}]=[\frac{7}{3}]=2$.
- 0个3, 有 1 种. ($11\ldots1$)
- 1个3, 有 $C_5^1$ 种. (31111, 13111, 11311, 11131, 11113)
- 2个3, 有 $C_3^1$ 种. (331, 313, 133)
故 $f(7)=1+C_5^1+C_3^1=9$.
当 $n=8$ 时, $n\equiv 2\pmod 3$, 此时 $[\frac{n}{3}]=[\frac{8}{3}]=2$.
- 0个3, 有 1 种. ($11\ldots1$)
- 1个3, 有 $C_6^1$ 种.
- 2个3, 有 $C_3^1+C_3^2$ 种. (将 33 放到 []1[]1[] 中, 分两种情形, 33 不分离, 33 分离)
故 $f(8)=1+C_6^1+(C_3^1+C_3^2)=13$.
当 $n=9$ 时, $n\equiv 0\pmod 3$, 此时 $[\frac{n}{3}]=[\frac{9}{3}]=3$.
- 0个3, 有 1 种. ($11\ldots1$)
- 1个3, 有 $C_7^1$ 种.
- 2个3, 有 $C_4^1+C_4^2$ 种. (将 33 放到 []1[]1[]1[] 中, 分两种情形, 33 不分离, 33 分离)
- 3个3, 有 1 种.
故 $f(9)=1+C_7^1+(C_4^1+C_4^2)+1=19$.
当 $n=10$ 时, $n\equiv 1\pmod 3$, 此时 $[\frac{n}{3}]=[\frac{10}{3}]=3$.
- 0个3, 有 1 种. ($11\ldots1$)
- 1个3, 有 $C_8^1$ 种.
- 2个3, 有 $C_5^1+C_5^2$ 种. (将 33 放到 []1[]1[]1[]1[] 中, 分两种情形, 33 不分离, 33 分离)
- 3个3, 有 $C_4^1$ 种.
故 $f(10)=1+C_8^1+(C_5^1+C_5^2)+1=28$.
一般的, 记 $[\frac{n}{3}]=k$, $n\equiv r\pmod 3$. 于是,
- 0个3, 有 1 种. ($11\ldots1$, $n$ 个 1.)
- 1个3, 有 $C_{n-2}^1$ 种.
- 2个3, 有 $C_{n-6+1}^1+C_{n-6+1}^2$ 种. (将 33 放到 []1[]1[]...[]1[] 中, 分两种情形, 33 不分离, 33 分离)
- $j$个3, 则剩余 $n-3j$ 个 1. 但是这种分析会比较复杂. 还要分 $j$ 是奇数和偶数的情形.
因此, 可以从另一个角度来考虑这个问题. 比如, 能否写出递推关系?
通过上面的计算, 我们得到前若干个 $f(n)$:
\[
1,1,2,3,4,6,9,13,19,28,\ldots
\]
因此, 猜测有
\[
f(n)=f(n-1)+f(n-3),\quad n\geqslant 4.
\]
试证明之.