The Modified Faro shuffle. I came across this problem in George Andrews's book "Number Theory" (section 4-3, problem 2).  It deals with a modified version of the Faro shuffle that behaves as such:
$$(1,2,3,4,5,6,7,8) \rightarrow (4,5,3,6,2,7,1,8)$$
Essentially you cut the deck in half, flip the top half ($1,2,3,4$ in our example), and then shuffle them back together ensuring that the bottom card (8) stays at the bottom.  The question asks us to prove that a deck with $2^n$ cards will return to it's original state after $n + 1$ shuffles.
The book implies that this is solved using congruence relations but I haven't been able to come up with anything substantial.  I see that the piece-wise function
$$f1(x) = -2x \mod(2^{n} + 1)\quad \text{for}\quad \{x: 1 \le x \le 2^{n-1}\}$$
and 
$$f2(x) = 2x + 1 \mod(2^{n} + 1) \quad \text{for}\quad \{x: 2^{n-1} \lt x \le 2^{n}\}$$
correctly map the elements but repeated composition of this function hasn't gotten me anywhere.  (These two pieces can be combined into one function using an absolute value operator but composition is just as ugly)  Any hints or insights you can provide would be appreciated.
 A: Something which may (or may not help) : You can represent these operations with permutation matrices, for the example where the deck is 8 (for simplicity to read whitespace means zeros):
$${\bf P}_{fliptop} =\left[\begin{array}{cccccccc} & & &1& & & & \\ & &1& & & & & \\ &1& & & & & & \\1& & & & & & & \\ & & & &1& & & \\& & & & &1& & \\ & & & & & &1& \\ & & & & & & &1\end{array}\right], {\bf P}_{shuffle} = \left[\begin{array}{cccccccc}1& & & & & & & \\ & & & &1& & & \\ &1& & & & & & \\ & & & & &1& & \\ & &1& & & & & \\ & & & & & &1& \\ & & &1& & & & \\ & & & & & & &1\end{array}\right]$$
Now if we do ${\bf P}_{shuffle}{\bf P}_{fliptop}$ on our column vector:
$${\bf P}_{shuffle}{\bf P}_{fliptop}[1,2,3,4,5,6,7,8]^T = [4,5,3,6,2,7,1,8]$$
Which is as in the question. Now the combined operation is just the matrix product between the matrices above.
A: This shuffle is known as a 'Milk Shuffle' and its inverse is the 'Monge Shuffle'. See The mathematics of the flip and horseshoe shuffles Section 6. The Monge Shuffle for Two-Power Decks suggests a method for solving this problem.
Ignore the bottom card (since it never changes position) and renumber the cards from bottom to top. 
With the new scheme, we see that $x \rightarrow 2x$ for $x \le 2^{n - 1}$ and $x \rightarrow 2^{n+1} - 1 - 2x \equiv -2x \pmod {2^{n+1}-1}$ for $ > 2^{n-1}$.
Thus, after $s$ shuffles, the position of a card starting in position $x$ is congruent to either $2^s \pmod {2^{n+1} - 1}$ or $- 2^s \pmod {2^{n+1} - 1}$. $2^{n+1} \equiv 1 \pmod {2^{n+1} -1}$ and the position of a card can never be congruent $-1 \pmod {2^{n+1} -1}$ (since the position is always between $1$ and $2^n -1 $). Therefore $n+1$ shuffles will return each card to it's starting position.
