# 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?