Consider a sequence $u_k$ which satisfies
$ u_{k+1} \leq (1-\frac{1}{\sqrt{k}}) u_k + \frac{1}{k}$
At what rate does this sequence decay to zero?
This is not a homework problem. I seem to have worked out a proof which shows that it decays to zero asymptotically faster than $1/k^s$ for any exponent $s$. I think my proof might be wrong, and at any rate I'm wondering what the exact rate of decay is.