问题

某人上一共有 $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.
\]

试证明之.