10 years ago, when analyzed the number of nodes in the regular tree, I have discovered an interesting formula, (b−1)n−1∑0bi=bn−1
This sums 1 parent node (level n=0), b child nodes on level 1, b2 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, n−1∑09∗10i=10n−1 or, for generalizing the base 10 -> b, n−1∑0(b−1)∗bi=(b−1)n−1∑0bi=bn−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)∑bi. Now we (b−1)−1∑−∞bi This geometric series is decreasing and can be computed simpler, using formal power series: b−1+b−2+…=∑=b−1(1+b−1+b−2+…)=(1+∑)/b. Extracting the sum, (b−1)∑=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)n−1∑−∞bi=(b−1)−1∑−∞bi+(b−1)n−1∑0bi=1+bn−1=bn or (b−1)n−1∑−∞bi=bn 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∑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+x2+⋯=∑0xn=1/(1−x) but also x−1+x−2+x−3+⋯=−∞∑−1xn=−1/(1−x) so that ⋯+x−2+x−1+1+x+x2+⋯=+∞∑−∞xn=−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, n−1∑09∗10i=10n−1 or, for generalizing the base 10 -> b, n−1∑0(b−1)∗bi=(b−1)n−1∑0bi=bn−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)∑bi. Now we (b−1)−1∑−∞bi This geometric series is decreasing and can be computed simpler, using formal power series: b−1+b−2+…=∑=b−1(1+b−1+b−2+…)=(1+∑)/b. Extracting the sum, (b−1)∑=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)n−1∑−∞bi=(b−1)−1∑−∞bi+(b−1)n−1∑0bi=1+bn−1=bn or (b−1)n−1∑−∞bi=bn 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∑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+x2+⋯=∑0xn=1/(1−x) but also x−1+x−2+x−3+⋯=−∞∑−1xn=−1/(1−x) so that ⋯+x−2+x−1+1+x+x2+⋯=+∞∑−∞xn=−1/(1−x)+1/(1−x)=0
No comments:
Post a Comment