Results 1 to 1 of 1

Math Help - binary tree math proof

  1. #1
    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 12:34 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2011, 08:40 PM
  2. asimptotic value of height of binary tree
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 20th 2011, 01:08 PM
  3. [SOLVED] Full Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 12th 2010, 06:22 PM
  4. Induction for binary tree.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 30th 2010, 12:17 PM
  5. [SOLVED] Binary tree - number of leafs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 3rd 2008, 09:11 AM

Search Tags


/mathhelpforum @mathhelpforum