Глава
Теория
Последовательность в олимпиадной алгебре — это не просто список чисел. Нужно понять правило изменения: разности, отношения, рекурсию, инвариант или скрытую телескопическую сумму.
Для арифметической прогрессии \(a_n=a_1+(n-1)d\), \(S_n=\frac{n(a_1+a_n)}2\). Для геометрической прогрессии \(a_n=a_1q^{n-1}\), \(S_n=a_1\frac{q^n-1}{q-1}\) при \(q\ne1\). Рекурсии часто решаются заменой или индукцией.
Ищите последовательности, когда есть повторяющийся процесс, переход от \(n\) к \(n+1\), сумма многих похожих дробей, максимальное число после шагов или условие “для любого \(n\)”.
Если соседние члены отличаются на постоянное число — это арифметическая прогрессия. Если отношение постоянно — геометрическая. Если выражение вида \(u_k-u_{k+1}\), сумма телескопируется. Если процесс сохраняет величину, ищите инвариант.
Не путайте номер члена и сам член. Не забывайте базу индукции. В рекурсии с дробями проверяйте область допустимых значений. В задачах на подсчёт последовательностей сначала решите, что считается свободным выбором.
Выпишите первые члены. Посмотрите на разности и отношения. Попробуйте заменить \(b_n=a_n+c\) или \(b_n=\frac1{a_n}\). Проверьте телескопирование. Сформулируйте индукционный переход.
Примеры
Начинаем с явной формулы.
Задача. В прогрессии \(a_1=5\), \(d=3\). Найдите \(a_{20}\).
\(a_{20}=a_1+19d=5+57=62\).
Комментарий. Важно не заменить \(19\) на \(20\).
Сумма крайних членов одинаковых пар постоянна.
Задача. Найдите сумму \(7+10+13+\cdots+70\).
Это арифметическая прогрессия с \(a_1=7\), \(d=3\), \(a_n=70\). Тогда \(7+3(n-1)=70\), откуда \(n=22\). Сумма равна \(\frac{22(7+70)}2=847\).
Комментарий. Сначала найдите число членов.
Постоянное отношение даёт степень.
Задача. В прогрессии \(b_1=3\), \(q=2\). Найдите \(b_8\).
\(b_8=3\cdot2^7=384\).
Комментарий. Номер \(8\) даёт показатель \(7\).
Иногда формула угадывается по первым членам и доказывается индукцией.
Задача. Последовательность задана \(a_1=1\), \(a_{n+1}=a_n+2n+1\). Докажите, что \(a_n=n^2\).
База: \(a_1=1=1^2\). Если \(a_n=n^2\), то \(a_{n+1}=n^2+2n+1=(n+1)^2\). Значит, формула верна для всех \(n\).
Комментарий. Разность соседних квадратов равна \(2n+1\).
Сдвиг часто превращает рекурсию в геометрическую.
Задача. Пусть \(a_1=1\), \(a_{n+1}=2a_n+1\). Найдите \(a_n\).
Добавим \(1\): \(a_{n+1}+1=2(a_n+1)\). Поэтому \(a_n+1=2^n\), и \(a_n=2^n-1\).
Комментарий. Правильная замена убирает свободный член.
Сумма раскрывается после разложения дроби.
Задача. Найдите \(\sum_{k=1}^{n}\frac1{k(k+1)}\).
\(\frac1{k(k+1)}=\frac1k-\frac1{k+1}\). Поэтому сумма равна \(1-\frac1{n+1}=\frac n{n+1}\).
Комментарий. Почти все слагаемые сокращаются.
В процессе может сохраняться не сам член, а комбинация членов.
Задача. Последовательность задана \(a_{n+1}=3a_n+2\), \(a_1=0\). Докажите, что \(a_n+1\) — степень \(3\).
\(a_{n+1}+1=3a_n+3=3(a_n+1)\). Так как \(a_1+1=1\), получаем \(a_n+1=3^{n-1}\).
Комментарий. Инвариантная форма — \(a_n+1\).
Иногда последовательность определяется началом и шагами.
Задача. Сколько последовательностей \(a_1,\ldots,a_5\) натуральных чисел имеют \(a_1=3\) и \(|a_{i+1}-a_i|\le1\), если все члены положительны?
Каждый шаг равен \(-1,0\) или \(1\), но нужно следить, чтобы член не стал нулём. Начиная с \(3\) за четыре шага при изменении не больше \(1\) вниз до нуля дойти нельзя. Значит, все \(3^4=81\) набора шагов подходят.
Комментарий. Разностная последовательность — основной объект.
Задачи
В арифметической прогрессии \(a_1=4\), \(d=5\). Найдите \(a_{15}\).
Используйте \(a_n=a_1+(n-1)d\).
\(a_{15}=4+14\cdot5=74\).
В геометрической прогрессии \(b_1=2\), \(q=3\). Найдите \(b_6\).
Используйте \(b_n=b_1q^{n-1}\).
\(b_6=2\cdot3^5=486\).
Найдите \(\frac1{1\cdot2}+\frac1{2\cdot3}+\cdots+\frac1{10\cdot11}\).
Разложите \(\frac1{k(k+1)}\).
\(\frac1{k(k+1)}=\frac1k-\frac1{k+1}\). Сумма равна \(1-\frac1{11}=\frac{10}{11}\).
Последовательность задана \(a_1=1\), \(a_{n+1}=a_n+2n+1\). Найдите \(a_{20}\).
Докажите, что \(a_n=n^2\).
По индукции \(a_n=n^2\). Поэтому \(a_{20}=400\).
Найдите сумму всех положительных членов прогрессии \(53,48,43,\ldots\).
Сначала найдите последний положительный член.
Общий член \(a_n=53-5(n-1)\). Положительность даёт \(58-5n>0\), значит \(n\le11\). Последний член \(a_{11}=3\).
Сумма равна \(\frac{11(53+3)}2=308\).
Пусть \(a_1=2\), \(a_{n+1}=3a_n+4\). Найдите \(a_n\).
Подберите \(c\), чтобы \(a_{n+1}+c=3(a_n+c)\).
Нужно \(3c=4+c\), откуда \(c=2\). Тогда \(a_{n+1}+2=3(a_n+2)\).
\(a_1+2=4\), значит \(a_n+2=4\cdot3^{n-1}\), и \(a_n=4\cdot3^{n-1}-2\).
Пусть \(F_1=F_2=1\), \(F_{n+2}=F_{n+1}+F_n\). Докажите, что \(F_{n+3}\ge2F_n\).
Выразите \(F_{n+3}\) через \(F_{n+1}\) и \(F_n\).
\(F_{n+3}=F_{n+2}+F_{n+1}=F_n+2F_{n+1}\). Так как \(F_{n+1}\ge F_n\) для \(n\ge1\), получаем \(F_{n+3}\ge3F_n\), тем более \(F_{n+3}\ge2F_n\).
Последовательность \(a_n\) имеет первые члены \(2,5,10,17,26\). Предположим, что вторые разности постоянны. Найдите формулу \(a_n\).
Первые разности: \(3,5,7,9\).
Разности равны \(2n+1\) при переходе от \(a_n\) к \(a_{n+1}\). Это соответствует \(a_n=n^2+1\). Проверка: \(1^2+1=2\), \(2^2+1=5\), и далее.
Найдите \(\sum_{k=1}^{n}\frac{1}{(k+1)(k+3)}\).
Разложите дробь на \(\frac12\left(\frac1{k+1}-\frac1{k+3}\right)\).
\(\frac{1}{(k+1)(k+3)}=\frac12\left(\frac1{k+1}-\frac1{k+3}\right)\).
Сумма равна \(\frac12\left(\frac12+\frac13-\frac1{n+2}-\frac1{n+3}\right)\).
Пусть \(1
Обозначьте \(A=\sqrt[2^{n+1}]{a}\), \(B=\sqrt[2^{n+1}]{b}\).
Тогда \(B>A>1\), \(x_{n+1}=2^{n+1}(B-A)\), а \(x_n=2^n(B^2-A^2)=2^{n+1}(B-A)\frac{A+B}{2}\).
Так как \(\frac{A+B}{2}>1\), получаем \(x_n>x_{n+1}\).
Последовательность задана \(a_1=4\), \(a_{n+1}=5a_n+4\). Докажите, что \(a_n\) делится на \(4\) при всех \(n\).
Используйте индукцию.
База очевидна: \(4\mid a_1\). Если \(4\mid a_n\), то \(5a_n+4\) тоже делится на \(4\). Следовательно, \(4\mid a_{n+1}\).
Пусть \(a_1=2\), \(a_{n+1}=\frac{2a_n}{a_n+2}\). Найдите \(\frac1{a_n}\).
Перейдите к обратным величинам.
\(\frac1{a_{n+1}}=\frac{a_n+2}{2a_n}=\frac12+\frac1{a_n}\). Значит, \(\frac1{a_n}=\frac12+\frac{n-1}{2}=\frac n2\). Поэтому \(a_n=\frac2n\).
Сколько последовательностей \(a_1,\ldots,a_n\) натуральных чисел имеют минимальный член не больше \(4\) и \(|a_{i+1}-a_i|\le1\)?
Зафиксируйте разности и минимальный член.
Разностная последовательность имеет \(n-1\) членов, каждый из которых равен \(-1,0,1\), всего \(3^{n-1}\) вариантов.
Для каждой разностной последовательности все исходные последовательности получаются прибавлением одной и той же константы ко всем членам. Ровно по одной из них имеет минимум \(1,2,3,4\). Поэтому ответ \(4\cdot3^{n-1}\).
Для чисел Фибоначчи \(F_1=F_2=1\) докажите \(F_{n+1}F_{n-1}-F_n^2=(-1)^n\) для \(n\ge2\).
Проверьте базу и сделайте переход, используя \(F_{n+2}=F_{n+1}+F_n\).
База \(n=2\): \(F_3F_1-F_2^2=2\cdot1-1=1=(-1)^2\).
Если \(F_{n+1}F_{n-1}-F_n^2=(-1)^n\), то \(F_{n+2}F_n-F_{n+1}^2=(F_{n+1}+F_n)F_n-F_{n+1}^2=-(F_{n+1}F_{n-1}-F_n^2)=(-1)^{n+1}\).
Пусть \(0
Рассмотрите \(1-a_{n+1}\).
\(1-a_{n+1}=1-2a_n+a_n^2=(1-a_n)^2\). Если \(0 Кроме того, \(a_{n+1}-a_n=a_n(1-a_n)>0\). Поэтому последовательность возрастает.
Докажите, что \(\sum_{k=1}^{n}\frac1{k^2}<2\) для всех \(n\).
Для \(k\ge2\) сравните \(\frac1{k^2}\) с \(\frac1{k-1}-\frac1k\).
При \(k\ge2\), \(k^2>k(k-1)\), поэтому \(\frac1{k^2}<\frac1{k(k-1)}=\frac1{k-1}-\frac1k\).
Тогда сумма меньше \(1+\sum_{k=2}^{n}\left(\frac1{k-1}-\frac1k\right)=1+1-\frac1n<2\).
Последовательность задана \(a_1=1\), \(a_{n+1}=a_n^2+a_n\). Докажите, что \(a_n\) делится на \(a_1a_2\cdots a_{n-1}\) при \(n\ge2\).
Заметьте, что \(a_{n+1}=a_n(a_n+1)\).
Докажем сильнее: \(a_n\) делится на произведение всех предыдущих членов. База очевидна.
Если \(a_n\) делится на \(a_1\cdots a_{n-1}\), то \(a_{n+1}=a_n(a_n+1)\) делится на \(a_1\cdots a_{n-1}\cdot a_n\). Значит, утверждение верно по индукции.
Последовательность \(a_n\) имеет постоянную вторую разность \(6\), причём \(a_1=2\), \(a_2=9\). Найдите \(a_n\).
Если вторая разность равна \(6\), старший коэффициент квадратной формулы равен \(3\).
Пусть \(a_n=3n^2+bn+c\). Из \(a_1=2\): \(3+b+c=2\). Из \(a_2=9\): \(12+2b+c=9\).
Вычитая, получаем \(9+b=7\), значит \(b=-2\). Тогда \(c=1\). Ответ: \(a_n=3n^2-2n+1\).
В выпуклом \(n\)-угольнике последовательно проводят диагонали так, что каждая новая диагональ пересекает внутри многоугольника не более одной из ранее проведённых. Докажите, что можно провести не более \(2n-6\) диагоналей, и приведите конструкцию, где это число достигается.
Для оценки рассмотрите последнюю диагональ и разрежьте многоугольник на две части.
Конструкция: проведём диагонали \(A_2A_4,A_3A_5,\ldots,A_{n-2}A_n\), затем диагонали \(A_1A_3,A_1A_4,\ldots,A_1A_{n-1}\). Их всего \((n-3)+(n-3)=2n-6\), и порядок можно выбрать так, чтобы каждая новая пересекала не более одной старой.
Докажем оценку индукцией по \(n\). Для треугольника всё ясно. Пусть последняя диагональ — \(A_1A_k\). Она пересекла не более одной предыдущей диагонали \(d\). Все остальные диагонали лежат внутри одного из двух многоугольников: \(A_1A_2\ldots A_k\) или \(A_kA_{k+1}\ldots A_nA_1\). По предположению индукции их не больше \((2k-6)+(2(n+2-k)-6)=2n-8\). Добавляя последнюю диагональ и, возможно, \(d\), получаем не больше \(2n-6\).
Найдите все действительные \(t\), для которых \(t\,n(n+3)(n+6)\) является целым числом при любом натуральном \(n\).
Подставьте несколько малых \(n\), чтобы получить ограничение на \(t\).
Из условий для \(n=1,2,3\) получаем \(28t,80t,162t\in\mathbb Z\). Наибольший общий делитель чисел \(28,80,162\) равен \(2\). Следовательно, \(2t\in\mathbb Z\), то есть \(t=\frac{k}{2}\) для некоторого целого \(k\).
Обратно, \(n(n+3)(n+6)\) всегда чётно: если \(n\) чётно, это ясно, а если \(n\) нечётно, то \(n+3\) чётно. Поэтому каждое \(t=\frac{k}{2}\) подходит. Ответ: \(t=\frac{k}{2}\), \(k\in\mathbb Z\).
Назовём число прямоугольным, если оно равно \(m(m+1)\). Докажите, что каждое прямоугольное число можно представить как частное двух прямоугольных чисел.
Попробуйте умножить \(n(n+1)\) на \(\frac{(n+1)(n+2)}{(n+1)(n+2)}\).
Пусть дано число \(n(n+1)\). Тогда
\[n(n+1)=\frac{n(n+2)(n+1)^2}{(n+1)(n+2)}=\frac{(n^2+2n)(n^2+2n+1)}{(n+1)(n+2)}.\]
В числителе стоит произведение двух последовательных чисел \(n^2+2n\) и \(n^2+2n+1\), а в знаменателе — \((n+1)(n+2)\), тоже прямоугольное число. Значит, представление найдено.
Пусть \(a
Сложите подходящие кратные двух векторов, чтобы получить \((D,0)\) и \((0,D)\).
Обозначим \(u=(a,b-a)\), \(v=(b-a,-a)\). Тогда \(a u+(b-a)v=(a^2+(b-a)^2,0)=(D,0)\).
Также \((b-a)u-a v=(0,D)\). Поэтому разметка периодична при сдвигах на \((D,0)\) и \((0,D)\).
В фундаментальном квадрате \(D\times D\) число отмеченных клеток равно площади квадрата, делённой на площадь фундаментального параллелограмма решётки. Определитель векторов \(u,v\) равен \(-a^2-(b-a)^2=-D\), значит площадь фундаментального параллелограмма равна \(D\). Поэтому в квадрате площади \(D^2\) находится ровно \(D\) отмеченных клеток.
Сколько последовательностей \(a_1,\ldots,a_n\) натуральных чисел имеют хотя бы один член \(4\) или \(5\), а любые два соседних члена отличаются не больше чем на \(2\)?
Сначала посчитайте последовательности с минимальным членом не больше \(5\), затем вычтите лишние.
Зафиксируем разности \(b_i=a_{i+1}-a_i\). Каждая разность может быть \(-2,-1,0,1,2\), всего \(5^{n-1}\) вариантов.
Для каждой разностной последовательности ровно по одной исходной последовательности имеет минимум \(1,2,3,4,5\). Поэтому последовательностей с минимумом не больше \(5\) ровно \(5^n\).
Лишние среди них — те, где нет \(4\) и \(5\). Если минимум не больше \(5\) и при шаге не больше \(2\) последовательность содержит число больше \(5\) и число меньше \(4\), то она обязана пройти через \(4\) или \(5\). Значит, лишние состоят только из \(1,2,3\). Таких \(3^n\). Ответ: \(5^n-3^n\).
Пусть \(1
Положите \(A=\sqrt[3^{n+1}]{a}\), \(B=\sqrt[3^{n+1}]{b}\) и разложите \(B^3-A^3\).
Тогда \(B>A>1\), \(y_{n+1}=3^{n+1}(B-A)\), а \(y_n=3^n(B^3-A^3)=3^{n+1}(B-A)\frac{B^2+AB+A^2}{3}\).
Так как \(A,B>1\), среднее \(\frac{B^2+AB+A^2}{3}>1\). Значит, \(y_n>y_{n+1}\).
Даны шесть последовательных натуральных чисел. Докажите, что их можно обозначить \(a,b,c,d,e,f\) так, чтобы \(\frac a{b+c}+\frac d{e+f}=1\).
Запишите числа как \(n,n+1,\ldots,n+5\) и сделайте одинаковые знаменатели.
Возьмём \(a=n\), \(d=n+5\), \(b=n+1\), \(c=n+4\), \(e=n+2\), \(f=n+3\).
Тогда \(b+c=e+f=2n+5\), а \(a+d=2n+5\). Поэтому \(\frac a{b+c}+\frac d{e+f}=\frac{a+d}{2n+5}=1\).
Даны восемь последовательных натуральных чисел. Докажите, что шесть из них можно обозначить \(a,b,c,d,e,f\) так, чтобы \(\frac a{b+c}+\frac d{e+f}=1\).
Возьмите первые шесть чисел и примените симметричную конструкцию.
Пусть среди данных есть \(n,n+1,\ldots,n+7\). Возьмём первые шесть: \(n,\ldots,n+5\).
Как в предыдущей конструкции, положим \(a=n\), \(d=n+5\), \(b=n+1\), \(c=n+4\), \(e=n+2\), \(f=n+3\). Тогда оба знаменателя равны \(2n+5\), а \(a+d=2n+5\). Поэтому сумма дробей равна \(1\).
Лестницы