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

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

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

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

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

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

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

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

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

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

Последовательность чисел $a ,a,...,a 1 2 2024$ такова, что $a =a 1 2024$ и $a + a − 1 =a2 n n+1 n+1$ при всех целых $n$ от 1 до 2023. Найдите $a2000.$

Источники: Бельчонок - 2024, вариант 4, 10.1 (см. dovuz.sfu-kras.ru)

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

Подсказка 1

Исследуйте последовательность на монотонность. Для этого попробуйте преобразовать представленное в условии равенство, связывающее n-ый и (n+1)-ый члены.

Подсказка 2

Выделите из этого равенства полный квадрат.

Подсказка 3

Вспомните, что по условию a₁ = a₂₀₂₄.

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

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

2 an− an+1 = (an+1− 1)≥ 0

Но тогда

a1 ≥ a2 ≥...≥a2024

Так как $a1 = a2024,$ то все неравенства обращаются в равенства, следовательно, все $ai$ равны 1.

Ответ: 1

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

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

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

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

Последовательность $x n$ задана рекуррентным соотношением $x = x + {x } n+1 n n$ и начальным условием $x = 1-. 0 67$ Найдите $[x66000].$

( $[a]$ — целая часть числа $a,$ ${a}$ — дробная часть числа $a).$

Источники: ИТМО-2023, 11.7 (см. olymp.itmo.ru)

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

Подсказка 1

Дробная часть, целая часть, ну и ну… А x_(n+1) = x_n + {x_n}, то чему равно x_(n+1) если использовать только дробные и целые части числа, а не само число?

Подсказка 2

Верно, x_(n+1) = [x_n] + 2*{x_n}. Значит, если смотреть только на дробную часть, то нетрудно доказать, что она будет равна дроби со знаменателем 67, а также, что числители дроби будут являться циклом, если рассмотреть последовательность целиком(как минимум, потому, что числитель n-ого члена последовательности сравним по модулю с 2^n, а остатки у 2^n по модулю 67 образуют цикл). А что можно тогда сказать, про члены, разность индексов которых равна 1 циклу?

Подсказка 3

Верно, во-первых, что(если длина цикла k и мы берем i-ый элемент), то {x_(i+k)} = {x_i}. Но тогда из этого следует, что x {x_(i+k)} - {x_i} = {x_(i+2k)} - {x_(i+k)}, так как {x_(i+2k)} = {x_(i+k)}. При этом, так как нам неважно, какая разность была между {x_(i+k)} и {x_i}, для вычисления x_(i+k+1), так как влияет только дробная часть, то будет выполнено, что
[x_(I+k)] - [x_i] = [x_(I+2k)] - [x_(I+k)]. Значит, x_(i+k) - x_i = x_(i+2k) - x_(i+k). Значит, разность между соответствующими элементами соседних циклов - константа. Что это дает?

Подсказка 4

Верно, что можно просто найти эту разность(и цикл) и понять, в каком по порядке циклу лежит x_66000 и чему он соответствует в первом цикле и мы сможем в явном виде найти x_66000. Как это сделать? Начать писать все x_i, начиная с нулевого, пока в числителе дробной части не будет 0. А значит, осталось перебрать 66 значений(10 минут) и найти нужные значения!

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

Пусть оказалось так, что ${x }= {x} k+i i$ для некоторого $k >0$ . Тогда выполнено $x − x = x − x k+i i 2k+i k+i$ . Действительно, на каждой следующей итерации мы учитываем только дробную часть исходного числа (целая же часть определяет только нашу “точку старта”). Поэтому выполнено равенство ${x2k+i}= {xk+i}$ . Также отсюда будет следовать $[xk+i]− [xi]= [x2k+i]− [xk+i]$ , то есть наш сдвиг по целой части будет таким же. Нетрудно видеть, что оба условия вместе дадут $xk+i− xi = x2k+i− xk+i$ (если известно ${xk+i}= {xi}$ ). Далее остаётся только найти цикл нужной длины. Оказывается, что $1 x66 = 337$ и выполнено ${x0}= {x66}$ , мы получили цикл, получаем

