给我几个树的归纳证明题

在递归算法和数据结构的教学中，归纳证明经常用于阐述树的相关性质。这里列举几个关于树的归纳证明题目：

1. **二叉树的节点数**: 已知一个满二叉树（每个层级都完全填充，最底层左侧开始放置节点）有 n 层，证明其节点总数可以用公式 `2^(n+1) - 1` 表示。

归纳证明步骤：
- 基础情况 (n=0): 一个空树（只有一个根节点）有1个节点，公式成立。
- 归纳假设: 对于任意一层 k，满二叉树有 `2^k - 1` 节点。
- 归纳步: 当增加一层时，新的层数变成 k+1，会新增两倍之前层的节点数再加上1（因为新添加的顶部有一条分支），即 `2 * (2^k - 1) + 1 = 2^(k+1) - 1`。

2. **汉诺塔问题**: 有三根柱子 A、B 和 C，汉诺塔游戏中每次只能移动一根盘子，并且大盘子不能放在小盘子上面，问将 n 个盘子从 A 移动到 C 需要多少步？

归纳证明：
- 基础情况 (n=1): 只有一个盘子，一步即可完成。
- 归纳假设: 将 n-1 个盘子从 A 移到 B，需要 `2^n - 2` 步（通过归纳得到）。
- 归纳步: 加上最后一步把最大的盘子从 B 移到 C，总共需要 `2^n - 2 + 1 = 2^n - 1` 步。

3. **斐波那契数列**: 第 n 项 F(n) 的计算可以用 F(n-1) + F(n-2)，初始两项为 F(0)=0, F(1)=1，求解第 n 项的递推公式。

归纳证明：
- 基础情况 (n=0,1): 显然 F(0)=0, F(1)=1 符合条件。
- 归纳假设: 假设 F(k) 和 F(k-1) 成立，那么 F(k+1) = F(k) + F(k-1)。
- 归纳步: 根据上述假设，F(n) 完全满足斐波那契数列的定义，所以归纳成立。