I have a recursion function as follows:
$$R(0) = 1$$
$$R(1) = 1$$
$$R(2) = 2$$
$$R(2n) = R(n) + R(n + 1) + n ,\qquad \forall n \gt 1$$
$$R(2n + 1) = R(n - 1) + R(n) + 1 ,\quad \forall n\ge 1$$
Now I want to find the reverse of this function. I know that first of all, I should solve the relation then after finding the function calculate the reverse. But the problem is that since the relations are different for even and odd numbers I cant figure out how to find a unique solution or even when I try to solve them separately, since the variables have coefficient it seems complicated.
For more clarification, here is an example, of how you can find the inverse of the Tower of Hanoi:
$$H_n = 2H_{n−1} + 1$$ $$= 2(2H_{n−2} + 1) + 1 = 2^2 H_{n−2} + 2 + 1$$ $$= 2^2 (2H_{n−3} + 1) + 2 + 1 = 2^3 H_{n−3} + 2^2 + 2 + 1$$ $$.$$ $$.$$ $$= 2^{n−1} H_1 + 2^{n−2} + 2^{n−3} + · · · + 2 + 1$$ $$= 2^{n−1} + 2^{n−2} + · · · + 2 + 1$$ $$= 2^{n} − 1.$$
Now the inverse is
$$\log_2(H - 1)$$