0
$\begingroup$

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.

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

2 Answers 2

1
$\begingroup$

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) $$

$\endgroup$
0
$\begingroup$

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.$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .