IBM Ponder This #101 · September 2006

Puzzle for September 2006.

Let f(n) be a function on the non-negative integers defined recursively as follows:

f(0)=1, f(n)=(1+(n*n-n)*f(n-1))/(n*n+1) for n > 0. So f(1)=1/2, f(2)=2/5 ...

This month's puzzle asks for you to determine the asymptotic behavior of f(n) as n -> infinity. In other words find a simple function g(x) such that f(n)/g(n) -> 1 as n -> infinity.

Solution

Best opened after a real attempt

To be added.