induction

4 views
Skip to first unread message

Jared Saia

unread,
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.

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

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.

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