[x66000]= [x0+66⋅1000]= 1000 ⋅([x66− x0])= 1000⋅33= 33000

Замечание. Как же найти такой цикл, не считая вручную все $66$ значений до него? Во-первых, уже $66 1- {x33}= 67 = 1− 67$ , что явно нам намекает, когда мы снова встретим единицу (по сути мы каждый раз умножаем дробную часть на 2, поэтому можно сразу сделать вывод, что на $66$ шаге, поскольку за столько же шагов результат возведётся в квадрат по модулю $67$ ). Во-вторых, уже на шестом шаге мы получим $3- {x6}= 1− 67$ , поэтому далее можно попробовать идти по кратным шести индексам, чтобы быстрее добраться до $66$ . Почему вообще всё это имеет смысл? Потому что $66000$ делится и на 6, и на 33, и на 66 — именно в них мы и ждём больше всего увидеть цикл, чтобы задача после этого решилась быстро и легко.

Ответ: 33000

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

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

Последовательность натуральных чисел ${a} n$ построена по следующему правилу:

3 an+1 = an +1999 при n = 1,2,....

Докажите, что в этой последовательности не больше одного точного квадрата. Для тех, кто не жил в $1999$ -м году сообщаем, что этот год был простым.

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

Подсказка 1

Попробуем рассмотреть остатки n-го и (n+1)-го членов по какому-нибудь модулю. Как они взаимосвязаны?

Подсказка 2

Давайте рассмотрим остатки по модулю 4, так как идёт речь про квадраты. Тогда все члены, начиная с третьего, могут иметь только остатки 2 и 3, и не могут являться квадратами, так как по модулю 4 квадраты имеют остатки 0 и 1. А могут ли сразу два первых члена быть квадратами?

Подсказка 3

Пусть первый член являться квадратом числа a, а второй является квадратом числа b. Что тогда следует из исходной рекурренты?

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

Рассмотрим взаимосвязь остатков $(a ,a ) n n+1$ по модулю $4$


$an$	0	1	2	3

$an+1$	3	0	3	2

Как известно, квадраты дают только остатки $0,1,$ однако при любом остатке $a1,$ остаток $a2$ будет какой-то из ${0,2,3},$ откуда остатки $a3,a4,...$ принимают значения из ${2,3},$ то есть $a3,a4,...$ не могут быть квадратами. Остаётся показать, что сразу оба $a1$ и $a2$ также не могут ими являться. Итак, пусть $a1 = a2,a2 = b2,$ тогда

b2 = a6 +1999 ⇐⇒ 1999= (b− a3)(b+ a3) ⇐ ⇒ b− a3 = 1,b+ a3 = 1999

Последний вывод следует из того, что $1999$ простое. Но тогда

2a3 =1998 ⇐⇒ a3 = 999

что невозможно, значит, в последовательности действительно не больше одного полного квадрата.

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

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

Последовательность натуральных чисел ${a} n$ удовлетворяет условию

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

при всех $n≥ 1.$ Известно, что $a1999$ делится на $2000.$ Найдите наименьшее $n ≥2,$ при котором $an$ делится на $2000.$

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

Подсказка 1

Попробуйте угадать какой-нибудь ответ, а для него уже вычислить требуемое n. Попробуйте теперь вычислить общий вид последовательности. Как это можно сделать?

Подсказка 2

Пусть a_n = 2n - 2 + b_n. Пользуясь тем, что a_n кратно 2000, поймите как может быть устроено b_n. Как после этого найти минимальное n, при котором a_n кратно 2000.

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

Заметим, что $a = 2n − 2 n$ — подходит. Пусть $a =2n− 2+ b. n n$ Если подставить это в равенство, то мы получим $(n − 1)b =(n+ 1)b , n+1 n$ то есть

n n n− 1 bn = n-− 2bn−1 = n−-2 ⋅n−-3bn−2 =

