Computing the index of the n^{th} ancestor of a node in a perfect binary tree / heap

Question

I think you can compute the index of the n^{th} ancestor of the node at index i using the formula: $\lfloor i / 2^n \rfloor$ where $n \in \mathbf{Z}^+$. Note that I am assuming that the parent node is at index 1 for this. Left child nodes have even indexes, and right child nodes have odd indexes. Nodes are number from top to bottom, left to right, with the root node being at the very top and the tree extending downwards.

I know that you can get the index of the parent via $\lfloor i / 2 \rfloor$. The only question is whether the rounding errors can potentially throw off the computation such that I need to compute the ancestor's index like: $\lfloor \cdots \lfloor \lfloor i / 2 \rfloor / 2 \rfloor \cdots / 2 \rfloor$.

My google-fu is failing me at the moment, so hoping one of you can verify one way or the other; extra points for a reference :)

EDIT: Of course, if you shift instead of divide its a moot point. However, I'm attempting to use this equation as part of a mathematical proof about how something can be modeled as a perfect binary tree; and dividing feels a little more appropriate in that context.

Answer 1

For any node $i$, its children are $2i$ and $2i+1$.

Using induction, you can prove that its $n^{th}$ level descendants are: $2^{n} \cdot i + j$ for $j \in \{0,\dotsc,2^n-1\}$.

Equivalently, you can say that any descendant $d$ has its $n^{th}$ ancestor $\lfloor d/2^n \rfloor = i$