Числовая последовательность

[Nikys]

(Оффтоп)

ІІІ обласний етап олімпіади з математики для школярів Київщини, 26 лютого 2012 року, 11 клас

До конца неразрешенная мною вчера задача.
Дана числовая последовательность такая, что $a_1 = 2$, $a_{n+1}=a_n(a_n - 1)+1$. Найти дробную часть суммы $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_{2012}}$.

На олимпиаде доказал две леммы. Во-первых:
Лемма 1. $a_1 \cdot a_2\cdot...\cdot a_n = a_{n+1} - 1 \forall n \in \mathbb{N}, n \geq 2$.
Легко показать это.
По базе индукции, при $n=2$: $a_1 \cdot a_2 = 2\cdot3=7 - 1 = a_3 - 1$.
Положим, что при некотором $n=k$ исполняется это утверждение. Действительно,
$a_1 \cdot a_2\cdot...\cdot a_k = a_{k+1} - 1$
Тогда при $n=k+1$:
$a_1 \cdot a_2\cdot...\cdot a_k \cdot a_{k+1} = (a_{k+1}-1)\cdot a_{k+1} = a_{k+2} - 1$
по условию и из предположения.
Поэтому утверждение правильно.
Лемма 2. Сумму вида $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_n}$ можно представить в виде $\frac{a_1 \cdot a_2 \cdot ... \cdot a_n - 1}{a_1 \cdot a_2 \cdot ... \cdot a_n} \forall n \in \mathbb{N}, n \geq 2$.
Доказательство также базируется на методе мат.индукции.
При $n=2$: $\frac{1}{2}+\frac{1}{3}=\frac{5}{6}=\frac{2\cdot3-1}{2\cdot3}$.
Пусть при некотором $n=k$: $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_k} = \frac{a_1 \cdot a_2 \cdot ... \cdot a_k - 1}{a_1 \cdot a_2 \cdot ... \cdot a_k}$.
Тогда при $n=k+1$:
$\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_k}+\frac{1}{a_{k+1}} = \frac{a_1 \cdot a_2 \cdot ... \cdot a_k - 1}{a_1 \cdot a_2 \cdot ... \cdot a_k} + \frac{1}{a_{k+1}} = \frac{a_1 \cdot a_2 \cdot ... \cdot a_k \cdot a_{k+1} - a_{k+1} + a_1 \cdot a_2 \cdot ... \cdot a_k}{a_1 \cdot a_2 \cdot ... \cdot a_k \cdot a_{k+1}} = \frac{a_1 \cdot a_2 \cdot ... \cdot a_k \cdot a_{k+1} - (a_{k+1}-1) + a_1 \cdot a_2 \cdot ... \cdot a_k - 1}{a_1 \cdot a_2 \cdot ... \cdot a_k \cdot a_{k+1}} = \frac{a_1 \cdot a_2 \cdot ... \cdot a_k \cdot a_{k+1} - 1}{a_1 \cdot a_2 \cdot ... \cdot a_k \cdot a_{k+1}}$
по предположению и 1-й лемме соответственно.

Тогда $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_{2012}} = \frac{a_1 \cdot a_2 \cdot ... \cdot a_{2012} - 1}{a_1 \cdot a_2 \cdot ... \cdot a_{2012}} = 1 - \frac{1}{a_{2013}-1}$.

А далее у меня большая просьба помочь с решением. Ясно, что дробная часть суммы и есть сама сумма. А вот с вычислением как быть...

(Оффтоп)

В 10-м классе была аналогичная задача, но там требовалось доказать, что целая часть этой суммы равна нулю. Собственно, я это уже доказал.
P.S. У моего преподавателя есть предположение, что задачу на область прислал товарищ dm (форумчане, думаю, понимают, о ком я)) ). Хотя, может и ошибается...

[Хорхе]

Похоже на корявое условие. Точной формулы "нет": A000058. Так что замысел авторов непонятен.

[Nikys]

Хорхе в сообщении #543299 писал(а):

Похоже на корявое условие. Точной формулы "нет": A000058. Так что замысел авторов непонятен.

