Метод математической индукции: Пусть P(n) - высказывание, зависящее от n. Если верно P(1) (база индукции), а также из того, что утверждение P(k) верно при всех k < n (предположение индукции) следует, что выполняется P(n) (индукционный переход), то 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.<br>
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).