Math Help Forum: Binary trees

This is a task from Kenneth Rosen's "Discrete Mathematics and its applications" book.

How can I use structural induction to show that l(T) (the number of leaves of T) is 1 more than i(T) (the number of internal nodes of T), where T is a full binary tree?

I am completely lost on this one,
I have that the number of leaves is: 2^h, with h being the height of the tree, and obviously 2^h - 1 being the number of internal nodes.

Total number of nodes n = 2^h + 2^h - 1

But I don't see how I should set up the basis step nor the inductive step, or should I use a recursive step?

This is a task from Kenneth Rosen's "Discrete Mathematics and its applications" book.

Mmmm, Rosen...



Structural induction on full binary trees works as follows. Suppose you have a property P of trees, i.e., for each particular tree T, P(T) is either true or false. Suppose further that you prove that P holds on a single-node tree (consisting of a single root), and for any tree as in the picture above, if and hold, then P of the whole tree holds. In this case, P holds on all full binary trees.

The first step is to come up with P. Here it is easy: P(T) is . Next, prove P for the single-node tree. For the induction step, suppose and hold, i.e.,

and . (*)

Let's call the whole tree T. Express through , and through , . Try to prove P(T) from (*).

Are you saying that the graph above is a tree?
But trees are a-cyclic.

You are right, the graph is not a tree. It's a schematic picture. The triangles represent the subtrees.

Edit: Drew the triangles in dashed lines to distinguish them from the graph edges.

Originally Posted by emakarov

Mmmm, Rosen...



Structural induction on full binary trees works as follows. Suppose you have a property P of trees, i.e., for each particular tree T, P(T) is either true or false. Suppose further that you prove that P holds on a single-node tree (consisting of a single root), and for any tree as in the picture above, if and hold, then P of the whole tree holds. In this case, P holds on all full binary trees.

The first step is to come up with P. Here it is easy: P(T) is . Next, prove P for the single-node tree. For the induction step, suppose and hold, i.e.,

and . (*)

Let's call the whole tree T. Express through , and through , . Try to prove P(T) from (*).

Basis step:

P(single node):

Inductive step:

P(T) :
P(T) : (by recursive formula of l(T) )
P(T) : (by recursive formula of i(T) )

Is this correct at all? What more do I need to complete the proof?

I think you got the idea. I'll be a bit pedantic below.

Originally Posted by posix_memalign

Basis step:

P(single node):

The left-hand side is what you need to prove. You can't conclude anything from it ( ) because you have not proved it yet. I would write: .

Inductive step:

P(T) :
P(T) : (by recursive formula of l(T) )
P(T) : (by recursive formula of i(T) )

First, the relationship between these three lines is not clear. Is it what you need to prove? Is it the induction hypothesis? Does the first line imply the second or vice versa?

Also, instead of "P(T) : ", it is better to write "P(T) is " or "P(T) means " or "P(T) iff ".

Generally, for each statement you write, it should be clear where it follows from or whether you plan to prove it. So, I would write

By induction hypothesis,

and . (1)

Also, from the picture we know that

(2)

and

. (3)

Therefore,