Hello,
We have a fat-tree and diameter is = 2h (h is height of tree)
How can proof how many nodes exists in tree?
Thanks
I would use induction to prove that given n nodes at h=0 (the top level), that P: "the number of nodes $\displaystyle S = n + \sum\limits_{h=1}^h 2n$"
The base case would be to prove that the statement is true for P(h=1).
The inductive step would be to suppose $\displaystyle S = n + \sum\limits_{h=1}^h 2n$ for P(h).
Then you would use the inductive step to show $\displaystyle S = n + \sum\limits_{h=1}^{h+1} 2n$ for P(h+1).
Let me know if you have further questions.
I made a mistake.
P: "The number of nodes in the graph is $\displaystyle \sum\limits_{h=0}^h 2^h*n$ (ie. for each new level, the number of nodes to be added is doubled based on the number of the previous level.)
The rest of the process would be the same.
ie. Prove the base case. Suppose for P(h). Show it's then true for P(h+1)
My equation was equivalent the form of a geometric progression
https://en.wikipedia.org/wiki/Geomet...ometric_series
See this section for the closed form of geometric series. In this case, "a" would be the number of base nodes at h=0 and "n" would be the height.