1.19

From The Algorithm Design Manual Solution Wiki
Revision as of 12:20, 1 September 2020 by Algowikiadmin (talk | contribs) (Created page with "<b>Step 1:</b> Show that the statement holds for the basis case <math>n = 1</math><br> :<math>E(n) = n - 1</math><br> :<math>E(1) = 1 - 1 = 0</math>. A tree with one node has...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Step 1: Show that the statement holds for the basis case [math]\displaystyle{ n = 1 }[/math]

[math]\displaystyle{ E(n) = n - 1 }[/math]
[math]\displaystyle{ E(1) = 1 - 1 = 0 }[/math]. 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.

[math]\displaystyle{ E\left(n + 1\right) = n + 1 - 1 }[/math]
[math]\displaystyle{ \Leftrightarrow E(n) + 1 = n }[/math] When adding one node to a tree one edge is added as well
[math]\displaystyle{ \Leftrightarrow n -1 + 1 = n }[/math]
[math]\displaystyle{ \Leftrightarrow n = n }[/math]

QED


Back to Chapter 1.