Тема АЛГЕБРА

Последовательности и прогрессии → .04 Рекуррентные соотношения

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела алгебра

Разделы подтемы Последовательности и прогрессии

Арифметическая прогрессия

Геометрическая прогрессия

Комбинация арифметической и геометрической прогрессий

Рекуррентные соотношения

Периодичность и зацикливание

Последовательности нестандартного вида

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 41#94738Максимум баллов за задание: 7

Банк города Бат выпускает монеты с буквой $H$ на одной стороне и буквой $T$ на другой стороне. Гарри разложил $n$ таких монет в ряд слева направо. Он последовательно производит следующую операцию: если в ряду ровно $k >0$ монет лежат буквой $H$ кверху, то он переворачивает $k$ -ю слева монету; иначе все монеты лежат буквой $T$ кверху, и он останавливается. Например, если $n =3$ и процесс начинается с конфигурации $THT$ , то последовательность операций выглядит как $THT → HHT → HTT → TTT,$ то есть процесс остановился после трех операций.

1.: Докажите, что при любой начальной конфигурации процесс остановится после конечного числа операций
2.: Для каждой начальной конфигурации $C$ через $L(C)$ обозначим количество операций, после которых процесс остановится. Например, $L(THT) =3$ и $L (TT T)= 0$ . Найдите среднее арифметическое значений $L(C),$ когда $C$ пробегает все $n 2$ возможных начальных конфигураций.играющих может обеспечить себе победу, как бы ни играл его соперник?

Источники: IMO - 2019, Problem 5

Показать ответ и решение

$1.$ Посмотрим, что происходит с конфигурациями, в зависимости от того, как расположены первая и последняя монеты

Если первая лежит буквой $H$ кверху, то последние $n− 1$ монет преобразуются по аналогичным правилам так, словно первой монеты нет (пока все не превратятся в $T$ ). После преобразований последних $k− 1$ монет последняя монета переворачивается.
Если последняя монета лежит буквой $T$ кверху, то она никогда не будет перевернута, а первые $n− 1$ монет преобразуются так, будто последней монеты нет.
Если конфигурация начинается монетой, повернутой кверху буквой $T$ и заканчивается монетой, повернутой кверху буквой $H,$ то средние $n − 2$ монеты преобразуются по правилам так, будто других монет нет, пока все не повернутся буквой $T.$ После этого сначала по порядку переворачиваются монеты $1,2,...,n − 1,$ а затем по порядку переворачиваются монеты $n,n− 1,...,1.$

Таким образом, рассмотрены все возможные конфигурации и очевидно, что для $n= 1$ и $n= 0$ процесс конечен. По индукции получаем, что он конечен для любого натурального $n.$

$2.$ Определим $E (n), AB$ где $A,B ∈ {H,T,∗}$ — среднее число ходов преобразования конфигурации длиной $n,$ которые начинаются на $A,$ если $A$ не является $∗$ и оканчиваются на $B,$ если $B$ не является $∗.$ Тогда при $n≥ 2$ имеем

$E (n)= E(n− 1)+1; H ∗$
$E∗T(n)= E(n− 1);$
$EHT (n) =E (n− 2)+ 1,$ исходя из замечаний для $H∗$ и $∗T ;$
$ETH (n) =E (n− 2)+ 2n − 1.$

Таким образом, выполняются равенства

E = 1(E (n)+ E (n)) H∗ 2 HH HT

Тогда получаем

EHH =2E(n− 1)− E (n − 2)+ 1

и аналогичным образом

ETT = 2E(n− 1)− E(n− 2)− 1

Теперь получаем реккурентное выражение для $E (n)$

1 n E(n)= 4(EHT(n)+ EHT(n)+EHH + ETT)= E(n− 1)+ 2

Поскольку, мы знаем, что $E (0)= 0$ и $E(1) = 12,$ то индукцией по $n$ получается, что $E (n)= 14n(n+ 1).$

Ответ:

$1n(n+ 1) 4$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 42#81696Максимум баллов за задание: 7

Существует ли такая бесконечная возрастающая последовательность $a ,a,a ,... 1 2 3$ натуральных чисел, что сумма любых двух различных членов последовательности взаимно проста с суммой любых трёх различных членов последовательности?

Источники: Всеросс., 2017, ЗЭ, 9.4(см. olympiads.mccme.ru)

Показать ответ и решение

