Дискретная математика для будущего учителя математики (стр. 3 )

Если это уравнение имеет кратные корни, например , где s≤k, а все остальные корни различны, то общее решение соотношения (15) имеет вид , где - некоторые константы. Доказательство см. в [50].

Задача 2.2. Найти общее решение рекуррентного соотношения над полем комплексных чисел аn+3+10аn+2+32аn+1+32аn=0.

Решение. Характеристическое уравнение этого соотношения x3+10x2+32x+32=0 не может иметь положительных корней.

Так как над полем комплексных чисел x3+10x2+32x+32=, то целые корни должны быть делителями свободного члена 32=l1l2l3. Проверку, то есть деление многочлена P(x) на можно проводить и «уголком», однако удобнее использовать схему Горнера. В данном случае в качестве делителей можно попробовать (–1), затем (–2), (–4) и так далее.

Значение l=–2 оказалось корнем, и при делении (x3+10x2+32x+32) на (x+2) получился многочлен (x2+8x+16). Дальнейший поиск корней производился уже для этого многочлена. В итоге получились корни l1=–2 и l2=l3 =–4.

Следовательно, (x3+10x2+32x+32)=(x+2)(x+4)2, то есть кратность первого корня r1=1, а второго – r2=2.

Поэтому общее решение имеет члены вида an = c1(–2)n + (c2 + c3n) (–4)n.

Задача 2.3. Найти формулу n-ого члена последовательности Фибоначчи, заданной соотношением при начальных условиях .

Это соотношение является линейным рекуррентным соотношением второго порядка с коэффициентами . Характеристическое уравнение является квадратным , корни которого различны . Общее решение исходного соотношения примет вид: . Учитывая заданные начальные условия , имеем . Отсюда . Следовательно, формула для n-го члена последовательности Фибоначчи примет вид

(16).

На первый взгляд кажется удивительным, что это выражение при всех натуральных значениях n принимает целые значения: 0,1,1,2,3,5,8,13,... Но это становится более понятным, если заметить, что после раскрытия всех скобок выражение будет иметь вид , но при замене на выражение не изменится (поменяет знак и первый сомножитель, и квадратная скобка), поэтому всегда будет .

Числа Фибоначчи обладают целым рядом замечательных свойств. Рассмотрим некоторые из них.

1)  Сумма первых n чисел Фибоначчи для равна

(17)

Первый способ доказательства основан на методе математической индукции: Для n=1 равенство верно. Пусть утверждение (17) верно для некоторого натурального n=k, т. е. имеем .

Прибавляя к обеим частям последнего равенства k+1, получим , а это как раз и есть соотношение (17) при n=k+1. По принципу математической индукции, утверждение (17) справедливо при любом натуральном n.

В основе второго способа доказательства лежит рекуррентное соотношение, определяющее последовательность чисел Фибоначчи. В самом деле, из соотношения имеем:

,

,

,

…

,

.

Сложив все эти равенства почленно, получим доказываемое:

.

2)  Сумма квадратов двух соседних чисел Фибоначчи снова является числом Фибоначчи

Доказательство. В самом деле, из формулы (16) следует, что

Поэтому

Формула (16) называется формулой Бине по имени получившего ее французского математика Жака Бине ().

Заметим, что число φ= играет важную роль не только во многих разделах математике, но и в искусстве, где оно считается самым благоприятным с эстетической точки зрения отношением. Это число связано с золотым сечением. Обозначается оно буквой φ в честь греческого скульптора Фидия (нач. V в. до н. э.–ок. 432-431 до н. э.), впервые сознательно использовавшего это отношение для скульптурного убранства Парфенона.

Числа Фибоначчи и золотое сечение удивительно широко распространены в Природе, Науке и Искусстве (см. [8], [26], [43], [54]).

Задача 2.4. (МИФИ): Последовательность чисел такова, что .

Найти число .

Решение: применяя описанную выше методику решения линейных рекуррентных соотношений с постоянными кооэфициентами, формула для n-го члена последовательности примет вид .

Читателю предлагаем воспользоваться указанным методом самостоятельно и проверить наши выводы.

Отсюда находим искомое число

Ответ: 182.

§3. Конечные суммы

