# The inequality about recurrence sequence

Sequence $(x_n)$ is difined $x_1=\frac {1}{100}, x_n=-{x_{n-1}}^2+2x_{n-1}, n\ge2$

Prove that $$\sum_{n=1}^\infty [(x_{n+1}-x_n)^2+(x_{n+1}-x_n)(x_{n+2}-x_{n+1})]\lt \frac {1}{3}$$

I found relation $(1-x_n)=(1-x_{n-1})^2$

I don't know what to do next.

There is a real number which is less than $\frac {1}{3}$?

-

A direct proof (note that I've shifted indices from starting at 1 to 0):

First, notice that $x_n\to1$ is the only possible limit. ($x=-x^2+2x \implies (x-1)^2=0$)

 The obvious mistake in my algebra was pointed out -- $x^2=x$ so $x=0$ or $1$. Recentering about $x=0$ doesn't change the recurrence, but recentering about $x=1$, as you can see below, yields a relation that can be solved by inspection.[/edit]

When in doubt, recenter your system about the fixed point; define $a_n=1-x_n$. Then, $$a_{n+1} = 1-x_{n+1} = 1-[-x_n^2+2x_n] = 1+x_n^2-2x_n=(1-x_n)^2=a_n^2.$$

This allows us to solve the system exactly; $a_n = a_0^{2^n}$, or $1-x_n=(1-x_0)^{2^n}$.

It should now be a matter of algebra to evaluate the sum.

-
No. $x = -x^2+2x \implies x^2-x = 0 \implies x(x-1)=0 \implies x=1$ or $x = 0$. – marty cohen May 13 '14 at 0:27
Can you show me a algebra to evaluate the sum? – user148928 May 13 '14 at 0:32
@marty, oops. :-) But the results are still good. $x=0$ obviously just yields the same recurrence, while $x=1$ will yield the solvable relation. – Jason May 14 '14 at 3:53
@user148928, just substitute the closed form solution to $x_n$. I suspect you'll get something like $(1-x_0)^{2^n+stuff}$. The trick then will be to bound $(1-x_0)^{2^n} < (1-x_0)^n$, then apply geometric series summation formula. – Jason May 14 '14 at 3:57