Доказать что n 3 n делится на 6 для любого натурального n

18.04.202223.04.2022 admin 0 Comments

Методом математической индукции доказать

Доказать методом математической индукции
Нужно доказать утверждение методом математической индукции. Дошёл до того, что осталось доказать.

Доказать методом математической индукции
Помогите пожалуйста доказать методом мат.индукции. Доказать, что 3^(3n+2) + 2^(4n+1) кратно 11.

Метод математической индукции
Есть какое-то утверждение. Доказали, что оно верно для n=1 и n=k+2, можно ли утверждать, что.

(n+1) 3 +5(n+1)= n 3 +3n 2 +3n+1+5n+5=(n 3 +5n)+3n 2 +3n+6.

То, что стоит в скобках, делится на 6 (по предположению индукции). Выражение 3n 2 +3n=3n(n+1).
Но из двух чисел n и (n+1) одно точно четное. Поэтому 3n 2 +3n делится на 6. Собственно, все.

Метод математической индукции
Докажите с помощью математической индукции, что для любого натурального числа n, число 3^(2n+3) +.

Доказательство метода математической индукции
Я пытался найти доказательство самого метода математической индукции, но не нашёл. Может вы сможете.

Доказать клаузу методом резолюций, методом Вонга и аксиоматическим методом
Очень прошу вас помочь разобраться в доказательстве клауз этими методами. Хочется понять именно.

Источник

Доказать что n 3 n делится на 6 для любого натурального n

3) Шаг индукции: докажем, что утверждение верно для n = k+1, т. е.

Пример 15. Доказать, что для любого натурального n число n 3 + 5n делится на 6.

Доказательство. База индукции имеется: при n = 1 число n 3 + 5n = 6 делится на 6. Предполагаем, что для некоторого k число k 3 + 5k делится на 6. Используя это, постараемся доказать, что тогда и (k + 1) 3 + 5(k + 1) делится на 6. Проведём преобразования:

(k + 1) 3 + 5(k + 1) = k 3 + 3k 2 + 3k + 1 + 5k + 5 = = (k 3 + 5k) + (3k 2 + 3k) + 6 = (k 3 + 5k) + 3k(k + 1) + 6.

Первое слагаемое в этой сумме делится на 6 по предположению, второе слагаемое тоже делится на 6, так как из чисел k, k + 1 одно обязательно чётно. Значит, вся сумма делится на 6, что и требовалось доказать.

В качестве ещё одного примера докажем теорему о числе подмножеств конечного множества.

Теорема 4. Множество, состоящее из n элементов, имеет 2 n различных подмножеств.

Доказательство. Применим индукцию по числу n. Если множество A = <а>состоит из одного элемента, то его подмножества — это 0, <а>. Их 2, поэтому теорема при n = 1 верна (база индукции). Предполагаем, что любое множество из k элементов имеет 2k подмножеств. Рассмотрим множество

Все его подмножества разделим на 2 вида. К первому виду отнесём подмножества, не содержащие ак+1. По предположению, таких подмножеств 2к. Остальные подмножества содержат ак+1, их количество также равно 2к, потому что каждое из них получается добавлением ак+1 к одному из подмножеств первого вида. Всего подмножеств множества A имеется:

Источник

Доказать что n 3 n делится на 6 для любого натурального n

Задача 15:

Найдите остатки от деления

а) 1989 1990 1991 + 1992³ на 7;

Решение:

Ответ: а) 0; б) 1, так как 9 дает остаток 1 при делении на 8.

Задача 16:

Докажите, что n³ + 2n делится на 3 для любого натурального n.

Решение:

Число n может давать при делении на 3 один из трех остатков: 0, 1, 2. Рассмотрим три случая.

Если n дает остаток 0, то и n³ и 2n делятся на 3 и поэтому n³ + 2n также делится на 3.

Если n дает остаток 1, то n³ дает остаток 1, 2n – остаток 2, а 1 + 2 делится на 3.

Если n дает остаток 2, то n² дает остаток 1, n³ – остаток 2, 2n – остаток 1, а 2 + 1 делится на 3.

Задача 17:

Докажите, что n 5 + 4n делится на 5 при любом натуральном n.

Решение:

Указание: Переберите остатки от деления на 5.

Задача 18:

Докажите, что n² + 1 не делится на 3 ни при каком натуральном n.

Решение:

Переберите остатки от деления на 3.

Задача 19:

Докажите, что n³ + 2 не делится на 9 ни при каком натуральном n.

Решение:

Переберите остатки от деления на 9.

Задача 20:

Докажите, что n³ – n делится на 24 при любом нечетном n.

Решение:

Указание: Докажите, что указанное число делится и на 3, и на 8.

Задача 21:

а) Докажите, что p² – 1 делится на 24, если p – простое число и p > 3.

б) Докажите, что p² – q² делится на 24, если p и q – простые числа, большие 3.

Решение:

Указание: Докажите, что указанные числа делятся и на 3 и на 8.

Задача 22:

Натуральные числа x, y, z таковы, что x² + y² = z². Докажите, что хотя бы одно из этих чисел делится на 3.

Решение:

Если ни x, ни y не делятся на 3, то x² и y² дают остаток 1 от деления на 3. Таким образом, их сумма имеет остаток 2 от деления на 3. Но z² не может иметь такого остатка.

Задача 23:

a и b – натуральные числа, причем число a² + b² делится на 21. Докажите, что оно делится и на 441.

Решение:

Проверьте, что и a и b делятся и на 3 и на 7.

Задача 24:

a, b, c – натуральные числа, причем a + b + c делится на 6. Докажите, что a³ + b³ + c³ тоже делится на 6.

Решение:

Проверьте, что числа x³ и x имеют одинаковые остатки от деления на 6.

Задача 25:

Три простых числа p, q и r, большие 3, образуют арифметическую прогрессию: p = p, q = p + d, r = p + 2d. Докажите, что d делится на 6.

Решение:

Если d – нечетно, то среди чисел p и q есть четное, что невозможно. Если d не делится на 3, то среди чисел p, q и r есть делящееся на 3, что тоже невозможно.

Задача 26:

Докажите, что сумма квадратов трех натуральных чисел, уменьшенная на 7, не делится на 8.

Решение:

Выясните возможные остатки квадратов при делении на 8.

Задача 27:

Сумма трех натуральных чисел, являющихся точными квадратами, делится на 9. Докажите, что из них можно выбрать два, разность которых также делится на 9.

Решение:

Возможные остатки квадратов от деления на 9: 0, 1, 4, 7. Проверьте, что если сумма трех из них делится на 9, то среди них есть два одинаковых.

Задача 28:

Решение:

Так как при нахождении последней цифры очередной степени числа 9 достаточно умножить на 9 лишь последнюю цифру предыдущей степени, то ясно, что за 9 следует 1 (9 9 = 81), а за 1 – 9 (1 9 = 9).

Таким образом, нечетные степени девятки оканчиваются на 9. Поэтому последняя цифра числа 1989 1989 – девятка.

Задача 29:

Решение:

Выпишем последние цифры нескольких начальных степеней двойки: 2, 4, 8, 6, 2, …. Мы видим, что 2 5 так же, как и 2¹, оканчивается на 2. Поскольку очередная цифра полностью определяется последней цифрой предыдущей степени, то произойдет «зацикливание»: 2 6 (как и 2²) оканчивается на 4, 2 7 (как и 2³) – на 8, 2 8 – на 6, 2 9 – на 2 и т.д. Поскольку длина цикла равна 4, то последняя цифра числа 2 50 определяется остатком от деления числа 50 на 4. Так как он равен 2, то последняя цифра числа 2 50 совпадает с последней цифрой числа 2², то есть равна 4.

Задача 30:

Решение:

Задача 31:

Найдите остаток от деления 2¹ºº на 3.

Решение:

Выпишите остатки от деления на 3 нескольких начальных степеней двойки. Докажите, что здесь происходит «зацикливание».

Задача 32:

Найдите остаток от деления 3 1989 на 7.

Решение:

Задача 33:

Докажите, что 2222 5555 + 5555²²²² делится на 7.

Решение:

Вычислите остаток от деления этого числа на 7 и убедитесь, что он равен нулю.

