# Finding the growth rate of a recurrence relation $a(n+1)=a(n) + 1-1/(1+10^{-2a(n)})$

I have a recurrence relation that I'm interested in for a research project: $$a(n+1) = a(n) + K\Big(1-\frac{1}{1+10^{c-2a(n)}}\Big)$$ Where K and c are defined constants. The simpliest senario, when K=1 and c=0 implies that: $$a(n+1) = a(n) + \Big(1-\frac{1}{1+10^{-2a(n)}}\Big)$$

I think that a(n) grows like or is asymptopic to $$\frac{\ln(n)}{2\ln(10)}$$ as n goes to infinity, thus: $$a(n)\in O(\ln(n))$$

However, I'm not sure how to show it. I cannot solve the recurrence relation. In generally I dont know how to work out the growth rate of recurrence relations so any help is apprecieted. I also dont know if my guess at is what $$a(n)$$ is asmyptopic too.

• You should make clear in your question that the case $c=0,K=1$ simplifies to the different-seeming recurrence in the title. Mar 28, 2022 at 17:10
• Your recurrence implies to $$a_{n+1}=a_n+\frac{K}{10^{2a_n-c}+1}$$ Mar 28, 2022 at 17:14
• Now your title and body disagree - the title is missing the $1-.$ Mar 28, 2022 at 17:15
• Note: $$\frac{\ln n}{2\ln 10}=\log_{100} n.$$ Mar 28, 2022 at 17:17
• Also, “asymptotic” is a much stronger term than the big-O notation. So rather than “that is…,” maybe “thus…” is more appropriate. Mar 28, 2022 at 17:19

Assuming that $$a_n$$ increases as $$n\to\infty$$ we can approximate as follows

$$\frac{a_{n+1}-a_n}{n+1-n}=\frac{1}{100^{a_n}+1}\approx a' = \frac{1}{100^{a}+1}$$

which is separable giving

$$a + \frac{100^a}{\ln 100}+ c_0 = n$$

then

$$a(n) = n-\frac{W\left(100^{n-c_0}\right)}{\ln 100}-c_0$$

Here $$W(\cdot)$$ is the product log function (Lambert function) and then

$$a(n) = \mathcal{O}\left(\ln n\right)$$

Note that $$1-\frac1{1+z^{-1}}=\frac{z^{-1}}{1+z^{-1}}=\frac{1}{1+z},$$ so your recurrence becomes:

$$a(n+1)=a(n)+\frac1{1+100^{a(n)}}$$

If $$b(n)=100^{a(n)},$$ the recurrence becomes:

$$b(n+1)=b(n)\cdot 100^{1/(1+b(n))}$$

Since $$f(x)=x\cdot 100^{1/(1+x)}$$ has $$f(x)>x$$ for all $$x,$$ then $$f$$ has no fixed point, so $$b(n)$$ is increasing and doesn’t converge.

But then $$\frac{1}{1+b(n)}\to 0.$$

Now:

\begin{align} f(x)-x&=x\left(100^{1/(1+x)}-1\right)\\ &=x\left(\exp\left(\frac{\ln(100)}{1+x}\right)-1\right) \end{align}

As $$x\to \infty,$$ $$\exp\left(\frac{\ln(100)}{1+x}\right)-1\sim \frac{\ln 100}{1+x}$$ So this means that: $$\lim_{x\to\infty} (f(x)-x)=\ln 100\lim\frac x{x+1}=\ln(100).$$

So if $$t(n)=b(n+1)-b(n)=f(b(n))-b(n)$$ then $$t(n)\to \ln(100).$$ The $$\frac{b(n+1)-b(1)}n=\frac{t(1)+\cdots +t(n)}{n}\to \ln(100).$$

So you get $$b(n)\sim\ln(100)n,$$ and thus $$a(n)\sim \log_{100}n+\log_{100}\ln(100).$$

But the constant is irrelevant for the asymptote, since $$b(n)\to\infty,$$ so you get $$a(n)\sim \log_{100} n.$$

I’ve used if $$g(n)\to\infty$$ and $$g(n)\sim h(n)$$ then $$\ln(g(n))\sim\ln(h(n)).$$ This is because:

$$\frac{g(n)}{h(n)}=\left(\frac{e^{\ln(g(n))/\ln(h(n))}}{e}\right)^{\ln(h(n))}$$

Since the left side converges to $$1,$$ and $$\ln(h(n))\to\infty,$$ this means that $$\frac{\ln g(n)}{\ln h(n)}\to 1,$$ or else the right side would not converge to $$1.$$