= nn−-2 ⋅ nn-−− 1 3 ⋅ nn−−-24 ⋅...⋅ 53 ⋅ 42 ⋅ 31b2 = n(n−2-1)b2

Значит, $an = 2n − 2 + n(n2−1)c,$ где $c$ — целочисленная константа.

По условию $a1999 ≡ 1001c− 4 (mod 2000).$ Значит, $1001c− 4≡0 (mod 2000).$ Это сравнение имеет не более одного решения по модулю $2000.$ Заметим, что это решение равно $4.$ Значит, $an ≡ 2n− 2+2n(n− 1)=2n2− 2 (mod 2000).$ Нам надо найти минимальное $n≥ 2$ такое, что $n2− 1= (n+ 1)(n− 1)$ кратно $2000.$ НОД скобочек может быть не более $2,$ значит одна из скобок делится на $125.$ Это возможно, если $n= 124,126,249,....$ Перебором получаем, что $n= 249$ — минимальное подходящее.

Ответ:

$249$

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

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

Последовательность чисел $a ,a ,... 1 2$ задана условиями $a =1, 1$ $a = 143 2$ и

a1+a2-+...+-an an+1 = 5⋅ n

при всех $n ≥2.$ Докажите, что все члены последовательности — целые числа.

Источники: Всеросс., 2012, РЭ, 10.3(см. olympiads.mccme.ru)

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

Положим $S = a + a +...+a , n 1 2 n$ тогда $a =S − S . n+1 n+1 n$ Достаточно показать, что все числа $S n$ – целые. Заметим, что $S1 = 1,S2 = 144,$ и $5Sn- Sn+1 − Sn = n ,$ то есть $n+5 Sn+1 = n Sn.$ Значит, при $n≥ 2$

(n+ 5)(n+ 4)...⋅7 (n+ 5)(n+ 4)(n+ 3)(n+ 2)(n+ 1) Sn+1 =--n(n−-1)...⋅2--⋅S2 =--------6⋅5⋅4⋅3⋅2---------⋅144=

= (n-+5)(n-+4)(n-+3)(n-+2)(n+1)- 5

Так как одно из чисел $n+ 5,n +4,n+ 3,n +2,n+ 1$ делится на $5,$ то при $n ≥2$ число $Sn+1$ – целое.

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

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

Дана последовательность $0< a < a <a < ...<a < a 0 1 2 22 23$ . При всех $0 <n ≤23$ выполнено условие

∘ -2----4--- an =2 an−1− an−1.

Докажите, что $−6 a0 < 10 .$

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

Распишем $a : n$

∘ 2-----4--- ∘ ----2-- an = 2 an−1 − an−1 = 2an− 1 1− an−1.

Из последнего выражение следует, что вся последовательность меньше либо равна $1.$ Тогда каждый член последовательности можно представить в виде тригонометрических функций. Пусть $a0 =sin φ,$ где $π φ∈ [0;2].$ Тогда

∘ ----- a1 = 2a0 1− a20 =2sin φcosφ = sin2φ.

То есть следующий член последовательности это синус от удвоенного аргумента предыдущего члена. Это будет верно до тех пор, пока у нас последовательность возрастает. Нужно, чтобы $a23$ был последним числом, после которого значение уменьшаться. Оценим аргумент, при котором это возможно.

Пусть $a22 = sinα,a23 = sin2α.$ Понятно, что

a23 > a22 ⇒ 2sinαcosα> sinα ⇒ cosα > 12

Тогда $α$ может быть таким: $π4 ≤α ≤ π3.$ Тогда у нас есть такое ограничение: $222φ< π2,$ т.к. у $a23$ должен быть принадлежать $[π2;23π).$ Следовательно,

222φ< π ⇒ φ< -π-< -1- 2 222 106

Используя неравенство $sinx≥ x$ при $x≤ 1$ получаем, что

-π- -π- -1- a0 = sinφ < sin222 ≤ 222 < 106

