[Siegmund]

I came at it yet another slightly different way... and ran into an infinite series I couldn't add up, but it happens to agree exactly with the difference equation solution posted here. As a result, I now have one of the more bizarre combinatorics results I have ever seen.

Let's begin by considering another question: what is the probability that the frog will ever return to the square on which he is currently standing?

He can get there after 3 jumps, RLL LRL or LLR, with probability 3/8.

He can get there after 6 jumps, Rx2 and Lx4, 15 ways out of 64, but 3x3 of these paths repeat the 3-jump patterns twice, and only 6 are new ways.

In general, (3k choose k) ways to return after 3k jumps, but only 2/(3k-1) of these are "new".

The sum of (3k choose k) * 2/(3k-1) *2^(-3k), from 1 to infinity, gives us the probability the frog will return to his current position. Call this P.

Then the number of times the frog will return to his current position is a geometric distribution with parameter P, and the expected number of times the frog will visit a position, given that he visits it at least once, is 1/(1-P).

We also can see that the frog's average speed is 1/2 to the right... that is, his expected number of visits to each position must be 2.

Therefore, he must visit 2*(1-P) of the squares an average of 1/(1-P) times each, and never visit the remaining 2P-1 squares at all.

As it happens, P~.572949017, which is jason's 1-M, and 2P-1 comes out to f97's Y.

What a roundabout way to show that sum[3k choose k)*2/(3k-2)*2^(-3k), {k,1,Infinity}] = (9-3sqrt(5))/4. The difference-equation route is certainly an elegant way to get the exact answer... but hopefully this shows the connection between the two correct methods posted.