# Closed form expression for a recurrence relation.

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.

-
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