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.

  • 2
    $\begingroup$ Is this formula written correctly? E.g. $f_1(3)=f_0(3-2+1)+2=f_0(2)+2$, which is undefined. $\endgroup$ – Douglas S. Stones Jan 1 '13 at 1:27
  • $\begingroup$ What led you to the recurrence relations? $\endgroup$ – mdave16 May 26 '17 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.