How many moves do I need to solve the leap frog puzzle? This is a standard puzzle that all of us have seen (and also probably appears in Conway's combinatorial game theory books).
There are $n$ green frogs and $n$ red frogs sitting on $2n+1$ lily pads in the given configuration
GGG_RRR

The frogs can only leap to an empty lilypad. They can jump over at most one frog.
The problem is to change the original configuration to
RRR_GGG

I want to show that this can be done optimally $(n+1)^2 - 1$ steps for each $n$. I tried doing this by trying to find a recurrence on $n$, but I failed.

To get the number of moves, look at how many spaces each frog must move.  Each frog moves $n+1$ spaces, so there are a total of $2n(n+1)$ spaces moved.  There are $n^2$ jumps where a frog moves two spaces, so the number of moves is $2n(n+1)-n^2=n^2+2n=(n+1)^2-1$  
To prove that a frog jumping another of the same color cannot be part of the optimum solution, assume it is a green frog.  We then must have GG_ with other frogs in the row.  How did we get here?  The first G could have jumped backwards, but then jumping forwards undoes the move and we would be better without the pair.  An R could have moved backwards, but then the front G should have jumped it and we would be farther along.  Finally, a G could have moved forwards, but then we had GG_ before (one space to the right) and we look at the move before that.
