Hello, any ideas for computing closed form for a recurrence relation?
In an attempt to compute what the $i$-th post order element would be in terms of its in order position in a complete binary tree, I could arrive at following recurrence relation:
For each $k$, $f_k \in S_{2^{k+1} - 1} $ i.e. it is a permutation on ${1,...,2^{k+1} -1 } $
\begin{cases} f_{k} (i) = f_{k-1} (i - 2^k + 1) + 2^k, & \text{if}\; i > 2^k\\ f_{k} (i) = f_{k-1} (i), &\text{if}\; i < 2^k\\ f_{k} (i) = 2^k + 1, &\text{if}\; i = 2^k \end{cases}
With this recurrence we can get the value of $ f_{k} (i) $ in $ O(\log i) $ steps, but a closed form expression would be of great help.