# Tree problem 1

Before looking at the solution, check some basic aspects of your outline.

### Start of proof

Did you declare the induction variable? That is, give it a name and explain how it measures the size of a tree. Height (e.g. named h) is traditional and easy to understand. Number of nodes can also work ok.

Trying to use rank as the induction variable is not a stupid idea. There might be other problems where it could work nicely. However, it's not going to work well for this proof because a tree can have a child subtree of the same rank.

If you tried to use level as the induction variable, you're probably structuring the proof wrong. See comments below about the inductive step. Or, perhaps, you've confused the word "level" with the word "height."

Check that you're using the correct definition of height. A single-node tree has height 0 (not height 1).

### Base case

Did you do all of the following?

• Identify the base case value(s) of h.
• Describe or draw all the trees of those heights.
• Check that the claim is true for these trees.

The base case for a tree induction is sometimes just a single tree (esp. for h=0). Sometimes you need to consider a small set of trees. If you are considering so many possible trees that you're having trouble writing them all out, stop writing and consider whether you could have used a lower value for the height.

### Inductive hypothesis

Did you identify the range of values for which the claim is supposed to be true? The range should go from the first base case value up through k-1.

### Rest of inductive step

Start by picking a tree of height k. Always start with the big object and divide it up.

Did you divide your big tree AT THE ROOT? If you removed a leaf or a layer of leaves from the bottom of the tree, rewrite your inductive step so you divide the tree at the root.

### Stuck finishing the inductive step?

Tree induction proofs typically break into cases in the inductive step. The definition of rank will give you some hints about the structure of the cases.

Have you used your inductive hypothesis?