Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Is this formula written correctly? E.g. $f_1(3)=f_0(3-2+1)+2=f_0(2)+2$, which is undefined. – Douglas S. Stones Jan 1 '13 at 1:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.