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

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

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

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

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

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

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

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

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

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

a) Докажите, что если $xn+1 = axn + b,$ то $xn = can + d.$ (при условии $a ⁄= 1$ )

b) Найдите явную формулу $n−$ ого члена последовательности, заданной соотношениями $xn+1 = 3xn − 1,$ $x1 = 1.$

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

a) Давайте попробуем доказать это по индукции.
1. База. При $n = 1$ имеем: $x1 = ax0 + b = ca + d,$ где в качестве c берётся $x0,$ а в качестве $d$ берётся $b.$

2. Шаг индукции. Итак, пусть при всех $k$ от $1$ до $n$ мы уже доказали формулу, что $x = cak + d. k$
Докажем её для $n + 1$ :

по определению xn+1 по предполож ению индукции n n+1 xn+1 = axn + b = a(ca + d) + b = ca + ad + b.

Однако мы бы хотели, чтобы наше $x n+1$ имело вид $x = can+1 + d. n+1$
Таким образом, у нас с одной стороны свободный член получился равным $ad + b,$ а с другой стороны он должен быть просто $d.$
Из этого условия и находим $d$ : $ad + b = d,$ значит, $b = d(1− a),$ откуда $b d = 1−a.$ Вот здесь-то нам и пригодилось условие, что $a ⁄= 1.$

b) Независимо от предыдущего пункта попробуем угадать формулу, посчитав первые несколько членов:

x1 = 1; x2 = 3⋅x1− 1 = 3⋅1− 1 = 2; x3 = 3x2 − 1 = 3(3− 1 )− 1; x4 = 3(3(3− 1)− 1)− 1; x5 = 3(3(3(3− 1)− 1)− 1)− 1.

И вот, например, для $x5$ если преобразовать выражение, то становится видно, что:

2 3 2 4 3 2 x5 = 3(3(3 − 3− 1) − 1)− 1 = 3(3 − 3 − 3− 1) − 1 = 3 − 3 − 3 − 3 − 1.

Таким образом, очевидно (но лучше доказать по индукции), что для $xn$ формула имеет вид:

xn = 3n −1 − 3n− 2 − 3n−3 − ...− 31 − 1 = 3n−1 − (3n−2 + 3n− 3 + ...+ 31 + 1)

В скобках у нас появляется формула суммы геометрической прогрессии с первым членом $3n−2$ и знаменателем $13 :$

n−2 n−3 1 3n−2(1− (13)n− 1) 3n−1(1− (13)n−1) 3 + 3 + ...+ 3 + 1 = -------2--------= -------2-------. 3

В итоге имеем

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

Ответ:

$3n−1+-1 2$

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

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

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

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

Медиана пятёрки чисел, это среднее по величине из них, то есть если $a≤ b≤c≤ d≤ e$ равна числу $c.$ Последовательность $a n$ задана начальными условиями $a1 = 1,a2 =3,a3 = 5,a4 = 7,a5 =9.$ Каждый следующий член последовательности — это медиана пяти предыдущих, увеличенная на 1.

Найдите $a500$ .

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

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

Подсказка 1

Вычислите первые 15-20 членов последовательности вручную. Какой паттерн изменения значений вы замечаете? Обратите внимание на повторяющиеся группы чисел.

Подсказка 2

Начиная с а₁₀, последовательность следует правилу "три одинаковых числа, затем увеличение на 1" (докажите это!) Как это помогает вывести рекуррентную формулу?

Посдказка 3

Для n > 8 верно а(n+3)= а(n)+ 1. Как использовать это, чтобы найти а₅₀₀?

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

Посчитаем вручную несколько следующих членов: $a =6,a = 7, 6 7$ $a =8,a = 8,a = 9,a = 9, 8 9 10 11$ $a = 9,a =10, 12 13$ $a =10,a =10, 14 15$ $a16 = 11,a17 = 11,$ $a18 = 11,a19 = 12.$

Заметим, что, начиная с $a10,$ каждый член последовательности повторяется 3 раза подряд, а после этого также три раза подряд идёт это число, увеличенное на 1. Получается, что с некоторого места верно $an+3 = an+ 1.$ Докажем при помощи метода математической индукции, что пятерка членов последовательности $an,an+1,an+2,an+3,an+4$ имеет один из следующих видов:

1.: $x,x,x+1,x+ 1,x +1$
2.: $x,x+ 1,x +1,x+ 1,x+ 2$
3.: $x,x,x,x+ 1,x+ 1$

