# show that $\sum_{k=1}^{n}(1-a_{k})<\frac{2}{3}$

Let $a_{1}=\dfrac{1}{2}$, and such $a_{n+1}=a_{n}-a_{n}\ln{a_{n}}$,show that $$\sum_{k=1}^{n}(1-a_{k})<\dfrac{2}{3}$$

My attemp: let $1-a_{n}=b_{n}$,then we have $$b_{n+1}=b_{n}+(1-b_{n})\ln{(1-b_{n})}<b^2_{n}<\cdots<(b_{1})^{2^{n}}=\dfrac{1}{2^{2^n}}$$ where use $\ln{(1+x)}<x,x>-1$ so $$\sum_{k=1}^{n}(1-a_{k})<\sum_{k=1}^{n}\dfrac{1}{2^{2^{k-1}}}?$$

But $$\sum_{k=1}^{+\infty}\dfrac{1}{2^{2^{k-1}}}=0.816\cdots$$big than$\frac{2}{3}$,so this inequality How to prove it?

• I think it's sadism. – Michael Rozenberg Nov 3 '17 at 15:29
• Why don't you separate the sum: $$\sum_{k=1}^\infty\, \left(1-a_k\right)=\sum_{k=1}^n\,\left(1-a_k\right)+\sum_{k={n+1}}^\infty\,\left(1-a_k\right)\,?$$ Pick a good $n$ and use your estimate for $\sum_{k=n+1}^\infty \,\left(1-a_k\right)$. – Batominovski Nov 4 '17 at 5:55
• It's easy to see that the sequence $a_k$ in the question corresponds with a (fast converging) Newton-Raphson method for calculating numerically the zero at $x=1$ of the function $\,f(x) = \ln(x)$ : $$a_{n+1} = a_n - \frac{f(a_n)}{f'(a_n)} = a_n - \frac{\ln(a_n)}{1/a_n}$$ Then someone smarter than me might find the Wikipedia reference helpful to formulate a decent answer. – Han de Bruijn Dec 2 '17 at 11:09
• One formula in the abovementioned Wikipedia reference leads to: $$1-a_{n+1} \approx -\frac{f''(1)}{2f'(1)}(1-a_n)^2 = (1-a_n)^2/2$$ Giving rise to a sharper estimate than the $0.816\cdots$ in the question. – Han de Bruijn Dec 2 '17 at 11:25
• Maybe it could help your equality/condition is equivalent to : $$e^{W(\frac{a_{n+1}}{-e})+1}=a_n$$ where W(x) is the Lambert function . – user448747 Dec 4 '17 at 15:39

As used by the OP: $\enspace b_n:=1-a_n$

Examples: $\enspace\displaystyle b_1=0.5\enspace , \enspace b_2=0.5-0.5\ln 2\enspace , \enspace b_3 = b_2 + (1-b_2) \ln (1-b_2) <0.013$

We have: $\enspace b_n<-\ln(1-b_n)\enspace$ => $\enspace a_{n+1}=a_n(1-\ln a_n)>a_n(1+b_n)\enspace$ => $\enspace b_{n+1}<b_n^2\enspace$

Using $\,b_{n+1}<b_n^2\,$ we begin with $\,b_4=1-a_4<0.0001=0.1^{2^2}\,$ and get $\enspace b_n<0.1^{2^{n-2}}\,$ .

It follows:

$\displaystyle \sum\limits_{k=1}^n (1-a_k) < b_1 + b_2 + b_3 + \sum\limits_{k=4}^\infty 0.1^{2^{k-2}}$

$\displaystyle < 1- 0.5 \ln 2 + 0.013 + \sum\limits_{k=4}^5 0.1^{2^{k-2}} + \sum\limits_{k=4}^\infty 0.1^{12+k}$

$\displaystyle = 1- 0.5 \ln 2 + 0.013 + 0.00010001 + \frac{1}{9}0.1^{15}$

$\displaystyle < 1- 0.5 \ln 2 + 0.013 + 0.00010002 < 0,66652643 <\frac{2}{3}$

• good insight, still not nice and simple... – lion Nov 3 '17 at 19:03
• the last sum how to get the value $0.00010001$ – geromty Nov 27 '17 at 12:40
• @geromty : I think with $\,\sum\limits_{k=4}^\infty 0.1^{2^{k-2}} < 0.00010002\,$ it becomes clear. :-) – user90369 Nov 27 '17 at 16:32
• @geromty : $\enspace\displaystyle 0.00010001=\sum\limits_{v=2}^3 0.1^{2^v}$ – user90369 Nov 28 '17 at 9:01
• @lion : Now it's nice and simple. :-) – user90369 Nov 28 '17 at 9:02

You can add more coefficients in the Taylor expansion $$\log(1-x)\leq-x-x^2/2+...$$ in order to obtain the sharper bound $$b_{n}+(1-b_{n})\ln{(1-b_{n})}<b^2_{n}/2+b_n^3/2$$ and so on, if it is necessary.

• Then How to prove this inequality? – geromty Nov 3 '17 at 14:18
• @geromty: by Taylor series, for instance. The LHS is a primitive of $-\log(1-x)$ evaluated at $b_n$, and the Taylor series of $-\log(1-x)$ only has positive coefficients. – Jack D'Aurizio Nov 3 '17 at 14:22
• The bound is really sharp, however, since $$\sum_{k\geq 1}(1-a_k)\approx 0.665926577$$ – Jack D'Aurizio Nov 3 '17 at 14:26
• @JackD'Aurizio,can you post your solution? – geromty Nov 3 '17 at 14:28
• @geromty: I do not have an elegant solution at the moment. I just computed $(1-a_k)$ up to twelve figures for any $k\in[1,5]$, then exploited the shown bound for $\sum_{k\geq 6}(1-a_k)$. – Jack D'Aurizio Nov 3 '17 at 14:30