Pensieve header: Stephen’s frog hopping problem.

A frog hops across a pond over n water lilies, at each step making a random jump forward. How many steps is it expected to take?

f[1]=1;
f[n_] /; n>1 := f[n]= 1+Sum[f[k],{k,1,n-1}]/n;

Table[f[n], {n,1,20}]

Table[f[n], {n,1,20}]//N

g[1]=1.;
g[n_] /; n>1 := g[n]= 1+Sum[g[k],{k,1,n-1}]/n;

Table[g[n], {n,1,20}]

Table[g[(E^n)//Round], {n,10}] // Timing

s[0]=0; s[1]=1.;
s[n_] /; n>1 := s[n]=(n/(n-1))s[n-1]+1;
h[n_] := s[n]-s[n-1]

Table[h[n], {n,20}]

(E^10)//Round

Table[h[n], {n,(E^10)//Round}]//Last //Timing

Table[h[(E^n)//Round], {n,10}]