Задача 34:

Найдите последнюю цифру числа .

Задача 35:

а) p, p + 10, p + 14 – простые числа. Найдите p.

б) p, 2p + 1, 4p + 1 – простые числа. Найдите p.

Решение:

Рассмотрите остатки от деления на 3. Одно из этих чисел делится на 3. а) p = 3; б) p = 3.

Задача 36:

p и 8p² + 1 – простые числа. Найдите p.

Решение:

Задача 37:

p и p² + 2 – простые числа. Докажите, что p³ + 2 – также простое число.

Решение:

Задача 38:

Докажите, что не существует натуральных чисел a и b таких, что a² – 3b² = 8.

Решение:

Рассмотрите остатки по модулю 3.

Задача 39:

а) Может ли сумма квадратов двух нечетных чисел быть квадратом целого числа?

б) Может ли сумма квадратов трех нечетных чисел быть квадратом целого числа?

Решение:

Проверьте, что остаток квадрата нечетного числа от деления на 4 равен 1, а остаток квадрата четного числа – 0.

Задача 40:

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

Решение:

Проверьте, что остаток квадрата нечетного числа от деления на 4 равен 1, а остаток квадрата четного числа – 0.

Задача 41:

p, 4p² + 1 и 6p² + 1 – простые числа. Найдите p.

Ответ: p = 5. Рассмотрите остатки при делении на 5.

Задача 42:

Докажите, что число 100 … 00500 … 001 (в каждой из двух групп по 100 нулей) не является кубом целого числа.

Решение:

Это число дает остаток 7 от деления на 9.

Задача 43:

Докажите, что a³ + b³ + 4 не является кубом целого числа ни при каких натуральных a и b.

Решение:

Выясните, какой остаток может давать число a³ + b³ + 4 от деления на 9.

Задача 44:

Докажите, что число 6n³ + 3 не является шестой степенью целого числа ни при каком натуральном n.

Решение:

Выясните, какой остаток может давать число 6n³ + 3 от деления на 7.

Задача 45:

x, y, z – натуральные числа, причем x² + y² = z². Докажите, что xy делится на 12.

Решение:

Если ни одно из чисел x, y не делится на 3, то z² дает остаток 2 при делении на 3, что невозможно. Заметьте теперь, что квадрат нечетного числа при делении на 8 дает остаток 1, квадрат четного числа, не делящегося на 4, – остаток 4, квадрат числа, делящегося на 4, – остаток 0. Докажите, что либо x и y оба четны, либо среди них есть число, кратное 4.

Источник

Метод математической индукции

Метод математической индукции

Способ доказательства методом математической индукции заключается в следующем:

1) Начало индукции. Доказывают или непосредственно проверяют справедливость утверждения ( формулы ) для n=1;

2) Индуктивный переход. Предполагают справедливость утверждения для некоторого натурального n=k .

3) Исходя из этого предположения, доказывают справедливость утверждения для n=k+1.

Ясно, что метод математической индукции (в дальнейшем м. м.и.) можно применять только для доказательства утверждений, зависящих от натурального n.

Задачи на делимость натуральных чисел часто предлагаются на математических олимпиадах разного уровня. Многие из них легко доказываются м. м.и.

1. Проверим, если n = 1, получим 13 + 2· 1 = 3 делится на 3

2. Предположим, что делится при n = к, т. е. к3+ 2к делится на 3.

3. Докажем, что при n = к + 1 полученное выражение тоже делится на 3.

(к + 1)3+ 2(к + 1) = к3 + 3к2 + 3к + 1 + 2к + 2 = (к3 + 2к) + 3к2 + 3к + 3 делится на 3, т. к. каждое слагаемое делится на 3.

Доказать, что при любом натуральном n число

(впрочем, здесь начать можно и с n=0)

2) Пусть ak делится на 7.

3) Докажем справедливость утверждения для n=k+1 ak+1=32(k+1)+1+2(k+1)+2=32k+1 9+ 2k+2 2= (32k+1+2k+2)9-7 *2k+2=9ak-7*2k+2

2) предположим, что утверждение верно при некотором натуральном n=k, т. е. число 7k+1+82k-1 делится на 19.