Хорхе
Вполне возможно, во-всяком случае, я это "точную формулу" также не получил ни символьным, ни численным вычислением, ни переведением последовательности из рекурентной в общую, ни введением дополнительных последовательностей... Или тут очень "олимпиадный" подход. Мне почему-то кажется, что задача "искусственная", т.е., было решение - сделали задачу, и для решения надо применять неочевидный подход или последовательность. Или как однажды было на Всеукраинской олимпиаде по математике, когда на разборе задач автор сказал "Жюри знает решение задачи" и ушел, так как дали задачу, не зная решение (которое на тот момент так и не было приведено, к сожалению, не скажу, что именно за задача, но слышал из уст разных преподавателей).
Можно ещё заметить, что $a_{n+1} - a_n = (a_n - 1)^2$. Тогда после суммирования 2012 последовательных таких записей $a_{2013} = (a_1 - 1)^2 + (a_2 - 1)^2 + ... +(a_2012 - 1)^2$. Можно ещё пытаться выводить что-то из произведения по лемме 1, но оно по спуску превратится в гигантское сложение, которое имеется уже по определению, так как из него и получено.

[Хорхе]

Тут даже олимпиадный подход не поможет. Дело ведь какое. Это последовательность довольно стандартная, имеет имя, маленький номер в OEIS, статью в википедии. То есть много людей ковыряли, думали. И все, до чего додумались - формула Варди

$$ a_n=[c^{2^n}+1/2] $$

с какой-то совершенно непонятной постоянной $c$.

От Вас же потребовали фактически выписать 2013-й член последовательности. Вооружившись техникой, Вы могли бы, конечно, его выписать, но я думаю, бумаги для этого не хватило бы у всех участников. Или можно было бы записать его через формулу Варди, но опять-таки, вопрос в постоянной $c$, которая не пойми чему равна. Чтобы достичь необходимой точности, Вам пришлось бы выписать тысячу (или тысячи) знаков $c$.

Короче говоря, задача составителям не удалась: решить ее участники не могли никак. Если бы задание было "найдите первые 1000 знаков после запятой в числе ...", то с ней можно было бы справиться, в этой формулировке - нет.

Думаю, dm к этому безобразию непричастен

[Nikys]

Хорхе
Это да...Даже не знаю, честно говоря. Но то, что задача серьезна - это согласен. Но все же, может будут какие-то дополнительные рассуждения, приближающие к решению...
А кстати, какие бы были предложения по решению задачи в Вашей формулировке? :) Просто не сказал бы, что задача из простых. Хотяя...На олимпиаде тысячу знаков и не дали бы) Хотя... какая гарантия, что это не девятки?)

[Dave]

(Оффтоп)

Хорхе в сообщении #543312 писал(а):

Это последовательность довольно стандартная, имеет имя, маленький номер в OEIS, статью в википедии.

Маленький номер в OEIS - это даже круче, чем нули в номерах автомобилей

Nikys в сообщении #543319 писал(а):

Хорхе
Это да...Даже не знаю, честно говоря. Но то, что задача серьезна - это согласен. Но все же, может будут какие-то дополнительные рассуждения, приближающие к решению...
А кстати, какие бы были предложения по решению задачи в Вашей формулировке? :) Просто не сказал бы, что задача из простых. Хотяя...На олимпиаде тысячу знаков и не дали бы) Хотя... какая гарантия, что это не девятки?)

По индукции просто доказать (очень грубую) оценку $a_n>2^{2^{n-2}}$ для любого $n$. Из неё, из формулы $S=\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_{2012}} = 1 -\frac{1}{a_{2013}-1}$, а также из того, что $2^{10}>10^3$, получаем, что $1-\dfrac 1 {10^{3 \cdot 10^{602}}} \leqslant S < 1$, а это означает, что девяток в десятичной записи $S$ не менее $3 \cdot 10^{602}$, т.е. более чем достаточно, чтобы исписать любую олимпиадную тетрадь.

[MrDindows]

Nikys в сообщении #543289 писал(а):

Тогда $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_{2012}} = \frac{a_1 \cdot a_2 \cdot ... \cdot a_{2012} - 1}{a_1 \cdot a_2 \cdot ... \cdot a_{2012}} = 1 - \frac{1}{a_{2013}-1}$.

Быть может это и есть ответ?
Дробную часть ведь нужно "найти", а не "вычислить")

[Nikys]

MrDindows
Оригинально, я даже не задумался! Вполне возможно))

[Хорхе]

Если авторы имели в виду такое, то это еще пущее безобразие, ведь нормальный участник олимпиады не будет считать это окончательным ответом. Хоть он, конечно, и запишет все, что ему удалось доказать, он будет продолжать тратить свое время на эту задачу.

[Nikys]

Хорхе
Уточню степень безобразия.

Цитата:

