Thread: Induction for binary tree.

The proposition 6.9 states that: t is a proper binary tree with n nodes and h is the height.

The number of external nodes in T is at least h+1 and at most 2^h. or h>=h+1 and h<=2^h. I let e be the number of external nodes. I must prove this statement by induction. So i let P(h) be that statement. So obviously P(1) is true because that is 2 external nodes =h+1 and 2^h. I try solving for P(h+1) for the lower bound. so we assume that e>=(h+1)+1=h+1>=h+2 is true. so adding +1 to both sides of e>=h+1 i get e+1>=h+2. That can't be right.. I guess i'm confused about how to set this up.

t is a proper binary tree with n nodes and h is the height... The number of external nodes in T is at least h+1 and at most 2^h. or h>=h+1 and h<=2^h.

Can't you see that you confused n and h? Just to remark, "external nodes" are also (in my experience, more often) called "leaves".

So i let P(h) be that statement.

When people have difficulties with induction, I think it is extremely important to write P(h) explicitly and to make sure that it is a proposition, not a number. This may not be the issue here, but it makes everything else easier.

Originally Posted by emakarov

Can't you see that you confused n and h? Just to remark, "external nodes" are also (in my experience, more often) called "leaves".

Yeah sorry, the h should be e.

When people have difficulties with induction, I think it is extremely important to write P(h) explicitly and to make sure that it is a proposition, not a number. This may not be the issue here, but it makes everything else easier.

i guess the problem I have is finding a way to connect the number of external nodes to the height in an equality. I can't n because that the number of nodes, not external nodes. So i just pick some random variable e. The problem is that I'm trying to prove that the statement above is true for h+1 as well. However i can't find a way to connect the relation. e>=h+1, so if i sub h+1 in i get e>=h+2 which i assume to be true..The problem is that there are 2 variables..

Look, if I communicated with my adviser by e-mail, and he would say something I don't immediately get, I would make an extra effort to try to understand, even if the misunderstanding happens because he expressed himself somewhat sloppily. I don't want to annoy him by unnecessary questions provided what he said is in fact understandable.

However, when somebody is having a difficulty with math, I don't see the benefit in maintaining a sloppy conversation. What is the reason for us to be careless if it makes it more difficult for me to understand and for you to find the problem?

Here are some remarks.

I can't n because that the number of nodes, not external nodes

What about the number of nodes and not external nodes?

So i just pick some random variable e.

I thought that e is the number of leaves, not a random variable.

The problem is that I'm trying to prove that the statement above

What statement above? I suggested writing it explicitly: P(h) = ... or P(n) = ...

e>=h+1, so if i sub h+1 in i get e>=h+2 which i assume to be true

Write clearly the induction statement, the induction hypothesis and the claim to prove.

Again, it's nothing personal. It is possible that by thinking harder I would be able to guess the precise reason for your problem. But making yourself more precise won't create more problems; it may only help both you to solve the question and me to understand you.