Курсы

Всё необходимое для достижения цели

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

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

Последовательность чисел ${a } n$ такова, что

an+1+1- a1 =1,a12 =2,an+2 = an

для всех натуральных $n$ от $1$ до $10.$ Найдите $a4.$

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

Подсказка 1

Что нам дано в условии: есть 12 чисел а₁, ...а₁₂, первое и последнее известны, а также есть 10 соотношений, их связывающие (для n от 1 до 10). По сути есть система из 10 уравнений с 10 неизвестными, и нам обещают, что она разрешима единственным образом. Что самое простое и естественное хочется сделать, когда перед нами куча несложных уравнений с кучей неизвестных?

Подсказка 2

Конечно, для упрощения системы хочется начать выражать неизвестные друг через друга! Зачем нам думать о всех 10 неизвестных, если можно уменьшить их количество?

Подсказка 3

Например, а₃ = (а₂+1)/а₁. То есть а₃ = a₂+1, и а₃ дальше в нашей системе уже фигурировать не будет. Попробуйте так же выразить несколько следующих членов последовательности, может, что-нибудь красивое получится!

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

Выпишем формулы для первых нескольких членов

a2+-1 a3+-1 a2+-2 2- a3 = a1 = a2+ 1, a4 = a2 = a2 = a2 + 1

a2+2 2- a5 = a4+1-=-a2-+-1= 2-, a6 = a5+-1=-a2-+1 = 1=a1, a7 = 1+1-=a2 a3 a2+ 1 a2 a4 2a2-+1 2a2-

Отсюда $an+5 = an,n ∈{1,...7},$ тогда $a2 = a12 = 2,$ то есть $2+a2 a4 =-a2--=4.$

Ответ:

$2$

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

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

Последовательность $a n$ определена условиями $a = 0,01 1$ и $(n+ 2)a = na n n+1$ для $n = 1,2,...,99.$ Найдите сумму $a +a + ...+ a . 1 2 100$

Источники: Миссия выполнима-2022, 11.5 (см. mission.fa.ru)

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

Подсказка 1

Нам нужно найти сумму а-шек, значит, достаточно получить такую сумму, чтобы коэффициенты при каждом a_i были одинаковыми. При этом мы видим, что если у нас есть равенство 3a₁ = a₂, 4a₂ = 2a₃, то сложив эти два неравенства, после приведения подобных мы получим 3a₁ + 3a₂ = 2a₃, и мы получаем сумму первых двух чисел с одинаковыми коэффициентами. Можно ли так сделать для суммы первых скольких-то членов? А скольких?

Подсказка 2

Верно, мы можем просуммировать так все равенства и получить, что 3(a_1 + … + a_99) = 99a_100, то есть (a_1 + … + a_99) = 33a_100. Значит, то, что мы ищем - это 34 a_100. Ну а это уже легко найти, потому что есть рекуррента. Найдите a_100 и запишите ответ.

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

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

3a1 =a2,4a2 =2a3,5a3 = 3a4,...,101a99 = 99a100,

приведя подобные члены и сократив на $3,$ получим $a1+ a2+ a3+...+a99 = 33a100.$ Поэтому искомая сумма $S =34a100.$ А поскольку

101 101- 100- 101⋅100⋅...⋅4⋅3 101⋅100- a100 = 99 a99 = 99 ⋅98 a98 = ...= 99 ⋅98...⋅2⋅1 a1 = 2 a1 = 50.5,

то $S = 34⋅50.5= 1717.$

Ответ: 1717

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

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

Члены последовательности $a n$ удовлетворяют соотношению:

-2-- an+2 = an− an+1 ,a1 = 8,a2 =19

Найти $n,$ для которого $an = 0.$

Источники: Росатом-2022, московский вариант, 11.3 (см. olymp.mephi.ru)

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

Подсказка 1

Рассмотрим момент, когда появился нулевой член последовательности. Что случается с произведением соседних членов, когда появляется ноль?

