Difference between revisions of "TADM2E 1.17"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
| − | + | <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 | QED | ||
Latest revision as of 18:22, 11 September 2014
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
