Последовательности. Индукция. —Каталог задач по Высшей математике

Главная
Каталог задач
Каталог заданий по Другое - Высшая математика
Последовательности. Индукция.

Тема Математический анализ

15 Последовательности. Индукция.

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

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

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

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

Подтемы раздела математический анализ

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

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

Задача 1#37947

a) Пусть у нас есть 13 различных видов конфет. И пусть мы хотим подарить кому-то конфеты трёх различных видов из этих 13. Сколькими способами можно выбрать эти 3 вида из 13? То есть сколько различных варианта подарка мы можем составить?

b) В разложении $(x+ y)13$ найти коэффициент при $x10y3$

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

На оба пункта ответ один и тот же - это количество неупорядоченных выборок из 13 объектов по 3. То есть, это будет равно биномиальному коэффициенту $(13) =-13!-= 11⋅12⋅13 = 11⋅2⋅13 = 22⋅13 = 286. 3 10!3! 6$

Ответ:

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

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

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

Задача 2#37946

Доказать, что знакопеременная сумма биномиальных коэффициентов $∑n (n) (− 1)k k k=0$ равна 0. То есть

n ( ) ∑ (− 1)k n = 0 k=0 k

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

Достаточно лишь подставить в формулу бинома Ньютона $∑n (n) (a+ b)n = k an−kbk, k=0$ справедливую при всех $a,b$ вместо этих букв конкретные значения $a = 1,$ $b = − 1.$ И тогда получится, что $n n n ∑n (n) k (a + b) = (1− 1) = 0 = 0 = k=0 k (− 1) .$ И мы всё доказали.

Ответ:

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

Задача 3#37945

Доказать формулу для бинома Ньютона по индукции:

n ∑n (n) n− ii (a+ b) = i a b i=0

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

1. База индукции. При $n = 1$ наша формула очевидна: $(a + b)1 = a+ b.$ Следовательно, формула верна при $n = 1.$

2. Шаг индукции. Пусть мы установили истинность формулы биному при всех $n$ от $1$ до $k.$ Докажем её тогда для $n = k+ 1$ :

$по предполож ению индукции (a+ b)k+1 = (a+ b)k(a+ b) =$
$= (ak + (k)ak−1b +(k)ak−2b2 + ...+ (k)bk)(a+ b) = 1 2 k$
$() ( ) ( ) ( ) () ( ) ∑k ( ) ( ) = (ak+1 + k1akb + k2 ak−1b2 + ...+ kkabk)+ (akb+ k1 ak− 1b2 + k2 ak−2b3 + ...+ kk bk+1) = ( ki + ki+1 )ak−ibi+1. i=−1$

Причём отметим, что в нашей записи биномиального коэффициента $( ) ki$ или $i > k,$ или $i < 0,$ то мы считаем по определению, что такой биномиальный коэффициент равен 0 (т.к. выборов такими параметрами просто не существует).

Далее, преобразуем немного наши индексы: $∑k () ( ) k∑ ( ) (ki + ik+1 )ak−ibi+1 = ki++11 ak− ibi+1. i=−1 i=−1$ Здесь мы воспользовались соотношением, верным для любых $i$ и $k$ : $(k) (k ) (k+1) i + i+1 = i+1 .$ Далее, просто сдвинем индекс суммирования на единичку, чтобы всё получилось красиво: $∑k (k+1)ak−ibi+1 = k+∑1 (k+1)ak+1−ibi i=−1 i+1 i=0 i$

Следовательно, мы заключаем, что $k∑+1( ) (a+ b)k+1 = k+i1ak+1−ibi. i=0$ Но именно это мы с вами и хотели доказать.

Ответ:

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

Задача 4#37944

Доказать следующие свойства биномиальных коэффициентов ( для любых $n$ и $k$ таких, что $1 ≤ k ≤ n$ ):

a) $(n) (n ) k = n− k$

b) $(n)+ (n ) = (n+1) k k+1 k+1$

c) $n∑ ( ) ( ) ( ) ( ) ( ) ( ) ( ) nk = nn + nn−1 + nn−2 + ⋅⋅⋅+ nk + ⋅⋅⋅+ n1 + n0 = 2n k=0$ (пользуясь исключительно комбинаторным определением! т.е. без бинома Ньютона)