Первый вариант будет базой индукции при $n =8.$ Медианой в нем является $x+ 1,$ значит, следующий элемент последовательности — $an+5 = x+ 2.$ Мы получаем пятёрку $x,x+1,x+ 1,x +1,x+ 2,$ начинающуюся с $an+1$ и имеющую вид 2. Во втором случае медианой пятёрки также является $x+ 1,$ тогда $an+5 = x+ 2,$ получим пятерку $x+ 1,x+1,x+ 1,x +2,x+ 2,$ начинающуюся с $an+1$ и имеющую вид 3. В третьем случае медианой является $x,$ тогда $an+5 = x+1,$ получим пятерку $x,x,x+ 1,x +1,x+ 1,$ начинающуюся с $an+1$ и имеющую вид 1.

Формула $a = an +1 n+3$ доказана для $n ≥8,$ воспользуемся ей:

492- a500 = a497+ 1= a494+ 2= ...= a8+ 3 = 8+164= 172

Ответ:

172

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

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

Докажите, что для каждого натурального $n$ существуют такие целые числа $a n$ и $b n$ , что

(1+ √5)n a + b√5- --2-- = -n-2n---.

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

Докажем индукцией по $n,$ что такие числа $a n$ и $b n$ существуют, причём они будут одной чётности.

База для $n= 1$ очевидна. Докажем переход от $n$ к $n+ 1.$

( √-)n+1 ( √-)n ( √-) 1+--5 = 1+--5 1+--5 2 2 2

По предположению индукции существуют такие $an$ и $bn,$ что

(1 +√5 )n an+ bn√5 --2-- = ----2---

Тогда

( 1+√5-)n+1 (an +bn√5) (1 +√5-) (an+ 5bn)+ (an +bn)√5 --2-- = ----2--- --2-- = ---------4---------

Пусть $an+1 = an+52bn$ и $bn+1 = an+2bn.$ Из предположения индукции $an+1$ и $bn+1$ — целые числа, причём одной чётности. Переход доказан.

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

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

Дана последовательность $a,a ,a,... 1 2 3$ действительных чисел, удовлетворяющих при каждом натуральном $n≥ 3$ равенству

a2n−1 an = (−1)n ⋅3 ⋅an−1+ an−2

Найдите $2024√a2025,$ если известно, что $a1 = 1$ и $a2 =4.$

Источники: ДВИ - 2025, вариант 253, задача 2

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

Подсказка 1

Давайте просто вычислим несколько первых членов последовательности, может быть, нам удастся увидеть закономерность?

Подсказка 2

Есть подозрение, что нечетные члены последовательности, начиная с третьего, всегда равны предыдущему члену, а следующий четный член в 4 раза больше предыдущего нечетного! Убедитесь в правдивости этой гипотезы и определите, чему равен 2025 член последовательности.

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

Найдём несколько первых членов последовательности:

3 a22 a3 = (−1) ⋅3 ⋅a2+ a1 =− 12+ 16= 4

2 a4 = (− 1)4⋅3⋅a3+ a3= 12+4 =16 a2

5 a24 a5 = (− 1) ⋅3⋅a4+ a3 = −48+ 64=16

Предположим, что $i$ — некоторое четное натуральное число и $ai = ai+1,$ вычислим $ai+2$ и $ai+3:$

a2 ai+2 = (−1)i+2⋅3⋅ai+1 +-i+1= 3ai+ai = 4ai ai

2 ai+3 = (− 1)i+3⋅3⋅ai+2+ ai+2-= −3⋅4ai+ 16ai =4ai ai+1

Таким образом, наша последовательность имеет вид:

2 2 3 3 i i 1, 4, 4, 4 , 4 , 4 , 4 ,..., 42 , 42 ,...

Тогда 2025-ый член последовательности равен $41012 = 22024,$ соответственно, $2024√a2025 = 2024√22024 =2.$

Ответ: 2

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

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

Дана последовательность $a,a ,a,... 1 2 3$ действительных чисел, удовлетворяющих при каждом натуральном $n$ равенству

a1+ a2+ a3+...+an = 2an− 1

Последовательность $b1,b2,b3,...$ определяется соотношениями $b1 = 2$ и $bn+1 = bn +an,$ $n∈ ℕ.$ Найдите $b1+b2+ b3+...+b2025− 22025.$

Источники: ДВИ - 2025, вариант 252, задача 2

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

Подсказка 1

Давайте поработаем с последовательностью а, можем ли мы выразить aₙ через аₙ₋₁, не используя в записи другие члены последовательности?

Подсказка 2

aₙ = 2аₙ₋₁, то есть каждый последующий член нашей последовательности в два раза больше предыдущего! А как называется такая последовательность? Определите а₁, чтобы записать формулу для n-ого члена последовательности.

Подсказка 3

Имеем геометрическую прогрессию с первым членом, равным единице, и знаменателем, равным двойке! Теперь давайте поработаем со второй последовательностью: можем ли мы выразить bₙ₊₁, не используя других членов наших последовательностей?

