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.

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

1 Answer 1


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.

  • $\begingroup$ whats the intuition behind $x_n = a_n - 1$ and where did you get the relation for $1+x_{n+1}$ thx $\endgroup$
    – HellBoy
    Nov 7, 2023 at 22:20
  • $\begingroup$ 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 $\endgroup$ Nov 7, 2023 at 22:24
  • $\begingroup$ What an elegant solution!! $\endgroup$
    – pie
    Nov 7, 2023 at 22:26
  • $\begingroup$ 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? $\endgroup$
    – HellBoy
    Nov 7, 2023 at 22:30
  • 1
    $\begingroup$ I didn't believe it blindly. I checked their proof with pen in hand. I advise you to do so, and to ask the OP if there is some step which you don't follow. @MOHAMEDSALHI $\endgroup$ Nov 7, 2023 at 22:36

You must log in to answer this question.

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