Подсказка 2

Рассмотрите последовательность произведений соседних членов. Какому соотношению она удовлетворяет? Как найти ноль?

Подсказка 3

Домножьте равенство, данное в условии, на знаменатель. Какой вид имеет общий член новой последовательности? Найдите ноль)

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

По условию $a,a ⁄= 0. 1 2$ Элементы последовательности определены пока $a ⁄= 0. n+1$ Для остальных номеров члены последовательности не определены.

Пусть $an+1 ⁄=0,an+2 = 0.$ Тогда для всех $k ≤n ⇒ ak+1ak− 2.$ Последовательность $bk = ak+1ak$ удовлетворяет соотношению $bk+1 = bk − 2$ и представляет собой арифметическую прогрессию с разностью $d= −2$ и первым членом $b1 =a2a1 = 8⋅19=152.$ Общей её член $bk = b1− 2(k− 1)$ равен нулю, если

2(k − 1)= 152 ⇒ k= 77⇒ b77 =a77⋅a78 =0 ⇒ a78 = 0

Ответ:

$78$

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

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

Последовательность ${b } n$ задана условиями $b =1,b = 22,b = 333 1 2 3$ и

bn+2+-bn+1-+1 bn+3 = bn

для любого натурального $n.$ Найдите $b2025.$

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

bn+2+bn+1+1-+b + 1 bn+4 = bn+3+-bn+2-+1 =----bn-------n+2---= bn+1 bn+1

= bn+2+bn+1+-1+-bn-(bn+2+-1)-= bnbn+1

bn+2 (1+ bn)+bn+1+ bn +1 = --------bnbn+1---------=

= bn+2(1+bn)+-bn+2bn−1= bnbn+1

= bn+2(1+-bn-+bn−1)= bn+2bn+1bn−-2= bnbn+1 bnbn+1

= bn+2bn−2 bn

Тогда

bn+4bn = bn+2bn−2,bn+2bn−2 = bnbn−4

Отсюда

bn+4 = bn−4

В итоге

b2025 = b1+8⋅253 = b1 = 1

Ответ: 1

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

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

Последовательность $(x ) n$ определена как $x =3,x = 4 0 1$ и

2 xn+1 = xn−1− nxn

при любом $n ∈ℕ.$ Найдите общий вид $x . n$

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

Если посчитать $x 2$ и $x , 3$ то сразу возникнет предположение, что $x = n +3. n$ Докажем его по индукции:

База для $n= 0$ и $n= 1$ следует из условия.

Пусть $xn−1 =n +2$ и $xn =n +3,$ тогда $2 xn+1 =(n+ 2) − n(n+ 3)=n +4,$ доказали.

Ответ:

$x =n +3 n$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

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

Последовательность $(x ), n$ заданная первыми членами $x = a 0$ и $x = b, 1$ а также рекуррентным соотношением

1( -1) xn+1 = 2 xn−1+ xn

является периодической. Докажите, что $ab= 1.$

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

Домножим рекуррентное соотношение из условия на $x n$ и получим:

2xnxn+1 = xn−1xn+ 1

что равносильно:

2(xnxn+1− 1)= xn−1xn − 1

Определим последовательность ${yn}$ по правилу $yn = xn−1xn− 1$ при $n∈ ℕ.$ Она является геометрической прогрессией так как $yn+1 = yn∕2.$ Если последовательность ${xn}$ периодическая, то таковой является и ${yn}.$ Понятно, что $yn = ny1−1, 2$ то есть $yn$ будет периодической лишь когда $yn = 0$ для всех $n ∈ℕ.$ Следовательно,

ab= x0x1 =y1+ 1= 1

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

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

Рассмотрим последовательность $a ,a ,...,a, 0 1 n$ в которой $a = 1 0 2$ и

a2 ak = ak−1 +-k−n1

при всех $k =1,2,...,n.$ Докажите, что

1− 1 <an <1 n

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

Перепишем рекуррентное соотношение в следующем виде:

