Recurrence Relations · Recursive Definitions

Lesson 6

Nikolai Chukhin · Alexander S. Kulikov

Problem. Let \(L(n)\) be the number of leaves in a complete binary tree of height \(n\). For example, \(L(4)=8\).

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

5 points