Math Is Fun Forum

White_Owl

Member

Registered: 2010-03-03

Posts: 106

Number of nodes in binary tree

Problem:
Show that maximum number of nodes in a binary tree of height

is

My Answer:
In a binary tree each node has two children; therefore, number of nodes on each level is twice the number of nodes on the previous level. In a recursive form number of nodes on level

is:

. Or in a closed form:

, for

.
Therefore total number of nodes in a full binary tree is:

Using induction we can prove that

Basic step for

:

and

Inductive step: Assuming

is true, then

should also be true:

by inductive hypotheses

, so

Therefore:

And now my questions:
a) I think it is obvious that

  in closed form would be

. But to be completely thorough how to convert recursive form into closed one? (Link to a book chapter would be fine.) And do I need to do it in the first place?

b) I have a strong suspicion that it is possible to solve the original problem without resorting to induction and I went a little overboard with it. If yes, please point me into the right direction on how to solve this problem easier?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Number of nodes in binary tree

Hi White_Owl;

Is a recurrence formula and like their continuous counterparts ( differential equations ) many of them can be solved by algebraic methods of generating functions. Start with any Discrete mathematics book. Most will cover that.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.