How Can I Write This Recursive Definition (this is pretty hard, I think)?!?!?

Question

I have been working on this for a while and can't figure it out. It has been really troublesome for me. Any help would be appreciated.

Suppose that n people numbered 1 to n are lined up with their backs to a wall. Starting at the end of the line, eliminate every other person until only 1 survives. Reverse directions when you reach the end of the line. For example, for n=10, the elimination order is 2,4,6,8,10,7,3,5,1 so the survivor is 9. Let s(n) denote the survivor's number (hence S(10)=9). Find a recursive definition for S(n). You should have a base case and 2 recursive cases-- one for S(2k) and S(2k+1).

Answer 1

S(2)=1
S(2k)=2k+1-2S(k)
S(2k+1)=2k+3-2S(k+1)

Notice that S(2k-1)=2k+1-2S(k)=S(2k). This makes sense because if the original lineup has an even number of persons, the outcome is unchanged if you remove the last person before beginning the elimination process, because the last person was a goner anyway.