Построим пример такой последовательности. Положим $a = 1,a = 7,a =(3a )!+ 1. 1 2 n+1 n$ Для того, чтобы показать, что она удовлетворяет требованиям, нам придётся эти требования несколько усилить. Будем говорить, что пара (тройка) чисел хорошая, если все её элементы, отличные от единицы, различны (а единица может встретиться в ней несколько раз). Докажем следующее утверждение, из которого будет следовать, что построенная последовательность — требуемая.

Пусть $(ai,aj)$ и $(ap,aq,ar)$ — хорошие пара и тройка элементов последовательности. Тогда НОД $(ai+aj,ap+aq+ ar)=$ НОД $(ai+ aj,ap+ aq− ar)= 1.$

Доказательство проведём индукцией по наибольшему индексу $m$ среди $i,j,p,q$ и $r.$ Если $m = 1,$ утверждение тривиально. Для перехода предположим, что $m >1.$ Число $am$ лежит либо только в паре $(ai,aj),$ либо только в тройке $(ap,aq,ar),$ либо в обеих.

Случай $1.$ Пусть $am$ — только элемент пары; скажем, $am = aj.$ Тогда, поскольку $0 <|ap+aq± ar|≤3am−1,$ число $am − 1 =(3am−1)!$ делится на $|ap +aq± ar|,$ то есть НОД $(ai+ am,ap +aq± ar)=$ НОД $((ai+ 1)+(am − 1),ap+ aq± ar)=$ НОД $(ai+ a1,ap +aq± ar) =1$ по предположению индукции.

Случай $2.$ Пусть $am$ — только элемент тройки; скажем, $am =aq.$ Аналогично, $am − 1$ делится на $ai+ aj,$ так что НОД $(ai+ aj,ap+ am ±ar)=$ НОД $(ai+ aj,ap+ a1±ar)= 1$ по предположению индукции.

Случай $3.$ Пусть $am$ — элемент и пары, и тройки; скажем, $am =aj = aq.$ Тогда $am− 1$ делится на $ap− ai± ar,$ так что НОД $(ai+ am,ap+ am± ar)=$ НОД $(ai+am,(ap+ am ± ar)− (ai+ am))=$ НОД $(ai+ am,ap − ai± ar)=$ НОД $(ai+a1,ap − ai± ar)= 1$ по предположению индукции. Переход индукции доказан.

Ответ:

Да, существует

Ошибка.
Попробуйте повторить позже

Задача 43#40087Максимум баллов за задание: 7

Последовательность $(a ) n$ такова, что $a = n2 n$ при $1≤ n ≤5$ и при всех натуральных $n$ выполнено равенство $a +a = a + a . n+5 n+1 n+4 n$ Найдите $a2015.$

Источники: ММО-2015, 11.1, автор - С.Б.Гашков, (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1!

Какие-то странные условия, попробуем получить из них что-то хорошее. Если вы знаете что-то про начальные члены последовательности, а еще про то, как они соотносятся с предыдущими, здорово бы было как-то выразить большие члены через члены от 1 до 5. Получить на них какое-то правило.

Подсказка 2!

Давайте напишем. a(n+5) +a(n+1) = a(n+4) + a(n). Заметим, что индексы в обеих частях отличаются на 4. Напишем a6+a2 = a5+a1 = чему-то, что мы уже знаем! Так, а может не только для а6+а2 мы знаем это равенство?

Подсказка 3!

Да, для всех чисел, отличающихся на 4 по номеру, мы поняли их сумму. Теперь вспомним, что мы ищем 2015. К сожалению, 2019 или 2011 мы не знаем. Попробуем получить еще что-то из условия с равенством. Попробуйте сделать так, чтобы и в левой, и в правой части оказалось одинаковое число.

Подсказка 4!

Да, подставим а(n+8) + а(n+4) = a(n+4)+an. Осталось сделать выводы и применить наши полученные знания :)

Показать ответ и решение

Из условия следует

2 2 an+4+ an = an+3 +an−1 = ...= a6+ a2 =a5 +a1 = 5 + 1 =26

А также

an+8+ an+4 =an+4+ an =⇒ an+8 = an

То есть значение $an$ зависит только от остатка $n$ по модулю $8,$ отсюда

a2015 =a7 = 26− a3 = 26 − 32 = 17

Ответ:

$17$

Ошибка.
Попробуйте повторить позже

Задача 44#97887Максимум баллов за задание: 7

Последовательность чисел задана следующим образом: $a = 0,a = 1 1 2$ и $a = 4(a − a ) n+1 n n−1$ при $n ≥ 2.$ Найдите наименьший положительный член последовательности, кратный $2014.$ В ответе укажите номер этого члена.

