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
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
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.