4 views

Skip to first unread message

Dec 1, 2012, 1:09:37 PM12/1/12

to cs561-f12

When you are writing out the inductive step, you want to reduce the big problem to a *smaller* problem. Some of you are doing this in the opposite (wrong) direction.

**See the bottom of page 17 of the link below for a discussion of why going from smaller to bigger is wrong for this particular proof about trees.**

For example in problem 1 of the last homework, the correct proof goes as follows:

BC: A tree with 1 node has 0 edges.

IH: A tree with j<n nodes has j-1 edges

IS: Let T be an arbitrary tree with n nodes. Note that T must have at least one leaf node. Let T' be the tree you get when you remove this leaf node and the incident edge from T. T' has n-1 nodes, so, by the IH, T' has n-2 edges. Thus, T must have (n-2) + 1 = n-1 edges.

QED

also note that this is a great document to read if you need a review of induction.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu