# Prove that the series$\sum a_n$, with $a_n$ defined recursively, converges to 1

Let $a_n$ , with $n\geq1$ be the sequence of real numbers defined by $a_1=\frac12$ and the following relation

$$a_{n+1}=\frac{a_n^2}{a_n^2-a_n+1}$$Prove that $\sum a_n$ converges to $1$.

Now, I have only been able to study the sequence defined by the recurrence relation. I know that it converges to zero by the monotone convergence theorem. I think I should prove that this is a geometric series like this $\sum_{n=0}^\infty \frac12\left(\frac12\right)^n$. What is the strategy I should follow in these cases? How would you approach this little problem?

Notice $\displaystyle\;a_{n+1} = \frac{a_n^2}{a_n^2 - a_n + 1}\;$ implies $$\frac{a_{n+1}}{1 - a_{n+1}} = \frac{a_n^2}{(a_n^2 - a_n + 1) - a_n^2} = \frac{a_n^2}{1-a_n} = -a_n + \frac{a_n}{1-a_n}$$ This leads to $$a_n = \frac{a_n}{1-a_n} - \frac{a_{n+1}}{1-a_{n+1}} \implies \sum_{n=1}^N a_n = \frac{a_1}{1-a_1} - \frac{a_{N+1}}{1-a_{N+1}} = 1 - \frac{a_{N+1}}{1-a_{N+1}}$$ Since you alreadly know $a_{N} \to 0$ as $N\to \infty$, you get

$$\sum_{n=1}^\infty a_n = \lim_{N\to\infty}\sum_{n=1}^N a_n = \lim_{N\to\infty} \left(1 - \frac{a_{N+1}}{1-a_{N+1}}\right) = 1 - \frac{0}{1-0} = 1.$$

Motivation behind the proof

On the surface, the use of expression like $\frac{a_n}{1-a_n}$ in above proof looks magical. In truth, it is the same tactic we used to attack other problems that involve series whose terms are defined recursively.

What we have done is compute a few values of the sequence $a_n$ and the partial sums $\smash{\sum\limits_{n=1}^N a_n}$ and then observe/detect the patterns.

• If one compute the first few terms of $a_n$, we find it is given by $\frac12,\frac13,\frac17,\frac{1}{43},\ldots$ This leads one to suspect all $a_n$ are reciprocals of integers.
• If one define sequence $b_n$ as $\frac{1}{a_n}$. It is easy to deduce $b_n$ satisfies the recurrence relation: $$b_{n+1} = b_n^2 - b_n + 1$$ Since $b_1 = 2$ is an integer, so does all $b_n$. So our intuition that all $a_n$ are recipocals of integers are true.
• If one compute the few values of the partial sums $\sum_{n=1}^N a_n$, we find it is given by $\frac12, \frac56 = 1 - \frac16, \frac{41}{42} = 1 - \frac{1}{42},\ldots$. The pattern is $$\sum_{n=1}^{N} a_n = 1 - \frac{1}{b_{n+1}-1} = 1 - \frac{a_{N+1}}{1-a_{N+1}}$$ If this is true for all $N$, then $a_{n}$ need to satisfy a recurrence relation $$a_n = \frac{a_n}{1-a_n} - \frac{a_{n+1}}{1-a_{n+1}}\tag{*1}$$
• We take above as a hint/direction, prove $(*1)$ directly using the recursive definition of $a_n$. The remaining steps simply follows.
• You are the man. – Charlie Sep 5 '14 at 10:59
• So, in these situations I should work on partial sums right? – Charlie Sep 5 '14 at 11:02
• @Charlie It is not something "one should work on the partial sums". Instead, it is the common tactics to compute the first few terms of the sequences and partial sums and observer the patterns. It just turn out in this case, the partial sums and the next term in sequence exhibit a pattern which we can use. See update of answer for the background thoughts that lead to the answer. – achille hui Sep 5 '14 at 12:34
• The best answer I've ever received. Thank you very much Achille. – Charlie Sep 5 '14 at 13:15
• It was very good you added a proof motivation. Usually, 'math-people' avoid that and the proof comes 'from the air'. Recently, in trying to find the $\lim_{n\to\infty}$ of an integral I did something like that and some user doesn't like to know that because "that was not the way that a proof is shown". Good for you. – Felix Marin Sep 17 '14 at 21:27