«Сколько будет один плюс один плюс один плюс один плюс один плюс один плюс один плюс один плюс один плюс один?» - спросил кролик. «Не знаю» - ответила Алиса - «Я сбилась со счета». «Она не умеет складывать!» [34]. Льюис Кэрролл (), настоящее имя и фамилия Чарлз Латуидж Доджсон, английский писатель, математик и логик

СУММЫ ВЕЗДЕСУЩИ не только в математике, но и в ряде других наук.

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

Мы часто используем готовые формулы для ряда нужных нам сумм, например, известные со школы формулы суммы членов арифметической или геометрической прогрессии, суммы квадратов первых натуральных чисел и т. д. Но не всегда знаем, как они получены, и какие, вообще, существуют методы суммирования конечных сумм.

Дискретная математика дает целый арсенал методов для исчисления конечных сумм. Учитель имеет возможность выбрать любой метод в зависимости от своих целей. Рассмотрим ряд некоторых из них.

1.метод. Метод преобразования сумм

Суть этого метода заключается в том, что для исчисления конечных сумм мы применяем известные три закона преобразования сумм: распределительный, сочетательный и переместительный.

Пример. Рассмотрим ряд подходов к выводу формулы для суммы (n+1) первых членов любой арифметической прогрессии.

1 подход. Рассмотрим сумму 1+2+3+…+n первых n натуральных чисел в двух видах:

Складывая эти равенства почленно, мы видим, что числа, стоящие на одной вертикали, вместе составляют (n+1), и так как вертикалей всего имеется n, то отсюда следует, что , и остается еще разделить на 2.

(18)

Из формулы (18) сразу же вытекает общая формула для суммы (n+1) первых членов любой арифметической прогрессии:

.

В самом деле,

В случае, когда a=0, d=1, последнее соотношение превращается в соотношение (18).

2 подход. Вычислим сумму (n+1) первых членов любой арифметической прогрессии общего вида (19) применяя законы преобразования конечных сумм.

Согласно переместительному закону, заменив k на (n-k), получим

(20)

Равенства (19) и (20) почленно сложим, используя сочетательный закон, имеем .

А теперь применим распределительный закон и вычислим тривиальную сумму .

Отсюда получаем формулу для суммы (n+1) первых членов любой арифметической прогрессии

.

2 метод. Метод приведения

Суть этого метода заключается в том, чтобы начать с подлежащей вычислению суммы и обозначить ее . Затем мы переписываем двумя способами, выделяя как последний, так и первый члены:

(21)

Теперь можно заняться последней суммой и попытаться выразить ее через . Если попытка окажется удачной, то мы получим уравнение, решением которого и будет искомая сумма.

Воспользуемся, к примеру, этим подходом для нахождения суммы (n+1) первых членов любой геометрической прогрессии общего вида

(22)

В соответствии с общей схемой приведения (21) сумма переписывается в виде , а сумма в правой части по распределительному закону равна .

Таким образом, , и, разрешая это уравнение относительно , получаем известную нам со школы формулу

.

3 метод. Метод неопределенных коэффициентов

Суть метода сводится к тому, чтобы сумму свести к сигма-рекуррентному соотношению: , где - многочлен степени k относительно n. Тогда можно искать сумму методом неопределенных коэффициентов в виде , где - многочлен степени (k+1) – на единицу большей, чем степень многочлена .

Например, найдем методом неопределенных коэффициентов сумму квадратов первых n натуральных чисел

. (23)

Ищем в виде .

Тогда из соотношения (23) получим

, откуда

.

Итак, .

При n=1 получим , поэтому .

Окончательно .

4 метод. Метод усложнения и упрощения

Метод усложнения и упрощения заключается в замене исходной суммы более сложной на первый взгляд двойной суммой (в общем случае, кратной суммой), которая в действительности может быть упрощена, если преобразовать ее как надо:

5 метод. Метод интегральной оценки

Интегральная оценка, для суммы следующая .

Рассмотрим погрешность полученной оценки: . Так как, сумма удовлетворяет сигма-рекуррентному соотношению , то погрешность удовлетворяет следующему сигма-рекуррентному соотношению

.

Это соотношение сводится к сумме

.

Прибавив найденную погрешность к оценке , мы получим искомую сумму .

6 метод. Формула суммирования Эйлера-Маклорена

При составлении компьютерных программ весьма важно знать, насколько эффективно будет работать тот или иной алгоритм.

