10 years ago, when analyzed the number of nodes in the regular tree, I have discovered an interesting formula, $$(b-1)\sum_0^{n-1} b^i = b^n - 1 \hspace {10 mm}$$
This sums 1 parent node (level n=0), b child nodes on level 1, $b^2$ nodes on the level 2 and so on. This is a geometric series and b is a constant node degree.
Result stems from the fact that (take b=10 for convince) 9 is 1 less than the base unit 10. Nine tens is ten less than the next base unit hundred. You can fill the gap between 9*10 and 100 by adding the nine units, and yet get 1 less than 100. Nine hundreds is one hundred less than one thousand. To fill the gap, you add nine tens and one ten is missing. You add 9 units and one is missing. This corresponds to any positional number system and here is illustration for b=6.
So, we need to add 1 to 9 to get 10, $9 = 10-1$. Let's add 9*10 and get a number 1 less than 100, $9 + 9*10 = 100 - 1$. Continuing, we get $9 + 90 + 900 = 1000 - 1$. We can quickly general, $$\sum_0^{n-1} {9 * 10^i} = 10^n - 1$$ or, for generalizing the base 10 -> b, $$\sum_0^{n-1} {(b-1) * b^i} = (b-1) \sum_0^{n-1} {b^i} = b^n - 1$$ So we sum levels 0 to n-1 and get number of elements. We cannot sum infinitely many levels as count explodes. See on the picture that every level, added all previous elements together is missing 1 (atom). What if we split it into b subparts and continue dividing? That is, we take (b-1) subparts of 1 of size 1/b, , add It is like we integrate moving the opposite direction -- we take parts of size b times smaller than rather than larger as we did in $(b-1) \sum{b^i}$. Now we $$(b-1) \sum_{- \infty}^{-1}{b^{i}}$$ This geometric series is decreasing and can be computed simpler, using formal power series: $ b^{-1} + b^{-2} + \ldots = \sum = b^{-1}(1 + b^{-1} + b^{-2} + \ldots) = (1 + \sum)/b$. Extracting the sum, $(b-1)\sum = 1$. It says that .99999999(9) = 1. Isn't it nice that the number of nodes below 1 adds to 1 and this one was missing when we added units, tens and hundreds? It was missing because we started our integration to n from 1. If we do it from -inf, the formula simplifies $$(b-1)\sum_{-\infty}^{n-1} b^{i} = (b-1)\sum_{-\infty}^{-1} b^{i} + (b-1)\sum_0^{n-1} b^i = 1 + b^n - 1 = b^n$$ or $$(b-1)\sum_{-\infty}^{n-1} b^{i} = b^n$$ Now, recently, I started to think about normalization factor of geometric distribution. The probabilities fade as geometric series, every next probability is b times less. Thereby, they sum to 1. Guess what is k in $k \sum{b^{-i}} = 1$? Yes, we know already that it is (b-1)! It is the same factor that makes 999 one less than 1000.
update
I have realized that not only $$1 + x + x^2 + \cdots = \sum_0 x^n = 1 / (1-x)$$ but also $$x^{-1} + x^{-2} + x^{-3} + \cdots = \sum_{-1}^{-\infty} x^n = -1 / (1-x)$$ so that $$\cdots + x^{-2} + x^{-1} + 1 + x + x^2 + \cdots = \sum_{-\infty}^{+\infty} x^n = -1/(1-x) + 1/(1-x) = 0$$
So, we need to add 1 to 9 to get 10, $9 = 10-1$. Let's add 9*10 and get a number 1 less than 100, $9 + 9*10 = 100 - 1$. Continuing, we get $9 + 90 + 900 = 1000 - 1$. We can quickly general, $$\sum_0^{n-1} {9 * 10^i} = 10^n - 1$$ or, for generalizing the base 10 -> b, $$\sum_0^{n-1} {(b-1) * b^i} = (b-1) \sum_0^{n-1} {b^i} = b^n - 1$$ So we sum levels 0 to n-1 and get number of elements. We cannot sum infinitely many levels as count explodes. See on the picture that every level, added all previous elements together is missing 1 (atom). What if we split it into b subparts and continue dividing? That is, we take (b-1) subparts of 1 of size 1/b, , add It is like we integrate moving the opposite direction -- we take parts of size b times smaller than rather than larger as we did in $(b-1) \sum{b^i}$. Now we $$(b-1) \sum_{- \infty}^{-1}{b^{i}}$$ This geometric series is decreasing and can be computed simpler, using formal power series: $ b^{-1} + b^{-2} + \ldots = \sum = b^{-1}(1 + b^{-1} + b^{-2} + \ldots) = (1 + \sum)/b$. Extracting the sum, $(b-1)\sum = 1$. It says that .99999999(9) = 1. Isn't it nice that the number of nodes below 1 adds to 1 and this one was missing when we added units, tens and hundreds? It was missing because we started our integration to n from 1. If we do it from -inf, the formula simplifies $$(b-1)\sum_{-\infty}^{n-1} b^{i} = (b-1)\sum_{-\infty}^{-1} b^{i} + (b-1)\sum_0^{n-1} b^i = 1 + b^n - 1 = b^n$$ or $$(b-1)\sum_{-\infty}^{n-1} b^{i} = b^n$$ Now, recently, I started to think about normalization factor of geometric distribution. The probabilities fade as geometric series, every next probability is b times less. Thereby, they sum to 1. Guess what is k in $k \sum{b^{-i}} = 1$? Yes, we know already that it is (b-1)! It is the same factor that makes 999 one less than 1000.
update
I have realized that not only $$1 + x + x^2 + \cdots = \sum_0 x^n = 1 / (1-x)$$ but also $$x^{-1} + x^{-2} + x^{-3} + \cdots = \sum_{-1}^{-\infty} x^n = -1 / (1-x)$$ so that $$\cdots + x^{-2} + x^{-1} + 1 + x + x^2 + \cdots = \sum_{-\infty}^{+\infty} x^n = -1/(1-x) + 1/(1-x) = 0$$
No comments:
Post a Comment