d) $(n) k$ возрастает по $n$ при фиксированном $k$

e)* Фиксируем $n.$ Найти такое $k,$ при котором $( ) nk$ максимально.

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

a) Как мы помним, $(n) k$ равно числу подмножеств размера $k$ у $n$ -элементного множества $S.$ Но любому $k$ -элементному подмножеству $A ⊂ S$ можно однозначно сопоставить $(n − k)$ -элементное подмножество $¯A$ в $S.$ Другими словами, выбрать $k$ элементов из $n$ возможных – это то же самое, что из $n$ -элементного множества ”выкинуть” $\text{[math]}$ $n − k$ элементов.

По формуле для $(n) k$ всё совсем очевидно.
Поскольку $( ) nk = k!(nn!−k)!,$ то $( ) nn−k = (n−nk!)!(k)! = k!(nn−!k)!,$ так как наша формула $--n!-- k!(n−k)!$ очевидно симметрична относительно замены $k$ на $n− k.$

b) Это легко доказать просто поигравшись с формулой $( ) nk = k!(nn−!k)!.$
Действительно: $(n) (n ) --n!-- -----n!---- приведём к общ. знам. n!(k+1)+n!(n−k) k + k+1 = k!(n− k)! + (k+1)!(n−k−1)! = (k+1)!(n−k)! =$
$( ) = n!(((kk++11))!+(n(−n−k)k!)) = (k+n1!()n!(+n1)−k)! = (k+(1n)+!(1n)!−k)! = n+k+11$

c)В левой стороне равенства мы суммируем количество способов выбрать:

$n$ -элементное подмножество из n-элементного множества
$(n− 1)$ -элементное подмножество из n-элементного множества
...
$1$ -элементное подмножество из n-элементного множества
$0$ -элементное подмножество из n-элементного множества

То есть мы суммируем количество способов выбрать все возможные подмножества из $n$ -элементного множества. Но таких подмножеств будет ровно $n 2 ,$ поскольку подмножество множества $X$ можно задать так: сопоставить 0 тем элементам, которые в подмножество не входят, и 1 - тем элементам, которые в подмножество входят. Тогда различных подмножеств множества $X$ всего столько же, сколько строк длины $|X |,$ составленных из нулей и единиц, то есть $2n$

d) $(nk)$ при фиксированном $k$ - это количество способов выбрать $k$ объектов из всё бОльших и бОльших множеств ( $n$ растёт по условию, а $n$ - это и есть "размер" $\text{[math]}$ множества, из которого мы выбираем). Таким образом, очевидно, что т.к. растёт количество элементов в множестве, из которого мы выбираем элементы, то и вариантов выбрать какие-то $k$ у нас будет становиться всё больше и больше.

e)* Заметим такое очевидное соотношение:

$(n ) = ----n!-----= ---n!- ⋅--k-- = (n)⋅--k-- k−1 (k−1)!(n−k+1)! k!(n−k)! n−k+1 k n−k+1$

Что же оно нам даёт? А даёт оно нам условие, при котором при фиксированном $n$ предыдущий по $k$ биномиальный коэффициент не больше следующего. А именно, если присмотреться, то из нашей формулы следует, что:

( ) ( ) n ≤ n если и только если---k---- ≤ 1 k− 1 k n − k+ 1

Но это последнее условие уже, в свою очередь, эквивалентно тому, что $k ≤ n− k + 1,$ то есть $2k ≤ n + 1,$ то есть $k ≤ n+1. 2$

Отсюда делаем вывод, что биномиальные коэффициенты растут при фиксированном $n$ до тех пор, пока $k ≤ n+21.$ То есть, наибольшее значение $( ) nk$ будет при максимальном $k$ таком, что $k ≤ n+1. 2$ А это есть просто $k = ⌊n+1⌋ 2$ ( $⌊...⌋$ означает округление вниз до ближайшего целого.)

Ответ:

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

Задача 5#37943

Доказать, что:
$n (2!)⋅(4!)⋅...⋅(2n!)> ((n+ 1)!)$ при условии, что $n >1.$

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

