这种没办法归纳吧

the solution you posted seems not right to me.. the answer should not be equal to the sum of f_n(k).. Instead maybe you should prove that the limit of f_n(k) is zero when n goes to infinity.. something like when you proved that Pr{stoppng time=infinity}=0 (here f_n(k) is actually a stopping time), then it's equivalent to Pr{S_n=k for some finite n}=1..
To prove f_n(k)->0 when n->infinity, you could just use the Stirling's formula for those factorials..