Mathematical Induction in binary trees

[TheMathNoob]

Homework Statement

Show that every 2-tree(Definition 3.2) with n internal nodes has n+1 external nodes

Homework Equations

A 2 tree is a tree which nodes have 2 children or no children.
Internal nodes are nodes which have two children
external nodes are leafs.

The Attempt at a Solution

Proof
base case
n=1
Internal nodes=1
external nodes=2

Inductive step

Inductive hypothesis: Let k internal nodes have k+1 external nodes
so k+1 internal nodes will have (k+1)+1 external nodes.

 

[andrewkirk]

so k+1 internal nodes will have (k+1)+1 external nodes.

What is your reason for thinking that that follows?

 

[TheMathNoob]

What is your reason for thinking that that follows?

k internal nodes= k+1 external nodes. But I have been thinking and this doesn't make any sense.
1 internal node= 2 external nodes
so k+1 internal nodes= k+3 external nodes.

I know that when you add an internal node, you should eliminate one external node, but I don't know how to show that.

 

[andrewkirk]

What happens to the internal and external node counts when you take an external node and give it two child nodes?

 

[TheMathNoob]

What happens to the internal and external node counts when you take an external node and give it two child nodes?

+2 external nodes +1 internal nodes

 

[andrewkirk]

Yes there are two new external nodes, but what is the net change in the number of external nodes?.

 

[TheMathNoob]

Yes there are two new external nodes, but what is the net change in the number of external nodes?.

1?