Results 1 to 4 of 4

Math Help - Induction for binary tree.

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    45

    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.
    Last edited by bfpri; March 29th 2010 at 09:23 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    Quote Originally Posted by emakarov View Post
    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..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. binary tree math proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 14th 2012, 03:24 AM
  2. Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2011, 07:40 PM
  3. asimptotic value of height of binary tree
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 20th 2011, 12:08 PM
  4. [SOLVED] Full Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 12th 2010, 05:22 PM
  5. [SOLVED] Binary tree - number of leafs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 3rd 2008, 08:11 AM

Search Tags


/mathhelpforum @mathhelpforum