2

I need to upper bound the following recurrence

$$f(n+1)=f(n)\times\left( 1-\frac{f(n)}{1-f(n)} \right), f(1)<\frac{1}{4} $$

Question I would like a strictly decreasing function $g(n)$ such that $f(n) < g(n)$.

I know that $0<f(n)<\frac{1}{4}$ is strictly monotonically decreasing, and that a limit exists. So far, I can show that $f(n\log(n))\leq \frac{1}{n}$, but this was derived with simple methods, and plotting the function shows that a better bound likely exists.

Motivation I have an algorithm that finds a graph matching with "quality" $f(n)$ after $n$ iterations, where smaller is better, and I wish to know how many phases are needed to achieve a given quality.

Lieuwe Vinkhuijzen
  • 653
  • 4
  • 10

1 Answers1

3

Writing $x_{n}=1/f(n)$ with $L>x_1>4$, gives $$x_{n+1}=1+x_n+\frac{2}{x_n-2}.$$ One can establish by induction for $n\geq 2$ that $$3+n+\frac{2}{L+6-8}+\cdots+\frac{2}{L+3n-8} <x_n < L-3+n+2 \left (\frac{1}{1}+\cdots+\frac{1}{n} \right ).$$

It follows that there exist constants $c_1,c_2$ such that $n+(2/3) \log n +c_1 < x_n < n+2 \log n +c_2$ for $n$ large enough. This gives $$f(n) < \frac{1}{n+(2/3)\log n +c_1}.$$

Marco
  • 2,733
  • 6
  • 15