Proofs with binary trees

Question

Now I have a binary tree which is How would I go about proving binary tree with $n$ leaves has exactly $2 n - 1$ nodes ?

Answer 1

Proceed by induction. By finiteness we can always find a node which has two leaves. Cut them off then use induction hypothesis

Edit:

For example

          o
        /   \
       o     X  <---- Cut here
           /   \
          o     o

becomes

         o
      /     \
     o       o

also a binary tree, but with 1 fewer leaves and 2 fewer nodes.

Edit 2: So now we just say $f(k) = f(k-1) +2$ which is $2(k-1) -1 + 2$ by induction giving us $2k-1$ as desired.