Lesson 9

Problem. Let \(L(n)\) be the number of leaves in a complete ternary tree of height \(n\) (where each vertex, except the leaves, has exactly three children). For example, \(L(3)=9\).

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