Подсказка 4

Воспользовавшись формулой суммы первых n членов геометрической прогрессии, найдём формулу для bₙ₊₁, а дальше остается просто посчитать искомую сумму!

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

Рассмотрим последовательность $a : n$

2an− 1= a1+ a2 +...+ an−1+ an

Тогда для любого $n ≥ 2:$

2an−1− 1= a1+ a2 +...+ an−2+ an− 1

Подставим второе равенство в первое:

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

an =2an−1

Пользуясь ранее найденным $a1 = 1,$ получаем $an =2n−1.$

Теперь рассмотрим вторую последовательность:

bn+1 = bn+ an = bn−1+ an−1+ an = b1+ a1+ a2+a3+ ...+ an

По формуле суммы геометрической прогрессии:

0 n bn+1 = 2+ 2-⋅(2-− 1)= 2n+ 1 (2− 1)

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

b1 +b2+ ...+b2025− 22025 = 2025 +20+ 21+...+22024− 22025 =

0 2025 = 2025+ 2-⋅(2----− 1)− 22025 = 2025− 1= 2024 (2− 1)

Ответ: 2024

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

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

Строго возрастающая последовательность $a ,a,a ,... 1 2 3$ натуральных чисел удовлетворяет при каждом натуральном $n$ соотношению

∘---------------- an+2 ≤ a2n +2an+ 2an+1 +2

Найдите все возможные значения $a25,$ если известно, что $a1 = 1.$

Источники: ДВИ - 2025, вариант 254, задача 2

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

Подсказка 1

Как воспользоваться условием о том, что a₁ = 1?

Подсказка 2

Можно ли с его помощью вычислить несколько первых членов последовательности?

Подсказка 3

Заметим, что так как последовательность строго возрастающая, 1 = a₁ < a₂ < a₃. Попробуйте выразить a₃.

Подсказка 4

Для a₃ можно воспользоваться неравенством из условия. Не забывайте, что члены последовательности — натуральные числа.

Подсказка 5

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

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

Найдём несколько первых членов последовательности:

∘-2------------ √------ 1 =a1 <a2 < a3 ≤ a1+ 2a1+2a2+ 2= 5+ 2a2

2 2 a2 < a3 ≤ 5+2a2

2 a2 − 2a2− 5< 0

1< a < √6+ 1< 4 2

Так как все члены последовательности натуральны, $a2$ в соответствии с полученным неравенством может принимать значения 2 и 3.

Пусть $a2 =3,$ тогда

3< a3 ≤√5-+2-⋅3-=√11-< 4

Но не существует натурального числа, лежащего между 3 и 4, следовательно, такой случай невозможен.

Получается, что $a2 = 2,$ в этом случае

√ - 2< a3 ≤ 9= 3

Следовательно, $a3 =3.$

Предположим, что $i$ -тый член последовательности равен $i,$ а $(i+1)$ -ый член последовательности равен $i+1,$ найдём $(i+2)$ -ой член последовательности:

∘--------------- ∘ -------------- ∘-------- i+1 <ai+2 ≤ a2i + 2ai+2ai+1 +2= i2+ 2i+2i+ 2+ 2= i2+4i+ 4= i+2

ai+2 = i+ 2

Таким образом, методом математической индукции доказано, что данная нам последовательность — последовательность натуральных чисел, тогда $a25 =25.$

Ответ: 25

Курсы

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

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

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

Дана последовательность $a,a ,a... 1 2 3$ действительных чисел, удовлетворяющих при каждом натуральном $n$ равенству

5−-an an+1 = 4

Пусть $Sn$ обозначает сумму первых $n$ членов этой последовательности: $Sn = a1 +...+ an.$ Известно, что $a1 = 11.$ Найдите наименьшее значение $n,$ при котором выполняется неравенство

1 |Sn− n− 8|< 1000

Источники: ДВИ - 2025, вариант 251, задача 2

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

Подсказка 1

Попробуйте вычислить несколько первых членов последовательности.

Подсказка 2

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

Подсказка 3

Это геометрическая прогрессия! Попробуйте понять, через какую формулу можно найти ее n-ый член.

Подсказка 4

aₙ = 1 + 10 ⋅ (-1/4)ⁿ⁻¹.

Подсказка 5

Осталось лишь найти по формуле сумму геометрической прогрессии и подобрать n.

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

Заметим, что искомому рекуррентному соотношению удовлетворяет данная формула для $n$ -го члена последовательности:

( 1)n−1 an =1+ 10 − 4

Покажем это, подставив формулу в соотношение:

( ) ( )n 5− 1− 10 − 1 n− 1 ( )n−1 ( )n 1+ 10 − 1 = ----------4-----= 1+ (−1)⋅ 1 ⋅10 − 1 = 1+ 10 − 1 4 4 4 4 4

По формуле суммы геометрической прогрессии найдем сумму:

∑n ( ( 1)k− 1) n∑ ( 1)k−1 ( ( 1)n) ( 1)n Sn = 1+ 10 −4 = n+ 10 −4 = n+ 8 1 − − 4 =n +8 − 8 − 4 k=1 k=1

Теперь рассмотрим выражение $|Sn− n− 8|:$

| ( ) | | ( ) | |( ) | |S − n− 8|= ||n+ 8− 8 − 1 n − n − 8||= ||− 8 − 1 n||=8|| − 1 n||= 8 n | 4 | | 4 | | 4 | 4n

Найдем наименьшее $n,$ для которого выполняется неравенство:

8n-< -1-- 4 1000

8000 <4n

Проверим степени четверки: $45 = 1024,$ $46 =4096,$ $47 =16384.$ Неравенство $4n >8000$ впервые выполняется при $n =7.$

Ответ: 7

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

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

Исследуем рекуррентное соотношение вида

an+2 = pan+1+ qan,

(1)

обычно называемое линейным рекуррентным соотношением второго порядка.

Докажите, что

(a) Ненулевая геометрическая прогрессия ${an}= bxn0$ удовлетворяет соотношению $(1)$ тогда и только тогда, когда $x0$ является корнем его характеристического уравнения.

(b) Ненулевая последовательность ${an}= bnxn0$ удовлетворяет соотношению $(1)$ тогда и только тогда, когда $x0$ является кратным корнем его характеристического уравнения.

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

(a) Если подставить $n an =bx0$ в (1), получится

n+2 n+1 n bx0 =pbx0 +qbx0.

Делим на $bxn, 0$ получаем

2 x0− px0− q =0.

Это и есть условие на $x0.$ В обратную сторону: если $x0$ удовлетворяет $x2− px0− q = 0, 0$ то умножив это равенство на $xn, 0$ получаем

n+2 n+1 n x0 = px0 + qx0.

Умножив на $b,$ получаем, что $an+2 = pan+1 +qan$ верно для всех $n.$

(b) Подставим $an = bnxn 0$ в (1). Получаем

b(n+ 2)xn+2= pb(n+ 1)xn+1+ qbnxn. 0 0 0

Теперь разделим обе части на $bxn0$ (это можно сделать, так как $b⁄=0$ и $x0 ⁄= 0$ ). После деления остаётся

(n+ 2)x20 = p(n +1)x0+ qn.

Мы видим, что это равенство должно выполняться при всех $n.$ Чтобы оно было тождеством, коэффициенты при $n$ и свободный член должны совпадать по обе стороны. Это даёт систему

x20− px0− q =0, 2x0− p= 0.

Первое уравнение означает, что $x0$ — корень характеристического уравнения, второе — что этот корень является кратным.

В обратную сторону: если выполнены условия $x20− px0− q = 0$ и $2x0 − p= 0,$ то равенство

(n+ 2)x20 =p(n+ 1)x0+ qn

выполняется для любого $n.$ Умножим его на $n x0,$ получим

n+2 n+1 b(n+ 2)x0 = pb(n+ 1)x0 + qbnxn0.

Это означает, что для $n an =bnx0$ действительно выполняется рекуррентное соотношение

an+2 = pan+1 +qan

при всех $n.$

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

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

Исследуем рекуррентное соотношение вида

an+2 = pan+1+ qan,

(1)

обычно называемое линейным рекуррентным соотношением второго порядка.

(a) Пусть характеристическое уравнение соотношения $(1)$ имеет два различных корня $x1$ и $x2.$ Тогда существует единственная пара чисел $c1$ и $c2$ такая, что $an = c1xn1 +c2xn2.$

(b) Пусть характеристическое уравнение соотношения $(1$ ) имеет кратный корень $x0.$ Тогда существует единственная пара чисел $c1$ и $c2$ такая, что $an = (c1 +c2n)xn0.$

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

(a) Подставим $n n an = c1x1 +c2x2$ в соотношение (1):

n+2 n+2 an+2 = c1x1 +c2x2 .

С другой стороны,

n+1 n+1 n n pan+1+ qan =p(c1x1 + c2x2 )+ q(c1x1 +c2x2).

Раскроем скобки:

n+1 n n+1 n pan+1 +qan = c1(px1 + qx1)+ c2(px2 +qx2).

pa +qa = cxn(px +q)+ cxn(px +q). n+1 n 11 1 22 2

Так как $x21 = px1+q$ и $x22 = px2+ q,$ получаем

pan+1+ qan = c1xn1+2+ c2xn2+2 =an+2.

Значит, формула $an = c1xn1 +c2xn2$ действительно задаёт решение.

Теперь покажем единственность. Для $n = 0,1:$

a0 = c1+ c2, a1 =c1x1+ c2x2.

Так как $x1 ⁄= x2,$ система очевидно имеет единственное решение $(c1,c2).$

Таким образом, общее решение рекуррентного соотношения (1) имеет вид

an = c1xn1 +c2xn2,

где $c1,c2$ однозначно определяются начальными условиями $a0,a1.$

(b) Подставим $n an = (c1+ c2n)x0$ в соотношение (1):

an+2 = (c1+ c2(n+ 2))xn0+2.

С другой стороны:

pan+1 +qan = p(c1+ c2(n+ 1))xn0+1+ q(c1+ c2n)xn0.

pan+1+ qan = xn0[p(c1+ c2(n+ 1))x0+ q(c1+ c2n)].

Так как $x0$ — кратный корень уравнения $2 x − px − q =0,$ выполняются соотношения

x20 = px0+q, 2x0 = p.

Подставляем:

2 2 p(c1+ c2(n+ 1))x0+ q(c1+c2n)= (c1+ c2n)x0+ 2c2x0.

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

n+2 pan+1+ qan =(c1+c2(n+ 2))x0 = an+2.

Значит, формула $an = (c1+ c2n)xn 0$ действительно задаёт решение.

Единственность следует из начальных условий:

a0 = c1, a1 = (c1+ c2)x0.

Эта система, очевидно, имеет единственное решение, назовем его $(c1,c2).$

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

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

Найдите все последовательности натуральных чисел $a ,a ,... 1 2$ такие, что для любого натурального $n$ выполнено равенство

2 (n + 1)an =n(an2 + 1).

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

Подсказка 1:

Какие наблюдения можно сделать, глядя на равенство из условия? Например, aₙ точно делится на n, потому что (n, n² + 1) = 1.

Подсказка 2:

Кстати, нетрудно заметить, что последовательность aₙ = n подходит. Попробуйте доказать, что это единственный ответ.

Подсказка 3:

Вместо того чтобы доказывать, что aₙ = n, можно ввести другую последовательность bₙ, зависящую от членов a. Для удобства можно подобрать такую bₙ, которая равна константе, если aₙ = n.

Подсказка 4:

Можно взять bₙ = (aₙ / n) – 1. То есть мы хотим доказать, что bₙ = 0. Какой вид примет рекуррентное соотношение?

Подсказка 5:

Обратите внимание, n² + 1 взаимно просто с n. На какую максимальную степень n делится bₙ?

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

Поскольку $(n2 +1,n)=1,$ $a n$ делится на $n.$ Тогда пусть $b = an− 1. n n$ Выражение из условия переписывается в следующем виде:

2 ( 2 ) (n + 1)n(bn +1)= n n (bn2 + 1)+1

2 2 bn(n + 1)= bn2n

Подставляя $n= 1,$ получаем $b1 = 0.$ Теперь пусть $n >1.$ Заметим, что $bn$ делится на $n2,$ тогда $b2 n$ делится на $n4,$ то есть $bn$ делится на $n6.$ Продолжая рассуждения, получаем, что $bn$ делится на сколь угодно большую степень $n.$ Тогда $bn = 0,$ то есть $an =n.$

Ответ:

$a =n n$

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

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

Последовательность ${a} n$ определена условиями

-1-- a0 = 7 и an = an−1+ an−1 для n ∈ℕ.

Докажите, что $64< a2024 < 65.$

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

Возведем в квадрат второе уравнение

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

Выразив остальные члены последовательности, получим систему