1 1 n 1 1 ak =------a2k−1= ak−1(n+-ak−1) =ak−1 −n-+ak−1 ak−1+ n

Следовательно,

--1- -1 ---1--- ak−1 −ak = n+ ak−1 (1)

для $k= 1,2,...,n.$

Понятно, что последовательность $ak$ возрастает. Значит,

an > an−1 > ...> a0 = 1 2

Из равенства $(1)$ следует:

-1--− 1-< 1 ak− 1 ak n

для $k= 1,2,...,n.$

Если просуммировать все такие неравенства, то получим:

1 1 a0 − an <1

или

1-> -1− 1= 2− 1= 1 an a0

То есть, $an < 1.$ Поскольку $an <1,$ и $ak$ возрастает, $a0 < ak ≤ an < 1$ для $k =1,2,...,n.$

Также из $(1)$ следует:

-1--− 1-= ---1---> --1- ak−1 ak n +ak−1 n +1

для $k= 1,2,...,n.$

Снова просуммируем все полученные неравенства и получим:

-1 -1 -n-- a0 −an > n+ 1

или

1 1 n n+ 2 an < a0-− n+-1 = n+-1

Таким образом,

an > n+-1= 1− -1--> 1− 1 n+ 2 n+ 2 n

что и требовалось.

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

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

Последовательность чисел $a ,a , 1 2$ …, $a 2022$ такова, что

3 3 an− ak ≥ n − k

для любых $n$ и $k$ таких, что $1 ≤n ≤2022$ и $1≤ k≤ 2022$ . При этом $a1011 =0.$ Какие значения может принимать $a2022$ ?

Источники: ВСОШ, РЭ, 2022, 9.6 и 11.6 (см. olympiads.mccme.ru)

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

Подсказка 1:

Дано только лишь неравенство, но при этом требуется вычислить значение одного из членов. Единственный способ найти его при таком раскладе — зажать между каким-то числом. То есть доказать, что, с одной стороны, оно не больше некоторого числа x, а с другой стороны, не меньше этого же числа x. Отсюда будет следовать, что оно равно x.

Подсказка 2:

По всей видимости, вместо одного из индексов нужно подставить 2022. Но что подставить вместо второго, чтобы реализовать первую подсказку? В условии дано значение 1011-го члена. Почему бы не подставить 1011 вместо второго индекса?

Подсказка 3:

Учтите, подставить эти индексы можно двумя разными способами.

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

Записывая условие при $n =2022,$ $k= 1011$ и при $n =1011,$ $k= 2022,$ получаем

3 3 a2022 = a2022− a1011 ≥2022 − 1011

−a = a − a ≥ 10113− 20223, 2022 1011 2022

то есть $a2022 ≥ 20223 − 10113 ≥a2022.$ Отсюда и следует ответ.

Ответ:

3 3 3 a2022 =2022 − 1011 = 7⋅1011

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

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

Последовательность целых чисел $a n$ задается следующим образом:

2 an+1 =an − an+ 1,a1 =100.

Докажите, что любые два различных члена последовательности взаимно просты.

Источники: БИБН - 2021, 11.3 (см. www.unn.ru)

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

Подсказка 1

Пупупу, нужно доказать взаимную простоту двух чисел… Попробуйте для начала взять первый и второй члены последовательности и посмотреть, какие у них могут быть общие множители и как они отличаются.

Подсказка 2

Можно посмотреть остаток любого члена последовательности по модулю предыдущего... и тут он оказывается равным единице! А что это значит?

Подсказка 3

А это значит, что единица должна делиться на потенциальный общий множитель, ведь мы имеем равенство по типу a₂ = a₁ * k + 1. Но ведь 1 делится только на 1, так что числа взаимнопросты! Теперь как-то надо обобщить это на все члены последовательности...

Подсказка 4

Ага, можно же воспользоваться индукцией!

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

Пусть $a n$ и $a n+m$ — два произвольных члена последовательности $(n,m ∈ℕ)$ . Докажем по индукции, что

