Data Structures, Algorithms, & Applications in C++
Chapter 11, Exercise 7
Property 11.4 can be proved by induction on i.
For the induction base, use i = 1.
Since i = 1 is the root; it has no left child
if 2i > n,
otherwise its left child is
at 2i = 2; it has no right child
if 2i+1 > n,
otherwise its right child is
at 2i+1 = 3.
For the induction hypothesis assume Property 11.4 is true for
i < m where
m is an arbitrary integer > 1.
In the induction hypothesis we must show that Property 11.4 is true for
the next value of i, that is
i = m <= n.
If
m is even, then from the induction base
and Property 11.4.2, it follows that the left child of node
m/2 is at
m. So the parent of
m is at
m/2. A similar argument applies when
m is odd. So Property 11.4.1 is true when
i =
m.
From Property 11.4.2 and the induction hypothesis it follows that the
left child of node
m-1 is at
2(m-1) unless
2(m-1) > n.
If m-1 has no right child, then node
m has no left child, and since
2(m-1)+1 > n,
2m > n. If
m-1 has a right child, it is at
2(m-1)+1 =
2m-1. After the right child of
m-1 is numbered, the left child of
m, if it exists, gets numbered. So its
number is
2m.
So Property 11.4.2 is true when
i =
m.
The proof for Property 11.4.3 is similar.