title: Proof by induction on binary trees
body: <p>Right now I'm currently working on a problem in my algorithm design textbook, and I've hit a bit of a brick wall.</p>
  
  <p>The problem is:</p>
  
  <blockquote>
    <p>A binary tree is a rooted tree in which each node has at most two
    children. Show by induction that in any binary tree that the number of
    nodes with two children is exactly one less than the number of leaves.</p>
  </blockquote>
  
  <p>I'm reasonably certain of how to do this: the base case has a single node, which means that the tree has one leaf and zero nodes with two children. However, I'm not quite certain exactly what the inductive step would entail.</p>