Recurrence Relations · Recursive Definitions

Lesson 11

Nikolai Chukhin · Alexander S. Kulikov

Again, you can guess the solution by listing the first few terms of the sequence:

It can be observed that the numbers resemble powers of two minus one, leading to the guess \(V(n)=2^{n}-1\), which can then be proved by induction.

Considering the tree structure, note that each subsequent level of vertices has twice as many vertices as the previous level. Hence, the total number of vertices in the tree will be \[1+2+4+8+16+\dotsb+2^{n-1}.\] This sum equals \(2^{n}-1\). This equality can be proved using mathematical induction or by using a formula for geometric series: \[1+c+c^{2}+c^{3}+\dotsb+c^{n}=\frac{c^{n+1}-1}{c-1}\] (the formula holds for \(c \neq 1\); for \(c=1\), the left-hand side equals \(n+1\)).