Найти тему
Злой дядька

Квадратичная рекуррента. Телескопический метод

Докажите, что если u[0]=0,001,
u[n+1]=u[n](1-u[n]) при n>=0,
то u[1000]<1/2000.

Я не знаю олимпиадной истории этой задачи, но искренне верю, что она есть. Буду благодарен тому, кто сообщит мне её.

Для начала по индукции докажем, что все члены нашей последовательности будут между 0 и 1. Действительно,
если 0<u[n]<1, то по неравенству о средних
0<u[n+1]=u[n](1-u[n])<=((u[n]+(1-u[n]))/2)^2=1/4<1.

Для доказательства оценки воспользуемся приёмом, который часто применяется в такого рода задачах: рассмотрим выражение 1/u[n]. Тогда
1/u[1]=1/u[0]+1/(1-u[0]);
1/u[2]=1/u[1]+1/(1-u[1]);
1/u[3]=1/u[2]+1/(1-u[2]);
...
1/u[999]=1/u[998]+1/(1-u[998]);
1/u[1000]=1/u[999]+1/(1-u[999]).

Сложив все эти равенства, получим
1/u[1000]=1/u[0]+1/(1-u[0])+1/(1-u[1])+...+1/(1-u[999])>2000.
Поэтому
u[1000]<1/2000.