1

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.

Simon Shan
  • 128
  • One perhaps useful observation: if we generalize to $f_C(x) = (1-C \frac{x}{x+1})x$, then $f_1(x) = \frac{x}{x+1}$, and therefore $f_1^n(1) = \frac{1}{n}$. It's 3am where I am, so I'm going to bed, but I'll finish this up and answer tomorrow if someone doesn't beat me to it – HallaSurvivor Feb 09 '20 at 08:04
  • Thank you. Nice observation. I am thinking about how to generalize it to other C. – Simon Shan Feb 09 '20 at 16:23
  • I think I get some ideas about it. Thank you for your help. And this link might also be helpful for some similar problems: https://math.stackexchange.com/questions/2914361/upper-bound-the-recurrence-fn1-fn-left-1-fracfn1-fn-right?rq=1. – Simon Shan Feb 09 '20 at 22:14

0 Answers0