1.19

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

Step 1: Show that the statement holds for the basis case


. A tree with one node has zero edges

Step 2: Assume that that summation is true up to n.

Step 3: Show that on the assumption that the summation is true for n, it follows that it is true for n + 1.


When adding one node to a tree one edge is added as well


QED


Back to Chapter 1.