Math Solving the recurrence relation for number of nodes in an AVL tree?

Math Solving the recurrence relation for number of nodes in an AVL tree?,math,data-structures,discrete-mathematics,avl-tree,recurrence,Math,Data Structures,Discrete Mathematics,Avl Tree,Recurrence,Suppose that we have this recurrence relation, which comes up in the analysis of AVL trees: F1 = 1 F2 = 2 Fn = Fn - 1 + Fn - 2 + 1 (where n ≥ 3) How would you solve this recurrence to get a closed-form for F(n)? This number is used to get the mininum number of internal nodes in an AVL tree with height n.

Suppose that we have this recurrence relation, which comes up in the analysis of AVL trees:

  • F1 = 1
  • F2 = 2
  • Fn = Fn - 1 + Fn - 2 + 1 (where n ≥ 3)

How would you solve this recurrence to get a closed-form for F(n)? This number is used to get the mininum number of internal nodes in an AVL tree with height n.


#1

There are many ways that you can solve this recurrence, but most of them are pretty involved. I think the easiest way to do this would be to expand out a few terms of the series and see what you find:

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

If you take a look at this, you'll note that the following holds:

  • 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

It looks like these terms are just terms from the Fibonacci series with 1 subtracted from them. In particular, note that F3 = 2, F4 = 3, F5 = 5, etc. Therefore, it looks like the pattern is

  • F(1) = 2 - 1 = F3 - 1
  • F(2) = 3 - 1 = F4 - 1
  • F(3) = 5 - 1 = F5 - 1
  • F(4) = 8 - 1 = F6 - 1
  • F(5) = 13 - 1 = F7 - 1
  • F(6) = 21 - 1 = F8 - 1

So, more generally, it looks like the pattern is F(n) = Fn + 2 - 1. We could try to formalize this using mathematical induction:

Base cases:

  • F(1) = 1 = 2 - 1 = F3 - 1
  • F(2) = 2 = 3 - 1 = F4 - 1

Inductive step: Assume F(n) = Fn+2 - 1 and F(n + 1) = Fn+3 - 1. Then we have that

  • F(n + 2) = F(n) + F(n + 1) + 1 = Fn+2 - 1 + Fn+3 - 1 + 1 = (Fn+2 + Fn+3) - (1 + 1) + 1 = Fn+4 - 1 = F(n + 2) + 2 - 1

Et voila! The induction checks out.

So how did I think to look for that pattern with the Fibonacci series? Well... the recursive definition kinda looked like the one for the Fibonacci series, so I expected there was probably some kind of connection between the two of them. Making the observation that everything was a Fibonacci number minus one was just creative insight. You could potentially try to solve this by using generating functions or other combinatorial tricks, though I'm not much of an expert on them.

Hope this helps!


#2

Possible duplicate of stackoverflow.com/questions/279619

#3

@phs- I don't think this is a duplicate. This question asks for how you solve the central recurrence that shows AVL trees have low height. The linked question asks for methods for generating terms in the Fibonacci sequence.

#4

This totally helps,Thx.I focus on the induction of Fibonacci number itself,but don't think about there may be some connection between these two.When i copy the solution of Fibonacci number,I have an egg on my face,so stupid.aha