How to show the asymptotic behavior of a recurrence relation?

83 Views Asked by At

I have a question on a recurrence relation, which is $$f(x) = (1-(1-e^{-1})\frac{x}{x+1})x.$$ Consider a sequence starting from 1, i.e. $\{f^n(1)\}$. I find that when $n$ is large, $f^n(1)$ is very close to $\frac{1}{(1-e^{-1})n}$ by using a program to compare them. Is it possible to show that $\{f^n(1)\}$ is decreasing as $a/t$ or is upper bounded by $a/t$ for some constant $a$?

My intuition is when $x$ is small, the function $f(x)\approx x-(1-e^{-1})x^2$ which is a quadratic recurrence relation. And $\frac{1}{(1-e^{-1})n}$ is the solution to a related differential equation. I know it is hard to solve the closed form of such a recurrence relation. But, I want to know if it is possible to show that $f^n(1)$ will decrease as $\frac{a}{n}$ or be upper bounded by $\frac{a}{n}$ for some constant $a$. I tried to show such an upper bound by induction, but I stuck there.

I would be grateful for any suggestions.