Знайти дробову частину числа, що є значенням виразу

То есть, задача действительно нерешаема. Представить её в зависимости от n-го члена тоже невозможно.

-- 29.02.2012, 22:53 --

Хорхе в сообщении #543487 писал(а):

Если авторы имели в виду такое, то это еще пущее безобразие, ведь нормальный участник олимпиады не будет считать это окончательным ответом. Хоть он, конечно, и запишет все, что ему удалось доказать, он будет продолжать тратить свое время на эту задачу.

Что произошло. Но по условию - это не конечный ответ.

[TOTAL]

Nikys в сообщении #543289 писал(а):

Лемма 2. Сумму вида $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_n}$ можно представить в виде $\frac{a_1 \cdot a_2 \cdot ... \cdot a_n - 1}{a_1 \cdot a_2 \cdot ... \cdot a_n} \forall n \in \mathbb{N}, n \geq 2$.
Доказательство также базируется на методе мат.индукции.
При $n=2$: $\frac{1}{2}+\frac{1}{3}=\frac{5}{6}=\frac{2\cdot3-1}{2\cdot3}$.
Пусть при некотором $n=k$: $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_k} = \frac{a_1 \cdot a_2 \cdot ... \cdot a_k - 1}{a_1 \cdot a_2 \cdot ... \cdot a_k}$.
Тогда при $n=k+1$:
$\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_k}+\frac{1}{a_{k+1}} $

Тогда при $n=k+1$:
$\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_{k+1}-1}+\frac{1}{a_{k+1}} $

[Nikys]

TOTAL

(Оффтоп)

Мм? Немного не понял.

[TOTAL]

Nikys в сообщении #544330 писал(а):

Мм? Немного не понял.

Надо найти сумму $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_{k+1}-1}+\frac{1}{a_{k+1}} $, а не $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{a_{k}}+\frac{1}{a_{k+1}} $

[Dave]

Не знаю, какой ответ хотел увидеть автор этой задачи, но мне удалось вывести следующую формулу:

$$a_n=g(c^{2^n})+1, \eqno(1)$$

где

$$g(x)=x-\frac 1 2-\frac 1 {8x} - \frac 9 {128x^3} - \frac 9 {1024x^5} - \dots - \frac {b_n} {x^{2n-1}} - \dots$$

(подробнее см. это сообщение), а константа $c$ определяется как $c=\sqrt {t}$, где $t$ - единственный положительный корень уравнения $g(t)=1$. Считать формулу $(1)$ явным видом или нет - личное дело каждого. С одной стороны, от одной последовательности $(a_n)$ мы перешли к другой - $(b_n)$, да ещё и к бесконечному ряду. С другой - перешли от дискретного к непрерывному случаю, который анализировать гораздо удобнее. И никаких целых частей, как в вышеупомянутой формуле Варди, так что прогресс налицо. Начинать последовательность $(a_n)$ можно с любого числа, большего $1$, формула $(1)$ будет отличаться только константой $c$. Можно также заменить степени вида $c^{2^n}$ на $2^{2^{n+k}}$, где $k=\log_2 \log_2 c$ - тогда $k$ будет иметь наглядный смысл индекса (возможно, дробного), на который смещается последовательность при замене начального значения.

[Nikys]

Цитирую составителя задачи, называйте как хотите:

Н.В.П. писал(а):

Существуют задачи сформулированные корректно, а есть такие, которые заставляют задуматься. Первоначально задача формулировалась как поиск целой части последовательности и была представлена для 10 класса. Я же предложил немножечко усложнить задачу и предложить 11 классу найти дробную часть суммы. Задача состояла в том, чтобы не только доказать, что сумма меньше единицы, но и преодолеть этот барьер "трех точек", представив сумму в более простом виде. Более того, последовательность задана рекуррентно и, если вы попробуете вернуться к первому члену последовательности, то заметите, что она не имеет общей формулы для n-го члена. Так что, ваше решение и есть ответ задачи.

Спасибо всем за измышления. Много узнал в теме полезного, да и немного вперед продвинулась проблема. Думаю, тема "что имели в виду составители" теперь закрыта. Предлагаю оставить тему в виде "Последовательность Сильвестера и египетские дроби" как открытый научный вопрос.

-- 06.03.2012, 20:15 --

TOTAL
Да нет, сумма то задана в виде:
$f(n)=\sum\limits_{i=1}^n \frac{1}{a_i}$, $f:\mathbb{N} \rightarrow \mathbb{R}$