First, note that since $x^2-x+1\geq \frac{3}{4}$ for every $x$ we have $$a_{n+1}\leq \frac{4}{3}a_n^2$$ and consequently by induction $$a_n\leq \frac{3}{4}\left(\frac{4}{3}a_1\right)^{2^{n-1}}=\frac{3}{4}\left(\frac{2}{3}\right)^{2^{n-1}}$$ In particular $\lim_{n\to\infty}a_n=0$. Now, define $S_n=\dfrac{1-2a_{n+1}}{1-a_{n+1}}$. Clearly we have $$S_n=\frac{1-a_n-a_n^2}{1-a_n}=a_n+\frac{1-2a_n}{1-a_n}=a_n+S_{n-1}$$ So $S_n=a_n+\cdots+a_2+a_1+S_0=\sum\limits_{k=1}^na_k$. It follows that $$\sum_{k=1}^\infty a_k=\lim_{n\to\infty}S_n=\lim_{n\to\infty}\dfrac{1-2a_{n+1}}{1-a_{n+1}}=1.$$

This in not an answer to your question but it is too long for a comment.

If you compute the first numbers, they are the reverse of $2,3,7,43,1807,3263443$ which correspnd to Sylvester's sequence: $b_{n+1} = b_n^2 - b_n + 1$, with $b_0= 2$ (sequence $A00058$ in OEIS). Going to OEIS, you will find very interesting information abou thee numbers.

These $b_n$ are also called Euclid numbers, because $$b_n = b_0 \times b_1 \times \cdots \times b_{n-1} + 1$$ So $a_n=\frac{1}{b_n}$.

I do not finish since Liu Gang sent a good demonstration.

I only prove $$S_{n}<1$$ because \begin{align*}a_{n}&=\dfrac{1}{1-\dfrac{1}{a_{n-1}}+\dfrac{1}{a^2_{n-1}}}<\dfrac{1}{-\dfrac{1}{a_{n-1}}+\dfrac{1}{a^2_{n-1}}}\\ &=\dfrac{1}{\dfrac{1}{a_{n-1}}-1}-\dfrac{1}{a_{n-1}}=-a_{n-1}+\dfrac{1}{-\dfrac{1}{a_{n-2}}+\dfrac{1}{a^2_{n-2}}}\\ &=-a_{n-1}-a_{n-2}+\dfrac{1}{-\dfrac{1}{a_{n-3}}+\dfrac{1}{a^2_{n-3}}}=\cdots=-a_{n-1}-a_{n-2}-\cdots-a_{1}+\dfrac{1}{\dfrac{1}{a_{1}}-1}\\ &=1-a_{n-1}-a_{n-2}-\cdots-a_{1} \end{align*}

Let $S_n = \sum_{k=1}^n a_k$, then we observe the following pattern:

$$S_1 = \frac{1}{2}, a_2 = \frac{1}{3}$$ $$S_2 = \frac{5}{6}, a_3 = \frac{1}{7}$$ $$S_3 = \frac{41}{42}, a_4 = \frac{1}{43}$$

Actually, if $S_n = \dfrac{k-1}{k} = 1 -\dfrac{1}{k}$ and $a_{n+1} = \dfrac{1}{k+1}$ then $S_{n+1} = \dfrac{k^2 + k -1}{k^2 +k} = 1- \dfrac{1}{k^2 + k}$ and $a_{n+2} = \dfrac{1}{k(1 +k) + 1}$.

ALl these suggest us to prove by induction $S_n = 1- \dfrac{1}{b_{n+1} - 1}$ and $a_{n+1} = \dfrac{1}{b_{n + 1}}$ with $b_{n+1} = b_n^2 - b_n + 1$ and $b_1 =2$. It's easy to see $b_n \to +\infty$

This is obvious when $n = 1$.

If this is true when $n = k$, i.e. if $S_k = 1- \dfrac{1}{b_{k+1} - 1}$ and $a_{k+1} = \dfrac{1}{b_{k + 1}}$ is true. then we can see $$a_{k+2} = \dfrac{a_k^2}{a_k^2 - a_k + 1} = \dfrac{1}{b_{k+1}^2 - b_{k+1} + 1} = \dfrac{1}{b_{k+2} }$$ and $$S_{k+1} = S_k + a_{k+1} =1 - \dfrac{1}{b_{k+1}^2 - b_{k+1}}= 1 - \dfrac{1}{b_{k+2} - 1}$$

• Could you please explicit the last two lines? I cannot understand how $b_n$ enters the reasoning. – Charlie Sep 5 '14 at 9:53
• @Charlie Sorry, there was a typo, I added several lines – Petite Etincelle Sep 5 '14 at 10:11
• Thanks, but why $b_{n+1}=b_n^2-b_n+1$? – Charlie Sep 5 '14 at 10:14
• @Charlie Because when you plug $a_n = \frac{1}{b_n}$ in your recurrence condition, you get $a_{n+1} = \frac{1}{b_n^2 - b_n + 1}$, that leads to take $b_n$ in this way – Petite Etincelle Sep 5 '14 at 10:19