1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction proof

  1. Apr 5, 2016 #1
    1. The problem statement, all variables and given/known data
    In a binary tree all nodes are either internal or they are leaves. In our definition, internal nodes always have two children and leaves have zero children. Prove that for such trees, the number of leaves is always one more than the number of internal nodes.

    2. Relevant equations


    3. The attempt at a solution
    Proof by induction

    Base case:
    n=1
    Number of leafs=1
    External nodes=0

    Induction step: Assume a binary tree has k internal nodes and k+1 leaves. Therefore we have to show that a binary tree with k+1 internal nodes will have (k+1)+1 leaves

    If we want to increase the number of external nodes by 1 in this binary tree, we would have to make a leaf an internal node and we do this by sticking two new leaves to an old leaf. Doing this the net change in leaves is 1 because we eliminate 1 and add 2 new. So the number of external nodes is k+1 and the number of leaves is (k+1)+1. Consequently, by induction, the number of leaves is always one more than the number of internal nodes in a binary tree.

    Is that correct?
     
  2. jcsd
  3. Apr 6, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That's certainly the idea of the induction proof. But that's too informal a way to write it, unless you have a very easygoing lecturer. A more formal approach would be as follows:

    Start with a proposition P(n) which states that all binary trees with n leaves have n-1 internal nodes.
    The base case is P(1), which is trivial, and you have covered that above.
    For the induction step, you need to prove that, if P(n) is true for all n in 1,....,m, then P(m+1) is also true.

    This involves a similar approach to what you have above, except that you need to work backwards from a tree with m+1 leaves to one with m leaves, rather than forwards as you did above.

    If you can prove that induction step then, by the principle of induction, it is proven that P(n) is true for all natural numbers n.

    See how you go.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Induction proof
  1. Induction Proof (Replies: 6)

Loading...