an+m − an ⋅Nnm =1,

где $Nnm ∈ ℕ,$ то есть что $an+m− 1$ делится нацело на $an$ , а в терминах сравнения по модулю: $an+m ≡ 1. an$

Из этого будет следовать, что если нашлись два различных не взаимно простых члена последовательности $ak$ и $ak+l$ $(k,l∈ℕ )$ , которые имеют общий множитель $d ∈ℕ,d> 1,$ то в равенстве

ak+l− ak⋅Nkl = 1

левая часть делится на $d >1,$ а правая не делится, так что приходим к противоречию, которое доказывает взаимную простоту любых двух различных членов.

База индукции: для $m = 1$ имеем

2 an+1 =an − an+ 1a≡n 1

Шаг индукции:

an+m+1 = a2n+m − an+m +1 ≡an 1− 1 +1 =1

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

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

Определим последовательность $x ,x,x ,...,x 1 2 3 100$ следующим образом: пусть $x 1$ произвольное положительное число, меньшее 1 , и $2 xn+1 = xn− xn$ для всех $n =1,2,3,...,99.$ Докажите, что $3 3 3 x1+ x2+ ...+x99 < 1.$

Источники: Всесиб-2021, 9.4(см. sesc.nsu.ru)

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

Подсказка 1

Давайте попробуем раскрутить задачку с конца. Если x₁<1, то x₁-(что-то неотриц.)<1…

Подсказка 2

Вспомните про циклические суммы. Как представить x₁-x₁₀₀ по другому?

Подсказка 3

Кубы как-то особо не связаны с исходной формулой для xₙ. Зато квадраты очень даже связаны. Что нужно доказать чтобы понизить степень многочлена?

Подсказка 4

Верно, нужно доказать что 1>x₁>x₂>…>x₁₀₀>0. Теперь нужно как-то из квадратов сделать первую степень…

Подсказка 5

xₙ-x_{n+1}=xₙ², а также x₁-x₁₀₀=x₁-x₂+x₂-x₃+…-x₉₉+x₉₉-x₁₀₀

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

Докажем сначала, что $1> x >x >...>x > 0. 1 2 100$ Для этого воспользуемся индукцией по $n =1,2,...,99.$ База индукции $x ∈(0,1) 1$ верна по условию. Шаг индукции: при $xn ∈ (0,1)$ выполнены неравенства $2 0< xn < xn,$ поэтому $2 xn+1 =xn − xn <xn <1$ и $2 xn+1 = xn− xn > 0,$ то есть $xn+1 ∈(0,1).$

Ввиду доказанного, $3 2 xn < xn = xn− xn+1$ для всех $n= 1,2,...,99,$ поэтому

3 3 3 2 2 2 x1 +x2+ ...+ x99 <x1+ x2+ ...+ x99 = x1− x2+x2 − x3+ ...+ x99− x100 =x1− x100 <x1 < 1,

что и требовалось доказать.

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

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

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

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

Последовательности $a n$ и $b n$ определяются следующим образом:

an+-2 b2n+-2 a1 = 1, an+1 = an+ 1; b1 =1, bn+1 = 2bn

Докажите, что любой член последовательности $bn$ встречается в последовательности $an.$

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

На самом деле верно, что $b =a n. n+1 2$ Представим $a n$ в виде несократимой дроби $c∕d . n n$ Докажем, что $c =c2+ 2d2 2n n n$ и $d =2c d 2n n n$ индукцией по $n.$ База легко проверяется. Переход от $n$ к $n +1.$ Обозначим $cn = c,dn =d.$ Имеем

an+ 2 c+ 2d c2n +2d2n c2+ 2d2 +4cd an+1 = an+-1 =-c+-d , аналогично a2n+1 = c2n+-d2n-= c2+-2d2-+2cd

откуда

2 2 2 2 a2n+2 = 3c2c2++-64dd2-++86ccdd = (c+22(cd+)2+d)(2(cc++d)d)