3) Докажем верность утверждения для n=k+1

Так как каждое слагаемое полученной суммы делится на 19, то и 7k+2+82k+1 также делится на 19. Утверждение доказано.

Доказать, что при любом натуральном n число 23+1 делится на 3n+1

1) Для n=1 число 23+1=9 делится на 31+1=9

2) Пусть утверждение верно для n=k, т. е. 23+1 делится на 3k+1.

23+1=23+1=(23)3+1=(23+1)((23)2 – 23+1) делится на 3к+2

Задачи для самостоятельного решения (прислать решения на 1,2,4)

Докажите, что при всех натуральных n

1) n3 + 11n делится на 6

5) 5·23n-2 + 33n-1 делится на 19

Метод математической индукции

1) Проверим справедливость утверждения для n =1.

2) Предположим справедливость формулы для n=k, т.е.

3) докажем справедливость формулы для n=k+1

Задача Доказать, что 3n

1) Проверим справедливость утверждения для n =1. 3 ≥ 3

2) Предположим справедливость формулы для n=k, т.е. 3к

3) докажем справедливость формулы для n=k+1, т. е. 3к+1

3к+1 = 3· 3к ≥ 3() = (2 + 1)( ) = 2· 2к + 2к + 2к + к = (2к+1+ к + 1) + (2к + 2к – 1), значит, тем более 3к+1

Задача Доказать, что при n ≥ 2

2) Предположим справедливость формулы для n=k, т.е.

3) докажем справедливость формулы для n=k+1, т. е.

—

Рассмотрим выражение —= , значит, тем более

Задача 4. Вывести формулу суммы первых n нечетных чисел натурального ряда.

Замечаем, что сумма первых n нечётных чисел натурального ряда равна n2 т. е. S(n)=n2. Докажем это м. м.и.

1) для n =1 формула верна.

2) предположим, что она верна для какого-нибудь натурального n=k, т. е. S(k)= k2.

Докажем, что тогда она будет верна и для n=k+1, т. е. S(k+1)=(k+1)2

Следовательно, формула верна для всех натуральных значений n, т. е. S(n)=n2

Задача 5. Доказать, что сумма квадратов первых натуральных чисел равна

12 +22 +32 +42 +…+n2=

1) Проверим справедливость утверждения для n =1.

т. е. для n =1 формула верна.

2) Предположим справедливость формулы для n=k, т.е. S(k)=12+22+32+…+k2 =

3) Исходя из этого предположения докажем справедливость формулы для n=k+1

Действительно, S(k+1)=12+22+32+…+k2+(k+1)2. Сумма первых k слагаемых равна S(k)= Значит, S(k+1)=S(k)+ (k+1)2=

Итак, мы доказали, что формула верна для n=kМы получили ту же формулу. Следовательно, в силу м. м.и. данная формула верна для любого натурального n.

Задача 6. Доказать, что для всех натуральных n справедлива формула

13+23+33+…+n3=

1) при n =1 левая часть этой формулы принимает вид 13=1 ; правая часть принимает вид . Значит, при n =1 формула верна.

2) предположим, что формула верна при n=k, т. е. верно равенство 13+23+33+…+k3 =

Докажем, что тогда эта формула верна и при n=k+1 (каким бы ни было k ), т. е. верно равенство 13+23+…+k3+(k+1)3=

Для этого заметим, что левую часть доказываемого равенства можно записать в виде (13+23+33+…+k3)+(k+1)3

Но по предположению выражение в скобках равно ,

13+23+…+k3+(k+1)3= .

Значит, доказываемая формула верна при n =1, а из её справедливости при n=k вытекает, что она верна и при n=kВ силу м. м.и. отсюда вытекает справедливость этой формулы для всех натуральных значений n.

Задача 8. Доказать, что при всех натуральных n выполняется неравенство

Доказательство:Обозначим левую часть неравенства через an.

1) начало индукции. Справедливость неравенства при n=1 очевидна.

2) индуктивный переход. Пусть ak . Надо доказать, что ak+1. А поскольку ak+1= , то нам достаточно доказать неравенство . Возведя это неравенство в квадрат и упрощая, приходим к неравенству n.