Страница 118 номер 242, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни

Сумма зависит от \(n\): при \(n = 4\), когда \(k = 2\), она равна \(C_4^0 + C_3^1 + C_2^2 = 1 + 3 + 1 = 5\), то есть равна числу \(F_5 = F_{n+1}\), — это равенство и докажем.

Обозначим сумму из условия через \(S_n\); количество слагаемых в ней задаётся числом \(k\), равным \(\dfrac{n}{2}\) при чётном \(n\) и \(\dfrac{n-1}{2}\) при нечётном:

\[S_n = C_n^0 + C_{n-1}^1 + C_{n-2}^2 + \ldots + C_{n-k}^k.\]

Числа Фибоначчи связаны равенствами \(F_1 = 1\), \(F_2 = 1\) и \(F_m = F_{m-1} + F_{m-2}\) при \(m \geqslant 3\). Докажем индукцией по \(n\), что \(S_n = F_{n+1}\) при всех натуральных \(n\). Каждое число Фибоначчи выражается через два предыдущих, поэтому баз у индукции две.

База. При \(n = 1\) число \(k\) равно нулю, и сумма состоит из одного слагаемого: \(S_1 = C_1^0 = 1\), а \(F_2 = 1\). При \(n = 2\) число \(k\) равно единице: \(S_2 = C_2^0 + C_1^1 = 1 + 1 = 2\), а \(F_3 = F_2 + F_1 = 2\). В обоих случаях \(S_n = F_{n+1}\).

Шаг. Пусть \(n \geqslant 3\) и равенство уже доказано для чисел \(n - 2\) и \(n - 1\), то есть \(S_{n-2} = F_{n-1}\) и \(S_{n-1} = F_n\). Достаточно доказать, что \(S_n = S_{n-2} + S_{n-1}\): тогда \(S_n = F_{n-1} + F_n = F_{n+1}\).

Основное рекуррентное свойство чисел сочетаний раскладывает слагаемое \(C_{n-j}^j\) на два:

\[C_{n-j}^j = C_{n-j-1}^{j-1} + C_{n-j-1}^j.\]

Свойство применимо, когда верхний индекс больше нуля и меньше нижнего, то есть при \(0 < j < n - j\). Чётный и нечётный случаи разбираем порознь: от чётности \(n\) зависит и число \(k\), и то, какое слагаемое в сумме последнее.

Нечётное \(n\). Здесь \(k = \dfrac{n-1}{2}\), и последнее слагаемое суммы \(S_n\) равно \(C_{k+1}^k\), потому что \(n - k = k + 1\). Для каждого номера \(j\) от 1 до \(k\) нижний индекс больше верхнего: \(n - j \geqslant n - k = k + 1 > j\), поэтому раскладывается каждое слагаемое, кроме первого. Сложив полученные равенства и прибавив первое слагаемое \(C_n^0\), получаем \(S_n\) в виде суммы двух групп чисел.

Первая группа — числа \(C_{n-j-1}^{j-1}\) при \(j\) от 1 до \(k\), то есть \(C_{n-2}^0\), \(C_{n-3}^1\), …, \(C_{n-k-1}^{k-1}\). Число \(n - 2\) нечётно, и последнему слагаемому суммы \(S_{n-2}\) отвечает номер \(\dfrac{n-3}{2} = k - 1\), поэтому первая группа — это в точности сумма \(S_{n-2}\).

Вторая группа — число \(C_n^0\) и числа \(C_{n-j-1}^j\) при \(j\) от 1 до \(k\). Так как \(C_n^0 = C_{n-1}^0 = 1\), эта группа равна \(C_{n-1}^0 + C_{n-2}^1 + \ldots + C_{n-k-1}^k\). Число \(n - 1\) чётно, и последнему слагаемому суммы \(S_{n-1}\) отвечает номер \(\dfrac{n-1}{2} = k\), поэтому вторая группа — это сумма \(S_{n-1}\).

Чётное \(n\). Здесь \(k = \dfrac{n}{2}\), и последнее слагаемое суммы \(S_n\) равно \(C_{n-k}^k = C_k^k = 1\): у него верхний индекс равен нижнему, так что рекуррентное свойство к нему неприменимо. Отложим это слагаемое в сторону, заметив, что \(C_k^k = C_{k-1}^{k-1} = 1\). Для номеров \(j\) от 1 до \(k - 1\) нижний индекс больше верхнего: \(n - j \geqslant n - k + 1 = k + 1 > j\), поэтому остальные слагаемые, кроме первого, раскладываются. Как и в нечётном случае, числа правых частей вместе с \(C_n^0\) разбиваются на две группы.

Первая группа — числа \(C_{n-j-1}^{j-1}\) при \(j\) от 1 до \(k - 1\), то есть \(C_{n-2}^0\), \(C_{n-3}^1\), …, \(C_{n-k}^{k-2}\), и вместе с ними отложенное слагаемое. Разность \(n - k - 1\) равна \(k - 1\), поэтому отложенное слагаемое \(C_{k-1}^{k-1}\) — это число \(C_{n-k-1}^{k-1}\), и вся группа равна \(C_{n-2}^0 + C_{n-3}^1 + \ldots + C_{n-k-1}^{k-1}\). Число \(n - 2\) чётно, и последнему слагаемому суммы \(S_{n-2}\) отвечает номер \(\dfrac{n-2}{2} = k - 1\), поэтому первая группа — это сумма \(S_{n-2}\).

Вторая группа — число \(C_n^0 = C_{n-1}^0\) и числа \(C_{n-j-1}^j\) при \(j\) от 1 до \(k - 1\), то есть \(C_{n-1}^0 + C_{n-2}^1 + \ldots + C_{n-k}^{k-1}\). Число \(n - 1\) нечётно, и последнему слагаемому суммы \(S_{n-1}\) отвечает номер \(\dfrac{n-2}{2} = k - 1\), поэтому вторая группа — это сумма \(S_{n-1}\).

В обоих случаях \(S_n = S_{n-2} + S_{n-1} = F_{n-1} + F_n = F_{n+1}\). Обе базы проверены, шаг доказан, поэтому равенство верно при всех натуральных \(n\).

Ответ: равенство \(C_n^0 + C_{n-1}^1 + C_{n-2}^2 + \ldots + C_{n-k}^k = F_{n+1}\) доказано.