Graph Theory help with proofs

[Sorthon]

So im in graph theory at my college and i have never done a single proof in my life. Normally the teacher gives us an option of either a proof or a program sense this class is also required for math majors. This time around however he decided to give every one one proof and one program and as far as the proof goes i am 100% lost.

The question goes as follows:

Corollary 3.2.24: Every binary tree of height h has at most 2^(k+1)-1 vertices.

Prove corollary 3.2.24 directly with the "strong form" of induction using its weaker induction: For some h>0 and all k<=h-1, a binary tree of height k has at most 2^(k+1)-1 vertices.

I'm not looking for a direct answer but any help to point me in the right direction would be much appreciated.

 

I know that a binary tree with 2 vertices will have a hieght of 1, then plugging in 1 into 2^(1+1)-1 which will = 3 stating that a tree with height 1 will have at most three vertices sense a vertex may only have two children in a binary tree. The tree will look like this:

 

0

/ \

0 0

The height of this tree is still only one and the largest amount of possible vertices with out increasing the height is 3.

Edited February 26, 2013 by Sorthon