Lesson 12

Problem. Let \(V(n)\) be the number of vertices in a complete ternary tree of height \(n\). For example, \(V(3)=13\).

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