math - 解决 AVL 树中节点数的递归关系？

Question

假设我们有这个递归关系，它出现在 AVL 树的分析中：

• F ₁ = 1
• F ₂ = 2
• F _n = F _{n - 1} + F _{n - 2} + 1（其中 n ≥ 3）

你将如何解决这种递归以获得 F(n) 的封闭形式？此数字用于获取高度为 n的AVL 树中的内部节点的最小数量。

Answer 1

有很多方法可以解决这种重复，但其中大多数都非常复杂。我认为最简单的方法是扩展该系列的一些术语，看看你会发现什么：

• F(1) = 1
• F(2) = 2
• F(3) = 4
• F(4) = 7
• F(5) = 12
• F(6) = 20

如果你看一下这个，你会注意到以下内容：

• F(1) = 1 = 2 - 1
• F(2) = 2 = 3 - 1
• F(3) = 4 = 5 - 1
• F(4) = 7 = 8 - 1
• F(5) = 12 = 13 - 1
• F(6) = 20 = 21 - 1

看起来这些术语只是斐波那契数列中减去 1 的术语。特别要注意 F ₃ = 2、F ₄ = 3、F ₅ = 5 等。因此，模式看起来是

• F(1) = 2 - 1 = F ₃ - 1
• F(2) = 3 - 1 = F ₄ - 1
• F(3) = 5 - 1 = F ₅ - 1
• F(4) = 8 - 1 = F ₆ - 1
• F(5) = 13 - 1 = F ₇ - 1
• F(6) = 21 - 1 = F ₈ - 1

因此，更一般地说，模式看起来是 F(n) = F _{n + 2} - 1。我们可以尝试使用数学归纳法将其形式化：

基本情况：

• F(1) = 1 = 2 - 1 = F ₃ - 1
• F(2) = 2 = 3 - 1 = F ₄ - 1

归纳步骤：假设 F(n) = F _n+2 - 1 和 F(n + 1) = F _n+3 - 1。那么我们有

• F(n + 2) = F(n) + F(n + 1) + 1 = F _n+2 - 1 + F _n+3 - 1 + 1 = (F _n+2 + F _n+3 ) - ( 1 + 1) + 1 = F _n+4 - 1 = F _{(n + 2) + 2} - 1

瞧！感应检查。

那么我是如何想用斐波那契数列寻找这种模式的呢？嗯……递归定义有点像斐波那契数列的定义，所以我预计它们两者之间可能存在某种联系。观察一切都是斐波那契数减一只是创造性的洞察力。您可能会尝试通过使用生成函数或其他组合技巧来解决这个问题，尽管我对它们不是很熟悉。

希望这可以帮助！