Difference between revisions of "TADM2E 1.17"
From Algorithm Wiki
(Recovering wiki) 
(No difference)

Revision as of 18:13, 11 September 2014
<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 zero edges
<b>Step 2:</b> Assume that that summation is true up to n.<br><br> <b>Step 3:</b> Show that on the assumption that the summation is true for n, it follows that it is true for n + 1.
 <math>E\left(n + 1\right) = n + 1  1</math><br>
 <math>\Leftrightarrow E(n) + 1 = n</math> When adding one node to a tree one edge is added as well<br>
 <math>\Leftrightarrow n 1 + 1 = n</math><br>
 <math>\Leftrightarrow n = n</math><br>
QED