4

$a_{n+1}a_n=a_n^2+a_n+1$, $a_1=1$,how to find integer $k$, make $\left|\sqrt{a_{2020}}-k\right|$ as small as possible.

Using computer, I get $a_{2020}\approx 2027.38$. then $\sqrt{a_{2020}}\approx 45.0264,k=45$

But without computer, how to calculate it?

I notice that if $\sqrt{a_{2020}}=XXX.6$,etc ,then $k=XXX+1$, else $k=XXX$. But then my ideas stuck.

KReiser
  • 65,137
AsukaMinato
  • 1,007

2 Answers2

5

We may note that our sequence is increasing, so it makes sense to rewrite the rule giving the sequence as $a_{n+1} = a_n+1+\frac{1}{a_n}$. The idea is to show that the contribution of the $\frac{1}{a_n}$ term is small, and in particular won't affect the estimate for what the square root is in this case.

Let $H_n=\sum_{i=1}^n \frac1i$, the $n^{th}$ harmonic number. Then for $n>1$, we have that $n + 1 \leq a_n \leq n+H_{n-1}$ by induction, which is relatively straightforwards. As $H_n \sim \ln n + \gamma +O(\frac 1n)$, this gives that $H_{2020}$ is approximately $\ln 2020$, which is certainly no more than $11$, as $2^{11}= 2048$. So $2021\leq a_{2020} \leq 2031$, and as $2025=45^2$, we see that $k$ must be $45$.

KReiser
  • 65,137
3

$a_1 = 1, a_{n+1} = a_n+1+\frac{1}{a_n} $.

Then $a_n > n$ and $a_{n+1} > a_n$.

$\begin{array}\\ a_{m+1}-a_1 &=\sum_{n=1}^m (a_{n+1}-a_n)\\ &=\sum_{n=1}^m (1+\dfrac1{a_n})\\ &<m+\sum_{n=1}^m \dfrac1{n}\\ &=m+H_m\\ &< m+\ln(m)+1\\ \end{array} $

so $a_{m+1} \lt m+\ln(m)+2 $.

$\dfrac1{a_m} \gt \dfrac1{m+1+\ln(m-1)} $ so

$\begin{array}\\ a_{m+1}-a_1 &=\sum_{n=1}^m (a_{n+1}-a_n)\\ &=\sum_{n=1}^m (1+\dfrac1{a_n})\\ &=m+\sum_{n=1}^m \dfrac1{a_n}\\ &=m+1+\sum_{n=2}^m \dfrac1{a_n}\\ &>m+1+\sum_{n=2}^m (\dfrac1{n+\ln(n)+1}-\dfrac1{n})+H_n-1\\ &=m-\sum_{n=2}^m \dfrac{\ln(n)+1}{n(n+\ln(n)+1)}+H_m\\ &>m+H_m-1.1\\ &>m+\ln(m)+.5-1.1\\ &=m+\ln(m)-0.6\\ \end{array} $

so $a_{m+1} \gt m+\ln(m)+.4 $.

Therefore $a_{2020} \gt 2028.01 $ and $a_{2020} \lt 2029.7 $ so $45.03 \lt \sqrt{a_{2020}} \lt 45.052 $.

Therefore $k = 45$.

marty cohen
  • 107,799