При работе с циклами на уроках информатики, учащиеся должны уметь доказывать правильность составленных циклов. Параметр цикла с известным числом повторений, а также описание табличной величины можно легко связать с методом математической индукции. Один из методов составления циклических алгоритмов является метод рекуррентных соотношений. Этот метод по своей сути очень близок методу математической индукции. И поэтому очень удобно вводить это понятие после изучения цикла с параметром и метода рекуррентных соотношений.
Образовательная цель – дать понятие принципа математической индукции как аксиомы, дать понятие сути метода математической индукции и способа доказательства методом математической индукции правильности работы циклов.
Воспитательная цель – научить применять метод для доказательства правильности циклов, развить способность к сравнению похожих методов и умение выделять сходные элементы в работе цикла и способе доказательства методом математической индукции.
Практическая цель – формирование навыков составления циклических алгоритмов, используя метод математической индукции, а также их последующей проверки с помощью компьютера.
Изучение метода математической индукции проводится в 3 этапа: введение, усвоение, закрепление.
1 этап Введение.
Вводить понятие метода математической индукции лучше сразу после изучения цикла “для” (с известным числом повторений). Введение проводится методом аналогии, сравнивая метод математической индукции и метод рекуррентных соотношений.
Занятия можно начать с задачи.
Задача 1. Даны две последовательности:
а) 1 2 6 24 120 720 5040…
б) 1 4 11 26 57 120 247 …
Найдите закономерность по которой составлены последовательности и допишите несколько членов каждой последовательности.
Ребята легко заметят, что в последовательности а) 1=1; 2=2*1; 6=1*2*3; 24=1*2*3*4 и т.д. и сделав вывод, что каждый следующий член получается умножением предыдущего на число порядкового номера члена последовательности, они добавят 5040*7=35280, 35280*8=282160 и т.д. Ученикам останется напомнить, что так вычисляется факториал числа и перед ними ни что иное как последовательность факториалов: 1! 2! 3! 4! 5! 6! 7!…, только вместо самих факториалов записаны их значения.
В последовательности б) ребятам можно подсказать обратить внимание на разность рядом стоящих членов, и тогда они заметят, что: 1=1; 4=1*2+2; 11=2*4+3; 26=11*2+4 и т.д. Следующие члены допишутся так: 247*2+8; (247*2+8)*2+9 и т.д. После этого хорошо видно, что каждый член последовательности получается из предыдущего по определенной закономерности. А значит, можно обе закономерности записать в виде формулы.
Для
а) ai=ai-1*i
б) ai=2ai-1+i
Соотношения в которых следующий член выражается через предыдущий называется рекуррентным соотношением. Это учащиеся уже знают, так как встречались с этим понятием при работе с циклами и табличными величинами.
Приводится несколько примеров рекуррентных соотношений:
Пример 1. арифметическая прогрессия ai=ai-1+d
Пример 2. последовательность Фибоначчи a1=a2=1
ai=ai-1+ai-2
Пример 3. последовательность факториалов a1=1
ai=ai-1*i
Рекуррентные соотношения удобно использовать при составлении алгоритмов вычисления значений величин. Метод составления алгоритмов, в котором используются рекуррентные соотношения, называется методом рекуррентных соотношений.
Задача 2.
Составим алгоритм для вычисления n-го члена последовательности 2 3 5 9 17, используя для запоминания членов последовательности таблицу.
Решение. Составим рекуррентное соотношение
Задача 3.
Вычисление n! с запоминанием всех полученных значений в таблице.
Суть метода рекуррентных соотношений в том, что следующее значение некоторой величины выражается через её предыдущее значение, а значение предыдущего соответственно через его предыдущее значение и т.д. То есть, чтобы вычислить n-ый член, надо вычислить n-минус первое значение этой величины шаг за шагом, снизу вверх, один за другим.
Метод рекуррентных соотношений очень похож на метод математической индукции.
После этого даётся понятие метода математической индукции и принципа математической индукции как аксиома:
Имеется М 
N и 1 М, а из n M —> n + 1 M} —> M = N
Метод в следующем: если есть цепочка
утверждений, зависящих от n N и первое истинно, а истинность n-го влечёт
истинность n+1, то высказывание истинно при любом
натуральном n.
Истинность первого предположения – это база
индукции, a 
n P(n)=U —> P(n+1) = U
– это шаг индукции.
! Предложим ребятам сравнить метод математической индукции с только то изученным методом рекуррентных соотношений. Они легко заметят, что роль базы индукции в методе рекуррентных соотношений играет начальное значение вычисляемой величины, а роль шага индукции играет рекуррентное соотношение.
Выделим существенные свойства метода математической индукции, сравнивая с этапами составления циклических алгоритмов.
- Необходимо, чтобы была база индукции, то есть было истинно первое утверждение, либо найдено начальное значение вычисляемой величины, или она была бы задана.
- Необходимо, чтобы истинность предыдущего влекла истинность следующего, то есть выполнялось рекуррентное соотношение.
- Доказано утверждение, которое истинно при любом n. Причём можно заметить, что оно в течение доказательства остаётся неизменным на " шагу, а это инвариант в информатике.
Инвариант – это неизменное условие, которое соблюдается после каждого выполнения тела цикла.
2 этап Усвоение.
Если у нас алгоритм составлен с помощью метода рекуррентных соотношений, то в цикле имеется инвариант.
Задача 4. Выведем формулу суммы первых n нечётных чисел натурального ряда. Докажем эту формулу с помощью метода математической индукции.
Решение.
…
Докажем эту формулу.
- Для n=1 S(1)=12 истина
- Предположим, что верна для n=к т.е. S(к)=к2 истина
- Докажем, что верна для n=к+1
т.е. S(к+1)=(к+1)2 ?
S(к+1)=1+3+5+…+(2к-1)+(2к+1)= S(к)+(2к+1)=к2+2к+1=(к+1)2
Теперь для сравнения методов составим рекуррентное соотношение.
S[1] =1
Si=Si-1+2*i+1
Формула S(n)= n2 – здесь играет роль инварианта. Так как доказано, что условие неизменно. Для доказательства этого факта рассматриваем как ведет себя цикл на первом шаге и на втором, третьем и следующих. Если выполнение тела цикла не влияет на условие, то это инвариант.
Для усвоения этой аналогии учащимся предлагаются следующие задачи:
Задача 1. Выведите формулу суммы
Докажите эту формулу методом математической индукции. После доказательства составим соотношение для членов суммы.
Имея все эти формулы, составляется алгоритм для нахождения суммы, который не будет нуждаться в дополнительной проверке и его работу можно проверить на компьютере.
Задача 2. Докажите правильность алгоритма вычисления среднего из n чисел, находящихся в таблице из n членов.
Применение метода математической индукции в свою очередь имеет ряд особенностей. А именно такого рода индивидуальные заключения справедливы тогда и только когда верна база индукции и верен индуктивный переход от к-1 к к.
Нарушение одного из этих двух условий может привести к получению неверных выводов. Наиболее часто это проявляется в построении циклов, когда неверно организуется либо начальные условия для выполнения вычислений в цикле, либо вычисления внутри цикла противоречат индуктивным утверждениям о требуемых промежуточных результатах. Для иллюстрации этого рассматриваются циклические алгоритмы (программы) с ошибками.
Чтобы обнаружить ошибку ученикам предлагается доказать правильность алгоритма (программы) с помощью метода математической индукции. Во время доказательства они обнаруживают ошибку. Для закрепления можно также предложить ребятам написать тот же алгоритм без ошибки.
В качестве упражнений для усвоения применения метода математической индукции можно предложить следующие задачи:
Задача 3. Составьте программу (алгоритм) поиска максимального числа в таблице и докажите его правильность.
Задача 4. Составьте программу (алгоритм) поиска заданного числа в таблице и докажите его правильность.
Задача 5. Составьте алгоритм подсчета суммы:
а) положительных элементов таблицы;
б) отрицательных элементов таблицы;
и докажите его правильность.
В задачах 3-5 варьируются задания с обработкой таблицы, но основной упор надо сделать на доказательстве алгоритмов методом математической индукции. Для проверки верности доказательства полученные алгоритмы можно проверить на компьютере.
3 этап Закрепление.
На этом этапе можно отойти от информатики и
перейти к математике и применению метода
математической индукции для доказательства
утверждений, формул и выражений зависящих от n N .
Каждую из задач перевести на язык программирования и показать что доказанный алгоритм выполняется без ошибок, т.е. после доказательства методом математической индукции доказывать правильность работы цикла ненужная работа.
Используя доказательства методом математической индукции, мы во-первых проверяем правильность задания начальных условий и вычислений внутри цикла, а также определяем инвариант, что позволяет легче понять цепь составления того или иного циклического алгоритма.
Для упражнений на закрепление можно взять следующие задачи:
Задача 1. Докажите, что сумма членов каждой строки таблицы равна квадрату нечетного числа, номер которого в строке равен номеру строки от начала таблицы.
| 1 | ||||||
| 2 | 3 | 4 | ||||
| 3 | 4 | 5 | 6 | 7 | ||
| 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| ... | ... | ... |
Решение:
Общий член последовательности, т.е. n-я строка, может быть записана так:
n n+1 n+2 … n+( n-1)*2.
Значит, последний член в этой строке равен 3 n-2. Надо доказать, что сумма чисел этой строки равна S(n)=(2 n-1)2
Для n=1 формула верна.
Предположим, что формула верна для некоторого натурального значения n=к, т.е.
S(к)=к+(к+1)+(к+2)+…+(3к-2)=(2к-1)2.
Докажем, что тогда она верна и для n=к+1:
S(к+1)=(к+1)+(к+2)+…+(3к-2)+(3к-1)+3к+(3к+1)=к+(к+1)+(к+2)+…+(3к-2)+(3к-1)+3к+(3к+1)-к= S(к)+(3к-1)+3к+(3к+1)-к=(2к-1)2+8к=4к2-4к+1+8к=4к2+4к+1=(2к+1)2 ч.т.д.
Задача 2. Найдите сумму
Задача 3 Докажите, что
Задача 3. Докажите, что для любого натурального числа справедливо равенство:
Задача 4. Докажите, что при любом натуральном числе большем 3 справедливо неравенство
Эти задачи носят обучающий характер. Целью их решения является закрепление навыков работы с методом математической индукции. Решения этих задач идентичны.