Recurrence Relations · Recursive Definitions

Lesson 9

Nikolai Chukhin · Alexander S. Kulikov

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)\).

5 points