Можно предположить, что на вводе в компьютер данная конкретная задача имеет размер n. Например, этим числом может оцениваться объём памяти, задействованной под программу. Время работы программы, очевидно, будет зависеть от n, то есть получается функция t(n), оценивающая сложность программы. Если эта функция является многочленом (полиномом), то соответствующий алгоритм называется полиномиальным. В настоящее время принято считать, что на практике такие алгоритмы являются наиболее эффективными.

С другой стороны, известны алгоритмы, сложность которых для задач достаточно большого объёма превосходит любую полиномиальную оценку. Обычно эти алгоритмы называют экспоненциальными. Например, алгоритмы, сложность которых оценивается функциями kn (k>1), n!, , nn и тому подобными.

Из таблицы 3 становится ясным различие между полиномиальными и экспоненциальными алгоритмами. Предполагается, что компьютер выполняет 107 операций в секунду, а приблизительные времена вычислений обоих алгоритмов сравнимы для различных размеров проблемы.

Таблица 3. Время выполнения алгоритмов

Сложность алгоритма	Размер проблемы
n = 10	n = 40	n = 70
n2	0,00001 сек.	0,00016 сек.	0,00049 сек.
2n	0,0001 сек.	30,5 час.	37436 веков

Очевидно, что в последнем случае бессильными оказываются и самые современные компьютеры. Поэтому весьма важно знать оценку таких комбинаторных чисел, которые встречаются наиболее часто. Первым шагом к решению этой проблемы явились исследования швейцарского математика Леонарда Эйлера ().

Л. Эйлер рассматривал задачу об отыскании или оценке суммы вида

f(0)+f(1)+f(2)+...+f(n)

для некоторой непрерывной функции f(x). Он получил следующую формулу:

f(0)+f(1)+f(2)+...+f(n)~[f(0)+f(n)]+, где [x] – целая часть числа x. Этот метод является общим методом аппроксимации сумм, который был впервые опубликован Л. Эйлером в 1738 г. и, независимо от него, в 1742 г. К. Маклореном.

Общая формула суммирования Эйлера-Маклоренна выглядит так:

, где (24)

Выражение в правой части зачастую оказывается превосходной аппроксимацией суммы в левой части, в том смысле, что остаток очень мал. Формула (24) сводит вместе следующие понятия: a и b – произвольные целые числа, ; m – произвольное натуральное число; f(x) – непрерывная на отрезке [a,b] функция, обладающая на интервале (a,b) производными до m-го порядка включительно; числа - числа Бернулли; функция - многочлен Бернулли. Вывод этой формулы в нескольких эквивалентных формулировках приводится в [50].

Пример. Для вычисления знакомой нам уже суммы с помощью формулы Эйлера-Маклорена, необходимо рассмотреть следующую степенную функцию , тогда и формула (24) сведется к следующей:

Так, для m=3 получим

§4. Производящие функции. Числа Каталана

Ценность изученных знаний заключается не в их количестве, а в умении их использовать

При решении конкретных задач вместо последовательностей зачастую бывает гораздо удобнее иметь дело с функциями, что позволяет применять хорошо известные методы математического анализа. Этот метод заключается в переходе от последовательностей к функциям. Он используется для вычисления комбинаторных чисел и доказательства комбинаторных тождеств.

Пусть дана некоторая последовательность чисел a0, a1, a2, ..., an… Образуем степенной ряд a(х)= (25).

Если этот ряд сходится в какой-то области к функции a(х), то функцию a(х) называют производящей для последовательности чисел a0, a1, a2, ..., an...

Из математического анализа известны разложения следующих функций в степенной ряд:

, (26)

, (27)

(28) и др.

Производящей функцией последовательности чисел 1,1,1,… является степенной ряд , который можно записать в виде явной формулы .

Над производящими функциями можно производить действия, аналогичные действиям над степенными рядами (см. [1], [9], [17], [43]).

Рассмотрим любопытные примеры, приводящие к рекуррентным линейным соотношениям с переменными коэффициентами, которые связаны с числами Каталана.

Задача 4.1. (Л. Эйлер). Найти число способов разбиения на треугольники выпуклого (n+2)-угольника его диагоналями (триангуляция), которые не пересекаются внутри этого многоугольника, при n³1.