1. База индукции. При $n= 2$ (внимание, по условию $n> 1$ ) у нас получается неравенство $2 2!⋅4!> (3!).$ И действительно, левая часть равна 48, а правая - всего лишь 36. Таким образом, базу мы проверили.

2. Шаг индукции. Предположим, утверждение верно при всех натуральных числах до $k,$ то есть при 1, 2, 3,..., $k.$ Основываясь на этом предположении, докажем его для $k+ 1$ :
Смотрите, по предположению индукции нам уже дано, что $k (2!)⋅(4!)⋅...⋅(2k!)> ((k+ 1)!).$
Теперь, давайте домножим обе части этого неравенства на $(2(k+ 1))!$ :

$(2!)⋅(4!)⋅...⋅(2k!)⋅(2(k+ 1))!>((k+1)!)k⋅(2(k+ 1))!.$ Но правая часть неравенства равна $((k+1)!)k⋅(k+2)!(k+ 3)(k+ 4)...(2k)(2k+ 1)(2k+ 2)$ что явно больше, чем
$((k+1)!)k⋅(k+2)!(k+ 2)(k+ 2)...(k+ 2)(k+ 2)(k+ 2)=((k+ 1)!)k⋅(k+ 2)k(k+2)!= ((k+ 2)!)k+1.$ Таким образом, мы всё доказали.

Ответ:

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

Задача 6#37942

Докажите, что:
Число $2n−2 n+1 n−1 6 + 3 +3$ кратно $11.$

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

1. База индукции. При $n= 1$ наше выражение равно $62⋅1−2+ 31+1+ 31− 1 =60+ 32+ 30 =11.$ $11$ кратно $11,$ поэтому база индукция очевидно выполнена.

2. Шаг индукции. Пусть мы уже доказали, что наше выражение $2n−2 n+1 n− 1 6 +3 + 3$ кратно $11$ при всех $n =1,2,3,...,N.$ Докажем его для $N +1$ :

$2(N+1)−2 N+2 N 2N− 2 N+1 N−1 6 + 3 + 3 = 36⋅6 +3⋅3 +3⋅3 =$ $N−2 N−2 N+1 N −1 = 33⋅6 +3⋅(6 + 3 + 3 ).$
Теперь очевидно, что и при $N + 1$ наше выражение делится на $11,$ потому что у нас получилась сумма двух слагаемых: одно из них кратно $33,$ а, значит, и $11.$ Другое, в свою очередь, представляет собой просто наше выражение при $n= N,$ а оно кратно $11$ по предположению индукции. Но сумма двух чисел кратных $11$ тоже кратна $11.$ Следовательно, всё доказано.

Ответ:

Курсы

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

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

Задача 7#36613

Доказать, что если $x ,x ,...x 1 2 n$ - произвольные положительные числа такие, что $x ⋅x ⋅...⋅x = 1, 1 2 n$ то $x1+ x2+ ...+ xn ≥ n.$

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

Попробуем доказать это по индукции.

1. База индукции. При $n= 1$ мы имеем, что $x1 =1,$ следовательно просто из условия следует, что $x1 ≥ 1.$ Таким образом, база, очевидно, выполнена.

2. Шаг индукции. Пусть требуемое неравенство выполнено при всех $k= 1,2,3,...,n.$ Докажем его для $k = n+1 :$

Заметим, что нам дано по условию, что $x1 ⋅x2⋅...⋅xn⋅xn+1 = 1$
Рассмотрим тогда сумму $x1+ x2+ ...+ xn+ xn+1.$ Как доказать, что она больше, чем $n +1$ ? Давайте вспомним неравенство между средним арифметическим и средним геометрическим и применим его к нашим $x1,x2,...,xn,xn+1$ :

x1+x2+-..n.++x1n-+xn+1≥ n+1√x1-⋅x2⋅...⋅xn⋅xn+1

Однако, как мы сказали выше, наше произведение под корнем по условию равно 1: $x1⋅x2⋅...⋅xn ⋅xn+1 =1.$ Значит, имеем: $x1+x2+...n++1xn+xn+1≥ n+1√x1-⋅x2⋅...⋅xn⋅xn+1 = n+1√1= 1$
Таким образом, мы просто получаем, домножая на $n+ 1,$ что $x1+ x2+...+ xn+xn+1 ≥n +1$
И мы всё доказали.