( ||| a2n = a2n−1+ a12-+2 ||||| a2 = a2 +n−211--+2 ||||{ n2−1 n2−2 an−12- an−2 = an−3+ a2n−3 +2 ||||| ⋅⋅⋅ ||||| a22 = a21+ 1a21 +2 ||( a21 = a20+ 12+2 a0

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

2 2 n−∑ 11 an = 2n+ a0+ a2k k=0

Тогда

20∑231 a22024 =4097+ a2> 4097 k=0 k

А значит, $a2024 > 64.$

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

20∑231 1 a22024 =4097+ a2< 4097 +2024⋅49 < 4225= 652 k=0 k

Интенсивы

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

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

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

Последовательность ${a } n$ задаётся следующим образом: $a = 1 1$ , $a = a + 1- n+1 n an$ для любого натурального $n.$ Докажите, что $a100 >14.$

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

Заметим, что $a > 0 n$ для любого натурального $n.$ Также

( 1 )2 a2n+1 = an + an- > a2n+ 2

Тогда

a2100 > a299+ 2> a298 +2⋅2> ...> a21+ 2⋅99= 199> 142

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

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

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

Докажите, что все члены последовательности

∘ --2--- x1 = 0, xn+1 = 2xn+ 3xn+ 1, n= 1,2,...

являются целыми числами.

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

Заметим, что все члены последовательности неотрицательны, и

∘------ xn+1 = 2xn+ 3x2n+ 1> 2xn ≥ xn

Поэтому все члены последовательности различны. Перенеся $2xn$ в левую часть и возведя полученное равенство в квадрат, получаем

x2n+1− 4xn+1xn+ x2n = 1

Кроме того, также выполняется и равенство

x2n−1− 4xn−1xn+ x2n = 1

(получаемое уменьшением индексов на $1$ ). Это означает, что $xn+1$ и $xn−1$ являются корнями уравнения $2 2 x − 4xnx+ xn = 1.$ Тогда по теореме Виета получаем $xn+1+ xn−1 = 4xn,$ т. е. $xn+1 =4xn − xn−1.$ Отсюда в силу того, что первые два члена последовательности — целые числа, следует, что все $xn,$ вычисляемые с помощью полученной формулы, т. е. $xn = 4xn−1− xn−2,$ — целые числа.

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

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

Последовательность ( $a n$ ) удовлетворяет условиям

∘ -------- a1 = 1, an+1− an = an+ an+1 при всех n≥ 1.

Какие значения может принимать $a 2023$ ?

Источники: ОММО - 2024, задача 10 (см. olympiads.mccme.ru)

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

Подсказка 1

Давайте для начала возведём в квадрат и посмотрим, что же у нас получается после приведения подобных. Во-первых, у нас получается симметричное уравнение относительно a_(n + 1) и a_n. А это значит, что то, что верно для a_(n - 1) верно и для a_(n + 1) относительно a_n. Что можно тогда заметить?

Подсказка 2

Мы можем заметить, что уравнению t^2 - (2a_n + 1)*t + a^2_n - a_n = 0 удовлетворяют и а_(n - 1), и a_(n + 1). Значит, по теореме Виета, a_(n - 1) + a_(n + 1) = 2a_n + 1. Теперь попробуйте найти первые несколько членов!

Подсказка 3

У нас получается такая прогрессия - 1,3,6,10….- это же значения суммы первых n натуральных чисел. Попробуйте это доказать, и тогда задача сведётся к тому, чтобы записать ответ.

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

Выписав условие $a − a ≥ 0 n+1 n$ , возведем равенство в квадрат и запишем его для двух соседних членов последовательности

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

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

То есть получаем, что $a n+1$ и $a n−1$ — два корня уравнения

2 2 t − (2an+ 1)⋅t+ an− an = 0

По теореме Виета получаем

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

an+1 = an+ (an− an−1)+1

Первые члены последовательности равны $1,3,6,10,...$ Это очень похоже на суммы первых $n$ натуральных чисел. Давайте по индукции докажем формулу:

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

База очевидна: $a1 = 1= 1⋅22$

Переход ясен:

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

Поэтому

2022⋅2023 a2023 = 2 = 2047276

Ответ: 2047276

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

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

Последовательность натуральных чисел $a,a ,a ,... 0 1 2$ определяется следующими соотношениями:

a0 = 1

a =kn +(−1)na , n n−1

где $k$ — фиксированное натуральное число.

Сколько существует таких последовательностей, в которых встречается число 2024?

Источники: Курчатов - 2024, 11.1 (см. olimpiadakurchatov.ru)

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

Подсказка 1

Дана формула для вычисления членов последовательности, но она выглядит сложно, попробуйте явно выразить первые члены, может быть увидите какую-то закономерность.

Подсказка 2

Видно, что каждый член с номером, дающим остаток 3 при делении на 4, равен 1. Тогда попробуйте выразить формулы и доказать их справедливость для членов с номерами 4m, 4m+1, 4m+2 и 4m+3, где m — целое неотрицательное число.

Подсказка 3

Все члены с номерами вида 4m имеют вид 4mk+1, с номерами 4m+1 — k-1, с номерами 4m+2 — (4m+3)k-1, с номерами 4m+1 — 1. Доказывать эти формулы очень удобно по индукции, ведь по условию дано соотношение, где последующий член выражается через предыдущий.

Подсказка 4

Теперь, используя полученные формулы, посмотрите какие члены нашей последовательности могут равняться 2024.

Подсказка 5

Числа с номерами 4m и 4m+3 сразу отпадают из-за нечётности, а с номером 4m+1 даёт только одну последовательность (какую?). Для чисел с номерами 4m+2 получается уравнение в целых числах ((4m+3)k=2025). При решении полученного уравнения количество рассматриваемых случаев можно уменьшить, рассмотрев, какие остатки при делении на 4 дают 4m+3, 2025 и какой тогда остаток при деление на 4 должно иметь k.

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

Докажем, что для любого целого $m ≥0$ справедливы следующие формулы:

a = 4mk+ 1, 4m a4m+1 = k− 1, a4m+2 = (4m + 3)k− 1, a4m+3 = 1.

Будем доказывать эти формулы индукцией по $m$ . База $m = 0$ проверяется непосредственно. Предположим, что формулы справедливы для всех чисел, не больших $m − 1$ , и докажем эти формулы для числа $m$ . Поскольку по предположению индукции $a4m−1 = 1$ , последовательно получаем следующие равенства:

a4m = k⋅(4m)+ (−1)4ma4m−1 =4mk +1, a = k(4m +1)+ (− 1)4m+1a = (4km + k)− (4mk+ 1)=k − 1, 4m+1 4m+2 4m a4m+2 = k(4m +2)+ (− 1) a4m+1 = (4km +2k)+ (k − 1)= (4m + 3)k− 1, a4m+3 = k(4m +3)+ (− 1)4m+3a4m+2 = (4km +3k)− (4km +3k − 1)= 1.

Таким образом, наши формулы доказаны. Теперь, используя эти формулы, посмотрим, какие члены нашей последовательности могут равняться 2024. Ясно, что числа вида $a4m$ и $a4m+3$ не могут равняться 2024: числа вида $a4m$ нечётны, а числа вида $a4m+3$ равны 1 . Далее, числа вида $a4m+1$ могут равняться 2024 только при $k =2025$ , что дает нам один пример последовательности.

Наконец, предположим, что для некоторого целого неотрицательного $m$ число $a4m+2$ равно 2024 . Мы получаем следующее уравнение: $(4m+ 3)k= 2025$ . Заметим, что сомножитель $4m + 3$ дает остаток 3 при делении на 4 , а число 2025 дает остаток 1 при делении на 4. Значит, число $k$ , во-первых, должно быть делителем числа 2025 , а во-вторых, должно иметь остаток 3 при делении на 4 (т.к. $3⋅3≡ 1(mod4)$ ). Поскольку $2025 =34⋅52$ , число $k$ имеет вид $3α⋅5β$ , где $α∈ {0,1,2,3,4}$ и $β ∈{0,1,2}$ . Для того, чтобы число $k$ такого вида давало бы остаток 3 при делении на 4 , необходимо и достаточно, чтобы степень $α$ была бы нечетной (поскольку $5 ≡1(mod4)$ и $3α ≡ 4(−1)α(mod4)$ ). Получаем ещё 6 возможных значений $k:3,3⋅5,3⋅52,33,33⋅5,33⋅52$ . Вместе с вариантом $k =2025$ получаем 7 возможных последовательностей.

Ответ: 7

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

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

Последовательность ${a } n$ задана рекуррентным соотношением

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

и начальными условиями $a0 = 1,a2 =5.$ Чему может быть равно $a6?$

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

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

Подсказка 1

Что первое хочется сделать, увидев рекуррентную формулу? Попробовать подставить что-то вместо n. Например, взять n-1 и посмотреть, что получится. В задаче же у нас спрашивают про чётный член. Тогда в теории надо как-то избавиться от членов вида n-1 и n-3 в формуле. Посмотрев на формулы для n и n-1, что можно попробовать сделать?

Подсказка 2

Давайте сложим две формулы, тогда останутся только члены с номерами n, n-2 и n-4. Теперь, записав полученное выражение как разность членов n, n-2 и n-2, n-4, можем найти формулу для разности 2k и 2(k-1) члена, через суммирование таких выражений. Как же теперь можно найти формулу для 2k-ого члена?

Подсказка 3

Верно, сложим аналогично выражения для всех k от 1 до 3. Тогда слагаемые буду сокращаться и мы сможем выразить 6-ый член. Победа!

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

Перепишем рекуррентную формулу:

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

Записав её для $n − 1$ вместо $n,$ получим

an−1 − an−3 = an−2− an−4 +3,

откуда

an− an−2 =an−2− an−4+6

Поскольку $a2− a0 =4,$ то

a2i− a2(i− 1) = 4+ 6(i− 1)

Значит,

a = 1+∑3 (4+ 6(i− 1)) =1+ 3⋅4+ 3⋅3(3− 1)= 31 6 i=1

Ответ: 31

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

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

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

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

Последовательность $(a ) n$ удовлетворяет условиям

∘ -------- a0 =0, a1 ⁄=0, an+1− an = an+an+1 при всех n ≥0.

Какие значения может принимать $a 2024$ ?

Источники: ОММО - 2024, задача 10 (см. olympiads.mccme.ru)

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

Подсказка 1

Подсказка 2

Подсказка 3

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

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

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

То есть получаем, что $a n+1$ и $a n−1$ — два корня уравнения

2 2 t − (2an+ 1)⋅t+ an− an = 0

По теореме Виета получаем

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

an+1 = an+ (an− an−1)+1

Первые члены последовательности равны $0,1,3,6,10,...$ Это очень похоже на суммы первых $n$ натуральных чисел. Давайте по индукции докажем формулу:

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

База очевидна: $a0 = 0= 0⋅12$

Переход ясен:

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

Поэтому

2023⋅2024- a2024 = 2

Ответ:

$2023⋅2024 2$

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

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

Найдите общий вид члена последовательности

(a) $a0 = 0, a1 = 1, an+2 = 5an+1 − 6an;$

(b) $a0 =1, a1 = 2, an+2 = 2an+1 − an;$

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

Подсказка 1, пункт (a)

Сначала нужно найти характеристический многочлен рекурренты и его корни. Как выглядит общий вид решения линейной рекурренты?

Подсказка 2, пункт (a)

Верно! Общий вид решения — сумма n-ых степеней корней характеристического многочлена, умноженных на некоторые коэффициенты. Как найти эти коэффициенты?

Подсказка 1, пункт (b)

Снова находим характеристический многочлен. Сколько у него корней?

Подсказка 2, пункт (b)

Верно! У него 1 корень. Как тогда выглядит общий вид решения?

Подсказка 1, пункт (c)

Тут всё аналогично первому пункту. Возможны только не самые приятные корни характеристического уравнения, но бояться их не стоит.

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

(a) Запишем наше характеристическое уравнение $2 q − 5q+6 =0.$ Тогда $q = 2$ или $q = 3.$ Любое решение рекурренты может быть представлено в виде $n n an = 2 A+ 3 B.$ Из условий $a0 = 0$ и $a1 = 1$ получаем подстановкой уравнения $A+ B =0$ и $2A +3B = 1.$ Решаем систему и получаем $A= −1,$ $B = 1.$ Тогда $n n an =3 − 2 .$

(b) Находим характеристическое уравнение: $2 q − 2q+ 1= 0.$ Решаем уравнение и получаем $q = 1.$ Так как у нас два корня, то общий вид решения этой рекурренты имеет вид $n an = (A+ Bn)⋅1 = A+ Bn.$ Подставляем начальные условия $a0 =1$ и $a1 = 2$ и находим $A$ и $B :$

A+ B ⋅0 =1

A+ B ⋅1 =2

Таким образом, $A =B = 1,$ то есть получаем, что $an =n +1.$

(c) Это рекуррентное уравнение — определение чисел Фибоначчи. Общий вид его решения называется формулой Бине. Найдем ее по аналогии с предыдущими пунктами. Для этого сначала находим характеристическое уравнение $q2− q− 1= 0.$ Тогда $q = 1±√5. 2$ Таким образом,

( 1+√5 )n (1− √5)n Fn = --2-- A + --2-- B

Подставим $F0 = 0$ и $F1 = 1$ и получим $A +B = 0$ и $√- √- 1+2-5A+ 1−25B =1.$ Тогда $A = 1√- 5$ и $B = −√1. 5$ Таким образом,

( √-)n ( √-)n Fn = 1+--5 √1-− 1−--5 √1- 2 5 2 5

Ответ:

(a) $n n an =3 − 2 ;$

(b) $an = n+ 1;$

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

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

Последовательность чисел $a n$ определяется условиями $a =20, 1$ $a = 50, 2$ $a =a − -3. n+1 n−1 an$ Найдите номер первого отрицательного члена этой последовательности.

Источники: Курчатов - 2024, 10.3 (см. olimpiadakurchatov.ru)

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

Подсказка 1

Попробуйте поработать с формулой (n+1)-го члена.

Подсказка 2

Например, можно домножить все на aₙ?

Подсказка 3

Тогда получится, что произведение соседних членов последовательности каждый раз уменьшается на 3! А нам ведь известны первые 2 члена последовательности…

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

Перепишем рекуррентное условие последовательности как

an+1an = anan−1− 3

Значит, произведение соседних членов последовательности каждый раз уменьшается на $3.$ Оба начальных члена последовательности положительны, значит, пока это произведение положительно, каждый следующий член последовательности будет оставаться положительным. Известно, что $a a = 1000, 1 2$ значит,