Подсказки к задаче

Подсказка 1

Рассмотрите разность элемента и прыдудущего, умноженного на 2.

Подсказка 2

Оказывается, что разность из подсказки 1 всегда увеличивается вдвое! Значит, мы можем выразить такие разности через степень двойки! Но как вернуться к нашим элементам?

Подсказка 3

Выразите n-ый член последовательности через такие разности с помощью последовательного "спуска"!

Подсказка 4

n-ый член последовательности равен (n-1)*2^(n-2).

Показать ответ и решение

Заметим, что

an+1− 2an = 2an − 4an−1 = 2(an− 2an−1)

Обозначим $bn = an+1− 2an$ , тогда $b1 = 1$ и $bn+1 = 2bn$ , следовательно, $bn = 2n−1$ . Таким образом,

an = bn−1+ 2an−1 = bn−1+ 2bn−2 +4an−2 =

⋅⋅⋅= b + 2b + ...+ 2n−1b + 2na =(n− 1)2n−2 n−1 n−2 1 1

Если это число кратно 2014 , то $(n− 1)$ кратно 1007 , т.е. $n= 1008$ .

Ответ: 1008

Ошибка.
Попробуйте повторить позже

Задача 45#99352Максимум баллов за задание: 7

По данному натуральному числу $a 0$ строится последовательность $a n$ следующим образом: $a = a2− 5, n+1 n$ если $a n$ нечётно, и $an, 2$ если $an$ чётно. Докажите, что при любом нечётном $a0 >5$ в последовательности $an$ встретятся сколь угодно большие числа.

Источники: Всеросс., 2000, РЭ, 10.6(см. math.ru)

Показать доказательство

Пусть число $a = 2k+ 1 n$ нечетно и больше $5.$ Тогда имеем

2 2 an+1 = (2k+1) − 5= 4k + 4k− 4

2 an+2 = 2k +2k− 2

a = k2+k − 1 n+3

При этом $an+3$ нечетно и, поскольку $k > 2,$ то $an+3 =k2+ k− 1> 2k+1 =an.$ Таким образом, $a0 <a3 < a6 < ...< a3m,$ поэтому при любом $n$ имеем $a3n ≥ n.$

Ошибка.
Попробуйте повторить позже

Задача 46#96385Максимум баллов за задание: 7

Последовательность $a, 0$ $a, 1$ $a , 2$ …удовлетворяет условию

1 am+n +am−n = 2(a2m + a2n)

для всех целых неотрицательных чисел $m≥ n.$ Известно, что $a1 = 1.$ Найдите $an.$

Источники: Всеросс., 1995, РЭ, 11.6(см. math.ru)

Подсказки к задаче

Подсказка 1

Для начала хорошо бы было понять ответ. Как это сделать? Нужно подставлять какие-то конкретные значения, после этого вычислить несколько первых членов, а затем попытаться угадать ответ. Как после этого его доказать?

Подсказка 2

На самом деле a_n = n^2. Попробуйте доказать это по индукции. Как можно сделать переход?

Подсказка 3

Сделайте переход от n = k - 1, n = k к n = k + 1, не забудьте проверить базу. Какой она должна быть?

Показать ответ и решение

Полагая $m = n,$ находим $a =0. 0$ Полагая $n= 0,$ получим $a + a = 1 (a +a ). m m 2 2m 0$ Отсюда

a2m = 4am (1)

Пусть $m= n+ 2.$ Тогда $a2n+2 +a2 = 1(a2n+4 +a2n), 2$ и так как в силу $(1)$ $a2n+4 = 4an+2$ и $a2n = 4an,$ то окончательно получаем:

a2n+2+ a2 = 2(an+2+ an) (2)

С другой стороны, в силу $(1)$ и условия $a1 = 1,$ имеем:

a +a =4(a + a)= 4(a +1) (3) 2n+2 2 n+1 1 n+1

Сравнивая $(2)$ и $(3),$ заключаем, что последовательность $(an)$ удовлетворяет рекуррентному соотношению

an+2 = 2an+1 − an+ 2

и начальным условиям $a0 = 0,a1 =1.$

Вычислив несколько первых членов последовательности: $a2 = 4,a3 = 9,a4 =16,$ приходим к предположению, что при всех $n ≥0,an = n2.$ Доказательство проведем по индукции. При $n =0$ и $n =1$ утверждение верно. Пусть оно верно при $n= k− 1$ и $n =k(k≥ 1).$ Тогда