Recurrence Relations · Recursive Definitions

Lesson 10

Nikolai Chukhin · Alexander S. Kulikov

Problem. Let \(V(n)\) be the number of vertices in a complete binary tree of height \(n\). For example, \(V(4)=15\).

It is easy to see that \(V(n)\) satisfies the following recurrence relation: \[V(0)=0, \quad V(n)=2V(n-1)+1.\] Find an explicit formula for \(V(n)\).

5 points