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

Question

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 F₃ = 2, F₄ = 3, F₅ = 5, etc. Therefore, it looks like the pattern is

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

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

Base cases:

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

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

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

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!