Data Structures, Algorithms, & Applications in C++
Chapter 15, Exercise 9
In the induction base we show Nh =
Fh+2 - 1 for h = 0 and 1.
When h = 0, the left side is
N0 = 0 and the right side is
F2 - 1 = 1 - 1 = 0.
When h = 1, the left side is
N1 = 1 and the right side is
F3 - 1 = 2 - 1 = 1.
For the induction hypothesis, assume that
Nh =
Fh+2 - 1 for h < m
where m is an arbitrary integer > 1.
In the induction step, we must show that
Nh =
Fh+2 - 1 for h = m.
The left side is
Nm =
Nm-1 +
Nm-2 + 1.
From the induction hypothesis, we obtain
Nm-1 = Fm+1 - 1 and
Nm-2 = Fm - 1. Therefore,
Nm =
Fm+1 - 1 +
Fm - 1 + 1 = Fm+2 + 1.