Контрольный вопрос: А где здесь вообще была индукция? Пользовались ли мы ей явно?

Ответ:

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

Задача 8#35969

Доказать, что:
$-1- -1- -1-- n+1 + n+2 +...+ 3n+1 > 1$

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

Попробуем сделать это по индукции.
1. База индукции. При $n= 1$ в нашей сумме будет $3$ слагаемых: $1 1 1 1 12- 2 + 3 + 4 + +4 = 13 > 1.$ Отлично, значит базу индукции мы проверили.

2. Шаг индукции. Предположим, утверждение верно при всех натуральных числах до $k,$ то есть при 1, 2, 3,..., $k.$ Основываясь на этом предположении, докажем его для $k+ 1$ :
$1 1 1 1 1 1 1 1 1 1 k+2 +k+3 +...+ 3k+4-=(k+1 + k+2 + ...+ 3k+1)+ 3k+2-+ 3k+3 + 3k+4 − k+1 >$
$1 1 1 1 >1 +3k+2 + 3k+3 + 3k+4-−k+1.$

Неравенство мы имеем по предположению индукции.
Далее, понятно, что $1+ 3k1+2-+3k1+3 + 31k+4 − k1+1 =$
$=1 + (3k+3)(3k+4)(k+1)+(3k+2)(3k(3+k4+)2(k)(+3k1+)+3()(3k3+k+24))(3(kk++13))(k+1)−(3k+2)(3k+3)(3k+4)=$
$=1 +3(k+1)(3k2+2)(3k+4) > 1.$

Значит, мы доказали, что $k1+2 + k1+3 + ...+ 3k1+4 > 1.$

Ответ:

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

Задача 9#35968

Докажите, что число $n5− n$ кратно $5.$

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

Давайте попробуем разложить наше выражение на множители. Сначала просто выносим $n,$ а затем используем два раза формулу разности квадратов. С учётом этого, имеем:

5 4 2 2 2 n − n= n(n − 1)= n(n − 1)(n +1)= n(n − 1)(n +1)(n +1)

Далее, надо просто рассмотреть случаи:
1. Если $n$ кратно 5, то всё уже хорошо. Тогда и наше произведение кратно 5, так как первый множитель в нём - это и есть $n.$
2. Если $n$ даёт остаток 1 при делении на 5, то, очевидно, скобка $(n− 1)$ делится на 5, а, значит, и всё наше произведение $2 n(n − 1)(n +1)(n +1).$
3. Если $n$ даёт остаток 2 при делении на 5, то $2 n$ даёт остаток 4, а, значит, $2 n +1$ уже делится на 5. Значит, вновь наше произведение делится на 5.
4. Если $n$ даёт остаток 3 при делении на 5, то $2 n$ даёт остаток 4 (потому что $2 n$ это будет $9$ в смысле остатка, а 9 даёт остаток 5), а, значит, $2 n +1$ уже делится на 5. Значит, вновь наше произведение делится на 5.
5. Если же, наконец, $n$ даёт остаток 4 при делении на 5, то скобка $(n +1)$ поделится на 5.
Поскольку в каждом из рассмотренных случаев получается, что выражение
$n(n− 1)(n+ 1)(n2+ 1)$ делится на 5, то и исходное выражение $n5− n$ - тоже. И мы всё доказали.

Ответ:

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

Задача 10#35853

Докажите, что:
Число $2 n(2n − 3n +1)$ кратно $6;$

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

Разложим на множители выражение в скобках, и тогда получим, что: $n(2n2 − 3n+ 1)=n(2n− 1)(n− 1).$ Очевидно, что числа $n$ и $n − 1$ имеют разную чётность, следовательно, хотя бы одно из них делится на $2.$ Значит и всё произведение $n(2n− 1)(n− 1)$ делится на $2.$

Кроме того, если cамо $n$ не кратно $3,$ то либо $n− 1$ (в случае, если $n$ даёт остаток $1$ при делении на $3$ ) , либо $2n− 1$ (в случае, если $n$ даёт остаток $2$ при делении на $3$ ) будет делиться на $3.$ Следовательно, и всё произведение кратно к тому же ещё и $3.$ А, значит, оно кратно $6,$ и мы, тем самым, всё доказали.

