TADM2E 1.17

From Algorithm Wiki
Revision as of 18:22, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Step 1: Show that the statement holds for the basis case $ n = 1 $

$ E(n) = n - 1 $
$ E(1) = 1 - 1 = 0 $. 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.

$ E\left(n + 1\right) = n + 1 - 1 $
$ \Leftrightarrow E(n) + 1 = n $ When adding one node to a tree one edge is added as well
$ \Leftrightarrow n -1 + 1 = n $
$ \Leftrightarrow n = n $

QED