Такие числа и получили название числа Каталана.

Решение: Пусть вершины данного выпуклого (n+2)-угольника (n³1) занумерованы числами 1, 2, …, n+2. Можно обозначить через аn число разбиений этого многоугольника на треугольники диагоналями, которые внутри него не пересекаются. Чтобы составить рекуррентное соотношение для этого числа нужно рассмотреть два случая:

1) Если через вершину с номером 1 не проходит диагональ, то в любое разбиение многоугольника входит треугольник с вершинами 1, 2 и (n+2). В этом случае вершину 1 следует исключить и рассматривать разбиения (n+1)-угольника.

2) Пусть существуют диагонали, проходящие через вершину с номером 1. Среди них можно выбрать диагональ, соединяющую вершины 1 и (k+2), где 1£k£n–1 и k – наименьшее. Тогда разбиение будет содержать треугольник с вершинами 1, 2 и (k+2). По одну сторону этого треугольника располагается (k+1)-угольник, а по другую – многоугольник с числом вершин, равным (n+2–k), так как концы диагонали будут двумя общими вершинами треугольника и многоугольника.

В этом случае число разбиений (n+2)-угольника равно произведению чисел разбиений двух этих многоугольников, то есть аk-1аn-k.

Если принять а0=а1=1, то, учитывая оба случая, можно получить следующее рекуррентное соотношение аn=а0аn-1+а1аn-2+…+аn-2а1+аn-1а0.

Далее следует найти квадрат производящей функции a(x)=:

(а0+а1x+а2x2+…+аnxn+…)(а0+а1x+а2x2+…+аnxn+…)=а0а0+(а0а1+а1а0)x+(а0а2+

+а1а1+а2а0)x2+(а0а3+а1а2+а2а1+а3а0)x3+…=а1+а2x+а3x2+…+аnxn-1+…=[a(x)]2.

Из получившегося равенства вытекает квадратное уравнение x[a(x)]2=a(x)–1.

Решением этого квадратного уравнения является функция

a(x)=.

Теперь для вычисления {аn} нужно представить эту функцию в виде степенного ряда. По формуле (26) имеем

Учитывая, что 2k–1(k–1)!=2×4×6×…×(2k–2) получим:

Подставляя найденное значение в формулу для производящей функции, получим a(x)= Ясно, что знак «+» из «±» не подходит, так как левая часть не содержит x в отрицательной степени. Поэтому окончательно получается a(x)=

Здесь коэффициенты при различных степенях x являются числами Каталана. Следовательно, эти числа образуют последовательность с членами

аn=

Задача 4.2. (расстановка скобок). Найти число всех способов перемножения n чисел, стоящих в заданном порядке.

Другими словами, сколькими способами можно расставить скобки в ?

Пусть аn – число способов расстановки скобок для .

Очевидно, а0=0, а1=1, а2=1. При n=3 – два способа , т. е. а3=2. При n=4, ответ затруднителен …

Попробуем для числа аn составить рекуррентное соотношение. Для этого в произведении расставим сначала скобки для первых k чисел (k<n), а затем для последних (n-k) чисел:

аk способов здесь расставить скобки

аn-k способов расставить скобки

Учитывая комбинаторные правила суммы и произведения, получим рекуррентное соотношение , n≥2.

Тогда .

Как получить явную формулу для аn?

Для этого обратимся к производящим функциям и найдем квадрат производящей функции a(x)=:

(а0+а1x+а2x2+…+аnxn+…)(а0+а1x+а2x2+…+аnxn+…)=

=а0а0+(а0а1+а1а0)x+(а0а2+а1а1+а2а0)x2+(а0а3+а1а2+а2а1+а3а0)x3+…

+(а0аn+а1аn-1+…+аn-1а1+аnа0)xn+…=а2x2+ а3x3…+аnxn+…=a2(x).

Из получившегося равенства вытекает квадратное уравнение

Решением этого квадратного уравнения является функция a(x)=. Поскольку a(0)=0, выбираем перед корнем знак минус.

Воспользуемся результатами разложения функции a(x) в степенной ряд, полученными в задаче 4.2:

Подставляя найденное значение в формулу для производящей функции, получим a(x)==.

Здесь коэффициенты при различных степенях x образуют последовательность чисел Каталана n-ый член которой равен аn=.