Спирина, М.С. Дискретная математика

После упрощения получим к 3 + 4 к 2 +8Л + 3 _ к +2 (Зк + \)(к + \)(к +2) ~ Зк +4 ' Левая и правая части оказались различными, т.е. гипотеза не подтвердилась. Но из того, что доказать не удалось, не следует неправильность гипотезы. Например, технический арсенал д о ­ казывающего может быть недостаточен. Чтобы себя проверить, посмотрим на каком -нибудь небольшом к , например к = 4. 5 4 _ 1-2 + 2- 3 + 3- 4 1 4-5 4 5 ’ 4 + 3-5 + Д - . А вот это уже до- 1о стоверно гарантирует, что формула S„ = я + I не выполняется i n + 1 для любого п е N. При применении метода математической индукции одинаково важны все этапы алгоритма: первый этап — база индукции дает возможность определить нижнюю границу применения формулы или действия неравен­ ства. В то же время мы проверяем справедливость этой формулы или неравенства для первого элемента множества. Второй этап — шаг к обобщению, который формулируется в виде гипотезы, справедливой для всех п = к. Этот этап называют индуктивным переходом или индуктивной фазой, т.е. от одного частного случая мы перешли к обобщению для п = к. На третьем этапе мы должны установить, насколько сильны индуктивные выводы: либо убедиться в их справедливости, либо их опровергнуть для значения, следующего за обобщенным, т.е. для к' = к+ 1. Это так называемая фаза доказательства. ММИ широко применяется для доказательства делимости чи ­ сел. Задача 29. Доказать, что 62я- 1 кратно 35. Решение. Проверим справедливость утверждения при п= 1. Име­ ем 62 1- 1 = 36 - 1 = 35, действительно делится на 35. Делимость нацело принято обозначать в виде (62 1- 1): 35. Гипотеза: пусть при п = к справедливо (62* - 1) •35. Докажем тогда, что при п = к + 1 верно (62(*+1)- 1) ■35. Имеем (j 2 (*+l)_ 1 = 62*+2 _ J = 62* • 62- 1 = 36 • б2* - 1. Чтобы доказать делимость, необходимо в выражении «увидеть» нашу гипотезу. Для этого к нему одновременно добавим и вычтем число 36. Пос­ ле группировки и вынесения общего множителя имеем 36 62* - - 1 = (36 • 62* - 36) + 3 6 - 1 = 36(62А—1) + 35. В полученном выражении каждое слагаемое делится на 35. Дей­ ствительно, произведение 36 • (62* - 1) кратно 35 по гипотезе. Так как второе слагаемое тоже делится на 35, то и вся сумма кратна 35, что и следовало доказать. 10 Д искретная математика 273