Ответ:

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

Задача 11#35851

Докажите, что неравенство $101n > 100n +99n$ справедливо при всех:
a) $n≥ 100;$ b) $n ≥ 49.$

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

a) Для простоты давайте поделим наше гипотетическое неравенство на $101n,$ и тогда получится, что оно равносильно вот такому: $100n 99-n (101) + (101) < 1.$ Действительно ли это так? Действительно ли эта сумма слева меньше 1?

Ну, давайте оценим её сверху, сказав, что второе слагаемое $99-n (101)$ меньше, чем первое $100n (101)$ (очевидно, при любом $n >0$ ): $99-n 100-n (101) < (101) .$
Но из такой оценки вытекает уже вот что: $100-n -99-n 100n 100n 100-n (101) + (101) < (101) +(101) =2⋅(101) .$
И это последнее выражение $100n 2 ⋅(101)$ меньше $1$ тогда и только тогда, когда $1 n> log110001 2.$ Этот логарифм приблизительно равен $70$ (убедитесь в этом сами), то есть мы доказали требуемое неравенство при $n> 70,$ и тем более при $n >100.$

b) Это уже гораздо более трудная задача. По сути, надо понять, когда выражение $(101001)n +(19901)n$ впервые становится меньше $1.$ Оно ведь монотонно убывает, поэтому надо найти эту граничную точку, то есть такое ближайшее $n,$ что до него у нас $(101001)n+ ( 91091)n < 1,$ а вот уже после него $(110001)n+ ( 91901)n > 1.$
Как его найти? Формально, надо найти такой $x∈ ℝ,$ что $(110001)x+ ( 91091)x = 1$ и взять ближайшее следующее целое $n$ к этому $x.$

Это не самая тривиальная задача: решить это уравнение аналитически. Но приближенно можно вычислить (например, методом деления отрезка пополам или методом Ньютона для функции $f(x)= (110001)x +( 91901)x− 1$ найти $x$ такой, что $f(x)= 0$ ), что $x≈ 48,2275,$ то есть уже начиная с $n =49$ наше неравенство будет выполняться, причём это наименьшее такое $n.$ Тем самым, мы доказали и пункт b).

Ответ:

Интенсивы

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

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

Задача 12#35330

Докажите неравенство Бернулли: $(1 + x)n ≥ 1+ nx$ при всех $x ≥ − 1$ и при всех натуральных $n.$

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

Докажем индукцией по $n$ при каждом фиксированном $x ≥ − 1.$
1. База индукции. При $n = 1$ это неравенство, очевидно, верно, причём вообще для любого $x ∈ ℝ,$ поскольку оно обращается в равенство.

2. Шаг индукции. Пусть это неравенство выполнено для всех чисел от $1$ до $n.$ Докажем его для $n + 1 :$ $n+1 n по предположению индукции для (1+ x)n (1 + x) = (1 + x)(1+ x ) ≥ (1+ x)(1 + nx) =$
$2 = 1 + nx + x+ nx2 так как≥ nx ≥0 1+ nx + x = 1 + (n+ 1)x$
Что и требовалось доказать.

Ответ:

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

Задача 13#35325

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$ :
$x по определ=ению xn+1 ax + b по предполож=ению индукции a(can + d)+ b = can+1 + ad + b. n+1 n$
Однако мы бы хотели, чтобы наше $xn+1$ имело вид $xn+1 = can+1 + d.$
Таким образом, у нас с одной стороны свободный член получился равным $ad + b,$ а с другой стороны он должен быть просто $d.$
Из этого условия и находим $d$ : $ad + b = d,$ значит, $b = d(1− a),$ откуда $d = -b-. 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$ и знаменателем $1 3.$ То есть, $n− 2 n−3 1 3n−2(1−(13)n−1)- 3n−1(1−(13)n−1)- 3 + 3 + ...+ 3 + 1 = 23 = 2 .$
Итого, имеем: $n− 1 1−(13)n−-1 n−1 1+(13)n−1 3n−1+1- xn = 3 (1 − 2 ) = 3 ( 2 ) = 2 .$

Ответ:

Предыдущий раздел

Следующий раздел