# 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 $\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.

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

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)

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

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.)