Results 1 to 1 of 1

Thread: binary tree math proof

  1. January 14th 2012, 03:24 AM #1
    transgalactic
    transgalactic is offline
    MHF Contributor
    Joined
    Nov 2008
    Posts
    1,401

    binary tree math proof

    a binary tree has leaves l1,l2,..lm
    and for each leaf their depth is d1,d2,..dm

    prove that
    \sum ^m_{i=1} 2^{-d_i}\leq1
    ?
    i dont know how to prove it

    i know that the height of a binary tree is lgn
    and that the number of nodes on a certain level is less then 2^n-1
    (the algebric series sum sum)
    Last edited by transgalactic; January 14th 2012 at 11:34 AM.
    Follow Math Help Forum on Facebook and Google+
« Finding the (countable) union of these events | Permutations »

Similar Math Help Forum Discussions

  1. Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2011, 07:40 PM
  2. asimptotic value of height of binary tree
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 20th 2011, 12:08 PM
  3. [SOLVED] Full Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 12th 2010, 05:22 PM
  4. Induction for binary tree.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 30th 2010, 11:17 AM
  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