Pen and paper gave me M(1) = 3, M(2) = 8, and we know M(3) = 15, with this I found https://oeis.org/A005563 and it has a description "This is also the number of moves that it takes n frogs to swap places with n toads on a strip of 2n + 1 squares (or positions, or lily pads) where a move is a single slide or jump" which is exactly our problem more commonly known as Toads and Frogs Problem.
The sequence gives us the following:
(1) xn+1 = 3 xn + 2 yn + 3
(2) yn+1 = 4 xn + 3 yn + 5
And the 2 initial conditions (x1, y1) = (0, 0), (x1, y1) = (0, -1) gave me all the solutions
Enter a number (yourinput)
Code will output the sum of the first yourinput terms