что и требовалось доказать.

Далее докажем, опять же по индукции, что $bn+1 =a2n.$ База снова легко проверяется, докажем переход от $n$ к $n+ 1.$ Пусть $bn+1 = c2n∕d2n,$ обозначим $c2n = c,d2n = d.$ Тогда

b2n+1-+2- (c∕d)2+-2- c2+-2d2 bn+2 = 2bn+1 = 2c∕d = 2cd = a2⋅2n = a2n+1

по доказанному выше.

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

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

Задана последовательность

2 a1 = 18,an = an−1 +6an−1

при $n> 1.$ Докажите, что в этой последовательности не встретятся степени (выше первой) натуральных чисел.

Источники: КМО - 2020, третья задача первого дня для 8-9 классов, автор Лучинин С.А. (cmo.adygmath.ru)

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

1 2 18= 2 ⋅3

a2 = 182 +6⋅18= 432= 24 ⋅33

Докажем индукцией по номеру члена последовательности, что каждый член последовательности, начиная со второго, можно представить в виде

ak = 2k+2⋅3k+1 ⋅tk

где $tk$ — целое, не делящееся на $2$ и на $3.$

База для $k= 2$ верна. Переход:

По предположению индукции, $ai =2i+2⋅3i+1⋅ti,$ где НОД $(ti,6)= 1.$

По условию,

ai+1 = a2i + 6ai =ai(ai+ 6)= 2i+3⋅3i+2 ⋅ti(2i+1⋅3i⋅ti+ 1)

Так как $i≥ 2,$ то последний множитель не делится ни на $2,$ ни на $3,$ то же верно для $ti.$ Значит, степени вхождения $2$ и $3$ в разложение на простые множители увеличились ровно на $1.$

Осталось заметить, что число вида $2s+1⋅3s⋅m,$ где НОД $(m,6)=1,$ не может быть степенью натурального числа выше первой. Ведь если бы оно было $p$ той степенью натурального числа, то все простые множители входили бы в него в степени, кратной $p.$ Тогда и числа $s+ 1$ и $s$ должны были бы делиться на $p,$ что невозможно при $p> 1.$

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

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

Последовательность $x n$ задана условиями $x = 5 1 3$ и $x = 4− -3. n+1 xn$ Найдите $x . 100$

Источники: ИТМО - 2020, 11.8 (см. olymp.itmo.ru)

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

Подсказка 1

Попробуем подставить первые несколько значений последовательности и проследить закономерность. Как связаны числитель и знаменатель дробей?

Подсказка 2

Правильно, числитель предыдущего члена последовательности является знаменателем следующего. Попробуем обозначить x_n через новую последовательность y_n так, чтобы дробь упрощалась. Как можно выразить x_n через y_n?

Подсказка 3

Подставим это представление в рекуррентное соотношение и посмотрим, как оно упростится. К какой известной последовательности это может привести?

Подсказка 4

Получаем геометрическую прогрессию. Какой у неё знаменатель? Какой вид x_n нам это дает? Выражаем и находим ответ!

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

Перебрав несколько первых членов последовательности, можно заметить, что числитель предыдущего является знаменателем следующего.

Определим последовательность $yn$ следующим образом: $y0 = 3,y1 = 5,yn =xnyn−1$ , то есть

yn xn = yn−1-

Подставив это представление $xn$ в рекуррентную формулу, мы получим

yn+1-= 4− 3yn−1- yn yn

y = 4y − 3y n+1 n n−1

Члены последовательности $yn$ имеют вид $3,5,11,29,83,...$ Можно заметить, что разность двух соседних членов каждый раз увеличивается в три раза, что характерно для геометрической прогрессии со знаменателем 3. Значит, имеет смысл искать $yn$ как $3na+ b.$ Можно проверить, что такая любая такая последовательность удовлетворяет рекуррентной формуле. Подставляя начальные значения и решая систему уравнений, находим $a =1$ и $b= 2$ , откуда