# Thread: How can calculate formula for nodes in Fat-Tree?

1. ## How can calculate formula for nodes in Fat-Tree?

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

2. ## Re: How can calculate formula for nodes in Fat-Tree?

I would use induction to prove that given n nodes at h=0 (the top level), that P: "the number of nodes $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 $S = n + \sum\limits_{h=1}^h 2n$ for P(h).
Then you would use the inductive step to show $S = n + \sum\limits_{h=1}^{h+1} 2n$ for P(h+1).

Let me know if you have further questions.

3. ## Re: How can calculate formula for nodes in Fat-Tree?

I made a mistake.
P: "The number of nodes in the graph is $\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)

4. ## Re: How can calculate formula for nodes in Fat-Tree?

Originally Posted by MacstersUndead
I made a mistake.
P: "The number of nodes in the graph is $\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)
Thank you,
But I did not understand. I think we used Geometric progression for calculate this.

5. ## Re: How can calculate formula for nodes in Fat-Tree?

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.