Метод математической индукции: Пусть P(n) - высказывание, зависящее от n. Если верно P(1) (<em>база индукции</em>), а также из того, что утверждение P(k) верно при всех k < n (<em>предположение индукции</em>) следует, что выполняется P(n) (<em>индукционный переход</em>), то P(n) выполняется при всех натуральных n.
Дальше почти без слов краткие решения (слова нужны, их надо выписывать из того, что написано выше):
3. Обозначение: число из n единиц =
[email protected] База:
[email protected] = 3 делится на 3.
Переход:
[email protected](3^n) = 1000 *
[email protected](3^(n - 1)) + 111,
[email protected](3^(n - 1)) по предположению делится на 3, 111 делится на 3, тогда всё делится на 3.
4. База: 1^3 + 2^3 + 3^3 = 36 делится на 9.
Переход. n^3 + (n + 1)^3 + (n + 2)^3 = ((n - 1)^3 + n^3 + (n + 1)^3) + 9(n^2 + n + 1). Первое по предположению делится на 9, второе делится на 9, тогда всё делится на 9.
5. База: 1 = 2^0, 2 = 2^1.
Переход: 2^k <= n < 2^(k + 1). n - 2^k < 2^(k + 1) - 2^k = 2^k - по предположению n - 2^k можно разложить на различные степени 2, притом все они меньше 2^k, т.к. n - 2^k < 2^k. Тогда n = (разложение n - 2^k) + 2^k.
6. База: 8 = 3 + 5
Переход: если в разложении n - 1 есть хотя бы одна пятерка, меняем 5 на 3 + 3 = 6, получаем n. Если там одни трёшки, то их не меньше трёх, меняем 3 + 3 + 3 = 9 на 5 + 5 = 10, получаем n.
Ответ: можно.
7. База: 1 = F(1), 2 = F(3).
Переход. F(k) <= n < F(k + 1), n - F(k) < F(k + 1) - F(k) = F(k - 1); по предположению n - F(k) раскладывается, при этом в разложении все слагаемые меньше F(k) (и даже меньше F(k - 1)). Тогда разложение для n = (разложение для n - F(k)) + F(k).