Theorem proof?

Favorite Answer

I'm not sure what you mean by regular induction versus mathematical induction, but I'll take a stab at it.

I learned induction by taking the problem and braking it apart into small pieces, where at least one of the smaller pieces is the same problem, but smaller. Use your hypothesis, and you when you put the pieces back together, you'll end up with your conclusion. So my proof won't involve building up the tree. It will start with the tree and take it apart and then put it back together.


Basis: Let T be a full binary tree with one vertex. Let's see what we get.

It has 0 internal vertices, so k=0. 2*0+1 = 1, and it does indeed have 1 vertex, so that matches.

0 + 1 = 1, and it does indeed have 1 terminal vertex, so the basis is established.

Hypothesis: For a full binary tree with j internal vertices, where j < k, then this smaller binary tree has 2j+1 total vertices and j+1 terminal vertices.

Induction: full binary tree T has k internal vertices. Take note that T is made up of its root node, a left hand branch and a right hand branch. Fortunately, both the left and right hand branches are also full binary trees, but how many internal vertices do they each contain.

Since T has a total of k vertices, then we take the root away, and we're left with k-1. We divide each by 2, because we have two sub-trees, and each branch contains (k-1)/2 internal vertices.

Now (k-1)/2 is definitely less than k, so we can use our hypthosis. Let's review:

TV(X) is the total vertices for full binary tree X...

TV(T) = 1 + TV(LBranch) + TV(RBranch)

Replace TV for the branches using the hypothesis...

TV(T) = 1 + (2[(k-1)/2) + 1 + (2[(k-1)/2) + 1

TV(T) = 1 + (k-1) + 1 + (k-1) + 1

TV(T) = 1 + k - 1 + 1 + k - 1 + 1

TV(T) = k + k + 1

TV(T) = 2k + 1

QED

Now for the TermVert. We just need to add the terminal vertices for both of the branches. The root vertex doesn't count, because it's not terminal.

TermVert(T) = TermVert(LBranch) + TermVert(RBranch)

Substitute the hypothesis to get...

TermVert(T) = (k-1)/2 + 1 + (k-1)/2 + 1

TermVert(T) = 2[(k-1)/2 + 1]

TermVert(T) = k-1 + 2

TermVert(T) = k+1

QED...Show more

Well, if you have to do it by induction, I would start with a 1-vertex tree. Clearly, if k=0, your criterion holds. This establishes your _basis_.

Next, I would note that the definition of a _full_ binary tree requires that each node have either 0 or 2 children. Therefore, in order for the tree to grow at all, one of the terminal vertices must gain two children. When this happens, two effects result:

1. The number of nodes increases by two.
2. The number of terminal nodes increases by two (for the two new ones) _and_ decreases by one (for the one former terminal node). Thus, the number of terminal nodes increases by a net of one.

Note that, if you increase k by 1, this increases the number of nodes by two, and the number of terminal nodes by one - the same effect. This establishes your _inductive step_.

I think a little polishing of the above would make your proof by induction. The key was noting the definition of a full binary tree, and finding the inductive step. Since the inductive step is usually something which moves some count up by a set amount, the idea of increasing the size of the table was the obvious means....Show more

I don't see why you need induction here... You have a full binary tree with k internal vertices and n terminal vertices (k+n total). Full means each internal one has 2 children (2*k children total), while terminals have no children. 2*k children are obviously distinct (it's a tree) and these should make up all the tree, except for the root. So 2*k == n+k-1, so n=k+1....Show more

i agree with certain degree
yeah
right
thank you
bye...Show more