# Prove that $\sum_{n=1}^\infty \dfrac{1}{\log_2(a_n)}$ converges.

Let $$a_0 = 2.$$ For $$n\ge 1,$$ let $$a_n$$ be the smallest positive integer so that $$\sum_{j=0}^n 1/a_j < 1$$. Prove that $$\sum_{n=1}^\infty \dfrac{1}{\log_2(a_n)}$$ converges.

I think one can come up with a recurrence relation for the $$a_n$$'s. Computing a few values of $$a_n,$$ we get that the sequence starts with $$2,3,7,43.$$ Now if we guess that the sequence is quadratic so that $$a_{n+1} = A a_n^2 + B a_n + C$$ for some constants A,B,C, then we can arrive at the formula $$a_{n+1} = a_n^2 - a_n+1.$$ This formula can be proved by induction if we additionally prove that $$\sum_{j=0}^n 1/a_j = 1 - 1/(a_n^2 - a_n)$$, with the base case of $$n=1$$ being obvious. Now assume the formula holds for some $$n\ge 1.$$ Then $$a_{n+1} = a_n^2 - a_n + 1$$ by the inductive hypothesis, and $$\sum_{j=0}^{n+1} 1/a_j = 1 - 1/((a_n^2 - a_n)(a_n^2 - a_n+1)) = 1 - 1/(a_{n+1}(a_{n+1}-1)).$$ So $$a_{n+2} = a_{n+1}^2 - a_{n+1}+1$$. Hence the result follows by induction. Now that we have a useful recurrence relation for the $$a_n$$'s, we could finish the problem if we could show that $$a_n \ge 2^{n^p}$$ for some $$p > 1$$, but I'm not sure which choice of p would work. Or one could find an alternative lower bound for the $$a_n$$'s that'll guarantee the convergence of the given series.

• how did you come up with the relation for $a_{n+1}$? Nov 7, 2023 at 22:38
• Hint: prove $a_{n+1}>\frac12a_n^2$, then prove $\log_2a_n\ge2^n-1$.
– J.G.
Nov 7, 2023 at 22:50

Let $$x_n:=a_n-1$$. Then, $$x_1=2$$ and $$1+x_{n+1}=(1+x_n)^2-(1+x_n)+1$$, hence $$x_{n+1}=x_n(1+x_n)>x_n^2,$$ so that $$\log_2(a_n)>\log_2(x_n)>2^{n-1}$$ and the convergence of the series follows.
• whats the intuition behind $x_n = a_n - 1$ and where did you get the relation for $1+x_{n+1}$ thx Nov 7, 2023 at 22:20
• I took advantage of the relation $a_{n+1}=a_n^2-a_n+1$ proved by the OP, and the solution of $a=a^2-a+1$ being $a=1$ gave me the idea of looking at the sequence $x_n=a_n-1.$ @MOHAMEDSALHI Nov 7, 2023 at 22:24
• yea OP said "I think one can come up with a recurrence relation for the $a_n$'s. Computing a few values of an, we get that the sequence starts with 2,3,7,43." how is a such wild guess boiled? Nov 7, 2023 at 22:30