N 2n решение. Старт в науке
Если предложение А(n), зависящее от натурального числа n, истинно для n=1 и из того, что оно истинно для n=k (где k-любое натуральное число), следует, что оно истинно и для следующего числа n=k+1, то предположение А(n) истинно для любого натурального числа n.
В ряде случаев бывает нужно доказать справедливость некоторого утверждения не для всех натуральных чисел, а лишь для n>p, где p-фиксированное натуральное число. В этом случае принцип математической индукции формулируется следующим образом.
Если предложение А(n) истинно при n=p и если А(k) Ю А(k+1) для любого k>p, то предложение А(n) истинно для любого n>p.
Доказательство по методу математической индукции проводиться следующим образом. Сначала доказываемое утверждение проверяется для n=1, т.е. устанавливается истинность высказывания А(1). Эту часть доказательства называют базисом индукции. Затем следует часть доказательства, называемая индукционным шагом. В этой части доказывают справедливость утверждения для n=k+1 в предположении справедливости утверждения для n=k (предположение индукции), т.е. доказывают, что А(k) Ю A(k+1)
Доказать, что 1+3+5+…+(2n-1)=n 2 .
- 1) Имеем n=1=1 2 . Следовательно, утверждение верно при n=1, т.е. А(1) истинно
- 2) Докажем, что А(k) Ю A(k+1)
Пусть k-любое натуральное число и пусть утверждение справедливо для n=k, т.е
1+3+5+…+(2k-1)=k 2
Докажем, что тогда утверждение справедливо и для следующего натурального числа n=k+1, т.е. что
- 1+3+5+…+(2k+1)=(k+1) 2 В самом деле,
- 1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2
Итак, А(k) Ю А(k+1). На основании принципа математической индукции заключаем, что предположение А(n) истинно для любого n О N
Доказать, что
1+х+х 2 +х 3 +…+х n =(х n+1 -1)/(х-1), где х № 1
- 1) При n=1 получаем
- 1+х=(х 2 -1)/(х-1)=(х-1)(х+1)/(х-1)=х+1
следовательно, при n=1 формула верна; А(1) истинно
- 2) Пусть k-любое натуральное число и пусть формула верна при n=k,
- 1+х+х 2 +х 3 +…+х k =(х k+1 -1)/(х-1)
Докажем, что тогда выполняется равенство
- 1+х+х 2 +х 3 +…+х k +x k+1 =(x k+2 -1)/(х-1) В самом деле
- 1+х+х 2 +x 3 +…+х k +x k+1 =(1+x+x 2 +x 3 +…+x k)+x k+1 =
=(x k+1 -1)/(x-1)+x k+1 =(x k+2 -1)/(x-1)
Итак, А(k) Ю A(k+1). На основании принципа математической индукции заключаем, что формула верна для любого натурального числа n
Доказать, что число диагоналей выпуклого n-угольника равно n(n-3)/2
Решение: 1) При n=3 утверждение справедливо, ибо в треугольнике
А 3 =3(3-3)/2=0 диагоналей; А 2 А(3) истинно
2) Предположим, что во всяком выпуклом k-угольнике имеет А 1 ся А k =k(k-3)/2 диагоналей. А k Докажем, что тогда в выпуклом А k+1 (k+1)-угольнике число диагоналей А k+1 =(k+1)(k-2)/2.
Пусть А 1 А 2 А 3 …A k A k+1 -выпуклый (k+1)-угольник. Проведём в нём диагональ A 1 A k . Чтобы подсчитать общее число диагоналей этого (k+1)-угольника нужно подсчитать число диагоналей в k-угольнике A 1 A 2 …A k , прибавить к полученному числу k-2, т.е. число диагоналей (k+1)-угольника, исходящих из вершины А k+1 , и, кроме того, следует учесть диагональ А 1 А k
Таким образом,
G k+1 =G k +(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2
Итак, А(k) Ю A(k+1). Вследствие принципа математической индукции утверждение верно для любого выпуклого n-угольника.
Доказать, что при любом n справедливо утверждение:
1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6
Решение: 1) Пусть n=1, тогда
Х 1 =1 2 =1(1+1)(2+1)/6=1
2) Предположим, что n=k
Х k =k 2 =k(k+1)(2k+1)/6
3) Рассмотрим данное утвержде-ние при n=k+1
X k+1 =(k+1)(k+2)(2k+3)/6
X k+1 =1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =k(k+1)(2k+1)/6+ +(k+1) 2
=(k(k+1)(2k+1)+6(k+1) 2)/6=(k+1)(k(2k+1)+
6(k+1))/6=(k+1)(2k 2 +7k+6)/6=(k+1)(2(k+3/2)(k+
2))/6=(k+1)(k+2)(2k+3)/6
Мы доказали справедливость равенства и при n=k+1, следовательно, в силу метода математической индукции, утверждение верно для любого натурального n
Доказать, что для любого натурального n справедливо равенство:
1 3 +2 3 +3 3 +…+n 3 =n 2 (n+1) 2 /4
Решение: 1) Пусть n=1
Тогда Х 1 =1 3 =1 2 (1+1) 2 /4=1. Мы видим, что при n=1 утверждение верно.
2) Предположим, что равенство верно при n=k
X k =k 2 (k+1) 2 /4
3) Докажем истинность этого утверждения для n=k+1, т.е
Х k+1 =(k+1) 2 (k+2) 2 /4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k++1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4
Из приведённого доказательства видно, что утверждение верно при n=k+1, следовательно, равенство верно при любом натуральном n
Доказать, что
((2 3 +1)/(2 3 -1)) ґ ((3 3 +1)/(3 3 -1)) ґ … ґ ((n 3 +1)/(n 3 -1))=3n(n+1)/2(n 2 +n+1), где n>2
Решение: 1) При n=2 тождество выглядит:
- (2 3 +1)/(2 3 -1)=(3 ґ 2 ґ 3)/2(2 2 +2+1), т.е. оно верно
- 2) Предположим, что выражение верно при n=k
- (2 3 +1)/(2 3 -1) ґ … ґ (k 3 +1)/(k 3 -1)=3k(k+1)/2(k 2 +k+1)
- 3) Докажем верность выражения при n=k+1
- (((2 3 +1)/(2 3 -1)) ґ … ґ ((k 3 +1)/(k 3 -1))) ґ (((k+1) 3 +
1)/((k+1) 3 -1))=(3k(k+1)/2(k 2 +k+1)) ґ ((k+2)((k+
1) 2 -(k+1)+1)/k((k+1) 2 +(k+1)+1))=3(k+1)(k+2)/2 ґ
ґ ((k+1) 2 +(k+1)+1)
Мы доказали справедливость равенства и при n=k+1, следовательно, в силу метода математической индукции, утверждение верно для любого n>2
Доказать, что
1 3 -2 3 +3 3 -4 3 +…+(2n-1) 3 -(2n) 3 =-n 2 (4n+3) для любого натурального n
Решение: 1) Пусть n=1, тогда
- 1 3 -2 3 =-1 3 (4+3); -7=-7
- 2) Предположим, что n=k, тогда
- 1 3 -2 3 +3 3 -4 3 +…+(2k-1) 3 -(2k) 3 =-k 2 (4k+3)
- 3) Докажем истинность этого утверждения при n=k+1
- (1 3 -2 3 +…+(2k-1) 3 -(2k) 3)+(2k+1) 3 -(2k+2) 3 =-k 2 (4k+3)+
+(2k+1) 3 -(2k+2) 3 =-(k+1) 3 (4(k+1)+3)
Доказана и справедливость равенства при n=k+1, следовательно утверждение верно для любого натурального n.
Доказать верность тождества
(1 2 /1 ґ 3)+(2 2 /3 ґ 5)+…+(n 2 /(2n-1) ґ (2n+1))=n(n+1)/2(2n+1) для любого натурального n
- 1) При n=1 тождество верно 1 2 /1 ґ 3=1(1+1)/2(2+1)
- 2) Предположим, что при n=k
- (1 2 /1 ґ 3)+…+(k 2 /(2k-1) ґ (2k+1))=k(k+1)/2(2k+1)
- 3) Докажем, что тождество верно при n=k+1
- (1 2 /1 ґ 3)+…+(k 2 /(2k-1)(2k+1))+(k+1) 2 /(2k+1)(2k+3)=(k(k+1)/2(2k+1))+((k+1) 2 /(2k+1)(2k+3))=((k+1)/(2k+1)) ґ ((k/2)+((k+1)/(2k+3)))=(k+1)(k+2) ґ (2k+1)/2(2k+1)(2k+3)=(k+1)(k+2)/2(2(k+1)+1)
Из приведённого доказательства видно, что утверждение верно при любом натуральном n.
Доказать, что (11 n+2 +12 2n+1) делится на 133 без остатка
Решение: 1) Пусть n=1, тогда
11 3 +12 3 =(11+12)(11 2 -132+12 2)=23 ґ 133
Но (23 ґ 133) делится на 133 без остатка, значит при n=1 утверждение верно; А(1) истинно.
- 2) Предположим, что (11 k+2 +12 2k+1) делится на 133 без остатка
- 3) Докажем, что в таком случае (11 k+3 +12 2k+3) делится на 133 без остатка. В самом деле
- 11 k+3 +12 2л+3 =11 ґ 11 k+2 +12 2 ґ 12 2k+1 =11 ґ 11 k+2 +
+(11+133) ґ 12 2k+1 =11(11 k+2 +12 2k+1)+133 ґ 12 2k+1
Полученная сумма делится на 133 без остатка, так как первое её слагаемое делится на 133 без остатка по предположению, а во втором одним из множителей выступает 133. Итак, А(k) Ю А(k+1). В силу метода математической индукции утверждение доказано
Доказать, что при любом n 7 n -1 делится на 6 без остатка
- 1) Пусть n=1, тогда Х 1 =7 1 -1=6 де-лится на 6 без остатка. Значит при n=1 утвержде-ние верно
- 2) Предположим, что при n=k 7 k -1 делится на 6 без остатка
- 3) Докажем, что утверждение справедливо для n=k+1
X k+1 =7 k+1 -1=7 ґ 7 k -7+6=7(7 k -1)+6
Первое слагаемое делится на 6, поскольку 7 k -1 делится на 6 по предположению, а вторым слагаемым является 6. Значит 7 n -1 кратно 6 при любом натуральном n. В силу метода математической индукции утверждение доказано.
Доказать, что 3 3n-1 +2 4n-3 при произвольном натуральном n делится на 11.
1) Пусть n=1, тогда
Х 1 =3 3-1 +2 4-3 =3 2 +2 1 =11 делится на 11 без остатка.
Значит, при n=1 утверждение верно
- 2) Предположим, что при n=k X k =3 3k-1 +2 4k-3 делится на 11 без остатка
- 3) Докажем, что утверждение верно для n=k+1
X k+1 =3 3(k+1)-1 +2 4(k+1)-3 =3 3k+2 +2 4k+1 =3 3 ґ 3 3k-1 +2 4 ґ 2 4k-3 =
27 ґ 3 3k-1 +16 ґ 2 4k-3 =(16+11) ґ 3 3k-1 +16 ґ 2 4k-3 =16 ґ 3 3k-1 +
11 ґ 3 3k-1 +16 ґ 2 4k-3 =16(3 3k-1 +2 4k-3)+11 ґ 3 3k-1
Первое слагаемое делится на 11 без остатка, поскольку 3 3k-1 +2 4k-3 делится на 11 по предположению, второе делится на 11, потому что одним из его множителей есть число 11. Значит и сумма делится на 11 без остатка при любом натуральном n. В силу метода математической индукции утверждение доказано.
Доказать, что 11 2n -1 при произвольном натуральном n делится на 6 без остатка
- 1) Пусть n=1, тогда 11 2 -1=120 делится на 6 без остатка. Значит при n=1 утверждение верно
- 2) Предположим, что при n=k 1 2k -1 делится на 6 без остатка
- 11 2(k+1) -1=121 ґ 11 2k -1=120 ґ 11 2k +(11 2k -1)
Оба слагаемых делятся на 6 без остатка: первое содержит кратное 6-ти число 120, а второе делится на 6 без остатка по предположению. Значит и сумма делится на 6 без остатка. В силу метода математической индукции утверждение доказано.
Доказать, что 3 3n+3 -26n-27 при произвольном натуральном n делится на 26 2 (676) без остатка
Предварительно докажем, что 3 3n+3 -1 делится на 26 без остатка
- 1. При n=0
- 3 3 -1=26 делится на 26
- 2. Предположим, что при n=k
- 3 3k+3 -1 делится на 26
- 3. Докажем, что утверждение верно при n=k+1
- 3 3k+6 -1=27 ґ 3 3k+3 -1=26 ґ 3 3л+3 +(3 3k+3 -1) -делится на 26
Теперь проведём доказательство утверждения, сформулированного в условии задачи
- 1) Очевидно, что при n=1 утверждение верно
- 3 3+3 -26-27=676
- 2) Предположим, что при n=k выражение 3 3k+3 -26k-27 делится на 26 2 без остатка
- 3) Докажем, что утверждение верно при n=k+1
- 3 3k+6 -26(k+1)-27=26(3 3k+3 -1)+(3 3k+3 -26k-27)
Оба слагаемых делятся на 26 2 ; первое делится на 26 2 , потому что мы доказали делимость на 26 выражения, стоящего в скобках, а второе делится по предположению индукции. В силу метода математической индукции утверждение доказано
Доказать, что если n>2 и х>0, то справедливо неравенство (1+х) n >1+n ґ х
- 1) При n=2 неравенство справед-ливо, так как
- (1+х) 2 =1+2х+х 2 >1+2х
Значит, А(2) истинно
- 2) Докажем, что А(k) Ю A(k+1), если k> 2. Предположим, что А(k) истинно, т.е., что справедливо неравенство
- (1+х) k >1+k ґ x. (3)
Докажем, что тогда и А(k+1) истинно, т.е., что справедливо неравенство
(1+x) k+1 >1+(k+1) ґ x
В самом деле, умножив обе части неравенства (3) на положительное число 1+х, получим
(1+x) k+1 >(1+k ґ x)(1+x)
Рассмотрим правую часть последнего неравенства; имеем
(1+k ґ x)(1+x)=1+(k+1) ґ x+k ґ x 2 >1+(k+1) ґ x
В итоге получаем, что (1+х) k+1 >1+(k+1) ґ x
Итак, А(k) Ю A(k+1). На основании принципа математической индукции можно утверждать, что неравенство Бернулли справедливо для любого n> 2
Доказать, что справедливо неравенство (1+a+a 2) m > 1+m ґ a+(m(m+1)/2) ґ a 2 при а> 0
Решение: 1) При m=1
- (1+а+а 2) 1 > 1+а+(2/2) ґ а 2 обе части равны
- 2) Предположим, что при m=k
- (1+a+a 2) k >1+k ґ a+(k(k+1)/2) ґ a 2
- 3) Докажем, что при m=k+1 не-равенство верно
- (1+a+a 2) k+1 =(1+a+a 2)(1+a+a 2) k >(1+a+a 2)(1+k ґ a+
+(k(k+1)/2) ґ a 2)=1+(k+1) ґ a+((k(k+1)/2)+k+1) ґ a 2 +
+((k(k+1)/2)+k) ґ a 3 +(k(k+1)/2) ґ a 4 > 1+(k+1) ґ a+
+((k+1)(k+2)/2) ґ a 2
Мы доказали справедливость неравенства при m=k+1, следовательно, в силу метода математической индукции, неравенство справедливо для любого натурального m
Доказать, что при n>6 справедливо неравенство 3 n >n ґ 2 n+1
Перепишем неравенство в виде (3/2) n >2n
- 1. При n=7 имеем 3 7 /2 7 =2187/128>14=2 ґ 7 неравенство верно
- 2. Предположим, что при n=k (3/2) k >2k
- 3) Докажем верность неравенства при n=k+1
- 3 k+1 /2 k+1 =(3 k /2 k) ґ (3/2)>2k ґ (3/2)=3k>2(k+1)
Так как k>7, последнее неравенство очевидно.
В силу метода математической индукции неравенство справедливо для любого натурального n
Доказать, что при n>2 справедливо неравенство
1+(1/2 2)+(1/3 2)+…+(1/n 2)<1,7-(1/n)
- 1) При n=3 неравенство верно
- 1+(1/2 2)+(1/3 2)=245/180
- 2. Предположим, что при n=k
- 1+(1/2 2)+(1/3 2)+…+(1/k 2)=1,7-(1/k)
- 3) Докажем справедливость неравенства при n=k+1
- (1+(1/2 2)+…+(1/k 2))+(1/(k+1) 2)
Докажем, что 1,7-(1/k)+(1/(k+1) 2)<1,7-(1/k+1) Ы
Ы (1/(k+1) 2)+(1/k+1)<1/k Ы (k+2)/(k+1) 2 <1/k Ы
Ы k(k+2)<(k+1) 2 Ы k 2 +2k Последнее очевидно, а поэтому 1+(1/2 2)+(1/3 2)+…+(1/(k+1) 2)<1,7-(1/k+1) В силу метода математической индукции неравенство доказано. Вероятностный
подход к измерению информации
Количество
информации
i
,
содержащейся в сообщении о том, что
произошло одно из
N
равновероятных
событий, определяется из решения
уравнения:
N
= 2
i
(формула Хартли)
Как
решать задачи данного типа:
Задача
1.
В
рулетке общее количество лунок равно
128. Какое количество информации мы
получим, когда увидим, что шарик
остановился в одной из лунок? Решение:
Для
решения этой задачи воспользуемся
формулой N=2 I .
Если N=128, то I=7, т.к. 2 7 =
128. Ответ:
количество информации равно 7 битам. Решить:
1.Какое
количество информации несет в себе
сообщение о том, что нужная вам программа
находится на одном из 8 CD
дисков? 2.
Происходит
выбор одной карты из колоды в 32 карты.
Какое количество информации мы получим,
когда увидим, что выбрана определенная
карта? 3.
Сколько
существует различных последовательностей
из символов «плюс» и «минус», длиной
ровно в пять символов? Алфавитный
подход к определению количества
информации
Чтобы
определить объем информации в сообщении
при алфавитном подходе, нужно: Определить
количество информации (i) в одном символе
по формуле 2
i
= N
,
(где N - мощность алфавита) Определить
количество символов в сообщении (K) Вычислить
объем информации по формуле: V =
K
*
i
Единицы
измерения информации
1
байт=8 бит
1
Кбайт = 2
10
байт = 1024 байт
1
Мбайт = 2
10
Кбайт = 1024
2
байт = 1 048 576 байт
1
Гбайт = 2
10
Мбайт = 1024
3
байт
»
1 млрд. байт
Задача
1.
При
составлении сообщения использовали
128-символьный алфавит. Каким будет
информационный объем сообщения в
Кбайтах, если оно содержит 2048 символов. Решение:
Определим
количество информации (i)
в одном символе по формуле N=2 I .
Если N=128, то I=7, т.к. 2 7 =
128. Количество
символов в сообщении (K)
известно К=2048. Вычисли
объем информации по формуле: V =
K
*
I
=
2048*7 бит = (2048*7) /8 /1024 Кбайт =2*7/8 Кбайт =
1,75 Кбайт Ответ:
информационный объем сообщения равен
1,75 Кбайт 1.
При
составлении сообщения использовали
128-символьный алфавит. Каким будет
информационный объем сообщения в
Кбайтах, если оно содержит 2048 символов. 2.
Сообщение занимает 2 страницы. На каждой
странице по 80 строк, в каждой строке по
32 символа. Найдите информационный объем
такого текста, если при его составлении
использовали 256-символьный алфавит. 3.
Выразите
8 Мбайт в битах. 4
ответов
Нет, твоя идея неверна. Сложность O(n) также должна признать, что эта проблема сложна. Вот решение. T(n) = T(n-1) + T(n/2) + n . Поскольку вы вычисляете вещи для очень больших n , чем n-1 почти то же самое, что и n . Поэтому вы можете переписать его как T(n) = T(n) + T(n/2) + n И здесь я сделал ошибку, и неправильное решение начинается
: который равен T(n) = 1/2 * T(n/2) + n/2 . Как вы видите, сложность этой рекурсии будет супер-крошечной бит меньше первоначальной. Обратите внимание: здесь вы не можете использовать магистерскую теорему, потому что a < 1 . Вы можете начать разворачивать рекурсию. где последнее преобразование суммы, потому что это геометрическая прогрессия. Таким образом, рекурсия остановится в какое-то время, и вы можете просто выбрать точку, когда это произойдет. Я выбрал его, когда T(1) = b . Это происходит, когда n/2^k = 1 или n = 2^k , что означает, что k = log n . Если вы замените этот k в рекурсии, вы получите самый большой элемент, выполняемый как O(n) , и поэтому это время работы этого уравнения. Конец ошибки, начало правильного
который равен T(n/2) + n = 0 , который равен T(n) = - 2n , поэтому он является линейным. Это было противно интуитивно мне (знак минуса здесь), но вооруженный этим решением, я вижу, что решение функциональное уравнение T(n)=T(n-1)+T(n/2)+n что-то действительно близкое к -2n - 2 . Если вы введете его в уравнение, вы увидите, что для любого n он выключен только 1. Таким образом, решение все еще O(n) P.S. еще раз, очень странная рекурсия для класса CS. Я считаю, что ты прав. Отношение рекуррентности всегда будет разделяться на две части: Т (п-1) и Т (п/2). Глядя на эти два, ясно, что n-1 уменьшает значение медленнее, чем n/2, или, другими словами, у вас будет больше ветвей из n-1 части дерева. Несмотря на это, при рассмотрении big-o полезно рассмотреть сценарий "наихудшего случая", который в этом случае состоит в том, что обе стороны дерева уменьшаются на n-1 (так как это уменьшается медленнее, и вам нужно будет имеют больше веток). В общем, вам нужно разделить отношение на два в общей сложности n раз, следовательно, вы имеете право сказать O (2 ^ n). Ваши рассуждения верны, но вы отдаете слишком много. (Например, также правильно сказать, что 2x^3+4=O(2^n) , но это не так информативно, как 2x^3+4=O(x^3) .) Первое, что мы хотим сделать, это избавиться от неоднородного члена n . Это говорит о том, что мы можем искать решение формы T(n)=an+b . Подставляя это в, находим: An+b = a(n-1)+b + an/2+b + n
которая сводится к 0 = (a/2+1)n + (b-a)
подразумевая, что a=-2 и b=a=-2 . Поэтому T(n)=-2n-2 является решением уравнения. Теперь мы хотим найти другие решения, вычитая уже найденное решение. Давайте определим U(n)=T(n)+2n+2 . Тогда уравнение становится U(n)-2n-2 = U(n-1)-2(n-1)-2 + U(n/2)-2(n/2)-2 + n
которая сводится к U(n) = U(n-1) + U(n/2).
U(n)=0 является очевидным решением этого уравнения, но как ведут себя нетривиальные решения этого уравнения? Предположим, что U(n)∈Θ(n^k) для некоторого k>0 , так что U(n)=cn^k+o(n^k) . Это делает уравнение Cn^k+o(n^k) = c(n-1)^k+o((n-1)^k) + c(n/2)^k+o((n/2)^k)
Теперь (n-1)^k=n^k+Θ(n^{k-1}) , так что выше это будет Cn^k+o(n^k) = cn^k+Θ(cn^{k-1})+o(n^k+Θ(n^{k-1})) + cn^k/2^k+o((n/2)^k)
Абсорбируя члены младшего порядка и вычитая общий cn^k , мы приходим к O(n^k) = cn^k/2^k
Но это неверно, потому что правая сторона растет быстрее, чем левая. Следовательно, U(n-1)+U(n/2) растет быстрее, чем U(n) , что означает, что U(n) должен расти быстрее, чем наш предполагаемый Θ(n^k) . Так как это верно для любого k , U(n) должно расти быстрее, чем любой многочлен. Хорошим примером того, что растет быстрее любого полинома, является экспоненциальная функция. Следовательно, предположим, что U(n)∈Θ(c^n) для некоторого c>1 , так что U(n)=ac^n+o(c^n) . Это делает уравнение
ac ^ n + o (c ^ n) = ac ^ {n-1} + o (c ^ {n-1}) + ac ^ {n/2} + o (c ^ {n/2})
Переупорядочивая и используя некоторый порядок роста математики, это становится C^n = o(c^n)
Это ложь (снова), потому что левая сторона растет быстрее, чем правая. Следовательно,
U(n) растет быстрее, чем U(n-1)+U(n/2) , что означает, что U(n) должен расти медленнее, чем предполагаемый Θ(c^n) . Так как это верно для любого c>1 , U(n) должно расти медленнее любой экспоненты. Это ставит нас в область квазиполиномов, где ln U(n)∈O(log^c n) и субэкспоненциальности, где ln U(n)∈O(n^ε) . Любой из них означает, что мы хотим посмотреть L(n):=ln U(n) , где предыдущие параграфы подразумевают, что L(n)∈ω(ln n)∩o(n) . Взяв естественный логарифм нашего уравнения, имеем Ln U(n) = ln(U(n-1) + U(n/2)) = ln U(n-1) + ln(1+ U(n/2)/U(n-1))
L(n) = L(n-1) + ln(1 + e^{-L(n-1)+L(n/2)}) = L(n-1) + e^{-(L(n-1)-L(n/2))} + Θ(e^{-2(L(n-1)-L(n/2))})
Итак, все сводится к: как быстро растет L(n-1)-L(n/2) ? Мы знаем, что L(n-1)-L(n/2)→∞ , так как в противном случае L(n)∈Ω(n) . Вероятно, что L(n)-L(n/2) будет таким же полезным, поскольку L(n)-L(n-1)∈o(1) намного меньше L(n-1)-L(n/2) . К сожалению, это настолько далеко, насколько я способен решить эту проблему. Я не вижу хорошего способа контролировать, как быстро растет L(n)-L(n/2) (и я смотрел на это в течение нескольких месяцев). Единственное, что я могу закончить, это процитировать еще один ответ: "очень странная рекурсия для CS-класса". Текст работы размещён без изображений и формул. Введение
Данная тема является актуальной, так как каждый день люди решают различные задачи, в которых они применяют разные методы решения, но есть задания, в которых не обойтись без метода математической индукции, и в таких случаях будут очень полезны знания в данной области. Я выбрал данную тему для исследования, потому что в школьной программе методу математической индукции уделяют мало времени, ученик узнает поверхностнуюинформацию, которая поможетему получить лишь общее представление о данном методе, но чтобы углубленно изучить эту теорию потребуется саморазвитие. Действительно будет полезно поподробнее узнать о данной теме, так как это расширяет кругозор человека и помогает в решении сложных задач. Цель работы:
Познакомиться с методом математической индукции, систематизировать знания по данной теме и применить её при решении математических задач и доказательстве теорем, обосновать и наглядно показать практическое значение метода математической индукции как необходимого фактора для решения задач. Задачи работы:
Проанализировать литературу и обобщить знания по данной теме. Разобраться в принципе метода математической индукции. Исследовать применение метода математической индукции к решению задач. Сформулировать выводы и умозаключения по проделанной работе. Основная часть исследования
История возникновения:
Только к концу XIX века сложился стандарт требований к логической строгости, остающейся и до настоящего времени господствующими в практической работе математиков над развитием отдельных математических теорий. Индукция - познавательная процедура, посредством которой из сравнения наличных фактов выводится обобщающее их утверждение. В математике роль индукции в значительной степени состоит в том, что она лежит в основе выбираемой аксиоматики. После того как длительная практика показала, что прямой путь всегда короче кривого или ломанного, естественно было сформулировать аксиому: для любых трех точек А, В и С выполняется неравенство. Осознание метода математической индукции как отдельного важного метода восходит к Блезу Паскалю и Герсониду, хотя отдельные случаи применения встречаются ещё в античные времена у Прокла и Эвклида. Современное название метода было введено де Морганом в 1838 году. Метод математической индукции можно сравнить с прогрессом: мы начинаем с низшего, в результате логического мышления приходим к высшему. Человек всегда стремился к прогрессу, к умению логически развивать свою мысль, а значит, сама природа предначертала ему размышлять индуктивно. Индукция и дедукция
Известно, что существуют как частные, так и общие утверждения, и на переходе от одних к другим и основаны два данных термина. Дедукция (от лат. deductio - выведение) - переход в процессе познания от общего
знания к частному
и единичному
. В дедукции общее знание служит исходным пунктом рассуждения, и это общее знание предполагается «готовым», существующим. Особенность дедукции состоит в том, что истинность ее посылок гарантирует истинность заключения. Поэтому дедукция обладает огромной силой убеждения и широко применяется не только для доказательства теорем в математике, но и всюду, где необходимы достоверные знания. Индукция (от лат. inductio - наведение) - это переход в процессе познания от частного
знания к общему
.Другими словами, - это метод исследования, познания, связанный с обобщением результатов наблюдений и экспериментов.Особенностью индукции является ее вероятностный характер, т.е. при истинности исходных посылок заключение индукции только вероятно истинно и в конечном результате может оказаться как истинным, так и ложным. Полная и неполная индукция
Индуктивное умозаключение - такая форма абстрактного мышления, в которой мысль развивается от знания меньшей степени общности к знанию большей степени общности, а заключение, вытекающее из посылок, носит преимущественно вероятностный характер. В ходе исследования я выяснил, что индукция делится на два вида: полная и неполная. Полной индукцией называется умозаключение, в котором общий вывод о классе предметов делается на основании изучения всех предметов этого класса. Например,пусть требуется установить, что каждое натуральное чётное число n в пределах 6≤ n≤ 18 представимо в виде суммы двух простых чисел. Для этого возьмём все такие числа и выпишем соответствующие разложения: 6=3+3; 8=5+3; 10=7+3; 12=7+5;14=7+7; 16=11+5; 18=13+5; Данные равенства показывают, что каждое из интересующих нас чисел действительно представляется в виде суммы двух простых слагаемых. Рассмотрим следующий пример: последовательность yn= n 2 +n+17; Выпишем первые четыре члена: у 1 =19; y 2 =23; y 3 =29; y 4 =37; Тогда мы можем предположить, что вся последовательность состоит из простых чисел. Но это не так, возьмем y 16 = 16 2 +16+17=16(16+1)+17=17*17. Это составное число, значит наше предположение неверно, таким образом, неполная индукция не приводит к вполне надежным выводам, но позволяет сформулировать гипотезу, которая в дальнейшем требует математического доказательства или опровержения. Метод математической индукции
Полная индукция имеет в математике лишь ограниченное применение. Многие интересные математические утверждения охватывают бесконечное число частных случаев, а провести проверку для всех этих ситуаций мы не в состоянии.Но как осуществить проверку бесконечного числа случаев? Такой способ предложили Б.Паскаль и Я.Бернулли, это метод математической индукции, в основе которого лежит принцип математической индукции
. Если предложение А(n), зависящее от натурального числа n, истинно для n=1 и из того, что оно истинно для n=k (где k-любое натуральное число), следует, что оно истинно и для следующего числа n=k+1, то предположение А(n) истинно для любого натурального числа n.
В ряде случаев бывает нужно доказать справедливость некоторого утверждения не для всех натуральных чисел, а лишь для n>p, где p-фиксированное натуральное число. В этом случае принцип математической индукции формулируется следующим образом: Если предложение А(n) истинно при n=p и если А(k)
А(k+1) для любого k>p, то предложение А(n) истинно для любого n>p. Алгоритм (он состоит из четырех этапов):
1.база
(показываем, что доказываемое утверждение верно для некоторых простейших частных случаев (п
= 1)); 2.предположение
(предполагаем, что утверждение доказано для первых к
случаев); 3
.шаг
(в этом предположении доказываем утверждение для случая п
=
к
+ 1); 4.вывод (у
тверждение верно для всех случаев, то есть для всех п)
. Заметим, что Методом математической индукции можно решать не все задачи, а только задачи, параметризованные некоторой переменной. Эта переменная называется переменной индукции. Применение метода математической индукции
Применим всю данную теорию на практике и выясним, в каких задачах применяется данный метод. Задачи на доказательство неравенств.
Пример 1.
Доказать неравенство Бернулли(1+х)n≥1+n х, х>-1, n € N. 1) При n=1 неравенство справедливо, так как 1+х≥1+х 2) Предположим, что неравенство верно для некоторого n=k, т.е. (1+х) k ≥1+k x. Умножив обе части неравенства на положительное число 1+х, получим (1+x) k+1 ≥(1+kx)(1+ x) =1+(k+1) x + kx 2 Учитывая, что kx 2 ≥0, приходим к неравенству (1+х) k+1 ≥1+(k+1) x. Таким образом, из допущения, что неравенство Бернулли верно для n=k, следует, что оно верно для n=k+1. На основании метода математической индукции можно утверждать, что неравенство Бернулли справедливо для любого n € N. Пример 2.
Доказать, что при любом натуральном n>1, . Докажем с помощью метода математической индукции. Обозначим левую часть неравенства через. 1), следовательно, при n=2 неравенство справедливо. 2)Пусть при некоторомk. Докажем, что тогда и. Имеем, . Сравнивая и, имеем, т.е. . При любом натуральном k правая часть последнего равенства положительна. Поэтому. Но, значит, и.Мы доказали справедливость неравенства при n=k+1, следовательно, в силу метода математической индукции, неравенство справедливо для любого натурального n>1. Задачи на доказательство тождеств.
Пример 1.
Доказать, что для любого натурального n справедливо равенство: 1 3 +2 3 +3 3 +…+n 3 =n 2 (n+1) 2 /4. Пусть n=1, тогда Х 1 =1 3 =1 2 (1+1) 2 /4=1. Мы видим, что при n=1 утверждение верно. 2) Предположим, что равенство верно при n=kX k =k 2 (k+1) 2 /4. 3) Докажем истинность этого утверждения для n=k+1, т.е.X k+1 =(k+1) 2 (k+2) 2 /4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k+1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4. Из приведённого доказательства видно, что утверждение верно при n=k+1, следовательно, равенство верно при любом натуральном n. Пример 2.
Доказать, что при любом натуральном nсправедливо равенство 1) Проверим, что это тождество верно приn = 1.; - верно. 2) Пусть тождество верно и для n = k, т.е.. 3)Докажем, что это тождество верно и для n = k + 1, т.е.; Т.к. равенство верно при n=kи n=k+1, то оно справедливо при любом натуральном n. Задачи на суммирование.
Пример 1.
Доказать, что 1+3+5+…+(2n-1)=n 2 . Решение: 1) Имеем n=1=1 2 . Следовательно, утверждение верно при n=1, т.е. А(1) истинно. 2) Докажем, что А(k) A(k+1). Пусть k-любое натуральное число и пусть утверждение справедливо для n=k, т.е.1+3+5+…+(2k-1)=k 2 . Докажем, что тогда утверждение справедливо и для следующего натурального числа n=k+1, т.е. что 1+3+5+…+(2k+1)=(k+1) 2 . В самом деле,1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2 . Итак, А(k) А(k+1). На основании принципа математической индукции заключаем, что предположение А(n) истинно для любого n N. Пример 2.
Доказать формулу, n - натуральное число. Решение: При n=1 обе части равенства обращаются в единицу и, следовательно, первое условие принципа математической индукции выполнено. Предположим, что формула верна при n=k, т.е. . Прибавим к обеим частям этого равенства и преобразуем правую часть. Тогда получим Таким образом, из того, что формула верна при n=k, следует, что она верна и при n=k+1, то это утверждение справедливо при любом натуральном n. Задачи на делимость.
Пример 1.
Доказать, что (11 n+2 +12 2n+1) делится на 133 без остатка. Решение:
1) Пусть n=1, тогда 11 3 +12 3 =(11+12)(11 2 -132+12 2)=23× 133. (23× 133) делится на 133 без остатка, значит при n=1 утверждение верно; 2) Предположим, что (11 k+2 +12 2k+1) делится на 133 без остатка. 3) Докажем, что в таком случае (11 k+3 +12 2k+3) делится на 133 без остатка. Действительно, 11 k+3 +12 2л+3 =11×11 k+2 + 12 2 ×12 2k+1 =11× 11 k+2 +(11+133)× 12 2k+1 =11(11 k+2 +12 2k+1)+133× 12 2k+1 . Полученная сумма делится на 133 без остатка, так как первое её слагаемое делится на 133 без остатка по предположению, а во втором одним из множителей является 133. Итак, А(k)→ А(k+1), то опираясь на метод математической индукции, утверждение верно для любых натуральных n. Пример 2.
Доказать, что 3 3n-1 +2 4n-3 при произвольном натуральном n делится на 11. Решение: 1) Пусть n=1, тогдаХ 1 =3 3-1 +2 4-3 =3 2 +2 1 =11 делится на 11 без остатка. Значит, при n=1 утверждение верно. 2) Предположим, что при n=k X k =3 3k-1 +2 4k-3 делится на 11 без остатка. 3) Докажем, что утверждение верно для n=k+1. X k+1 =3 3(k+1)-1 +2 4(k+1)-3 =3 3k+2 +2 4k+1 =3 3 *3 3k-1 +2 4 *2 4k-3 = 27 3 3k-1 +16* 2 4k-3 =(16+11)* 3 3k-1 +16* 2 4k-3 =16* 3 3k-1 + 11* 3 3k-1 +16* 2 4k-3 =16(3 3k-1 +2 4k-3)+11* 3 3k-1 . Первое слагаемое делится на 11 без остатка, поскольку 3 3k-1 +2 4k-3 делится на 11 по предположению, второе делится на 11, потому что одним из его множителей есть число 11. Значит и сумма делится на 11 без остатка при любом натуральном n. Задачи из реальной жизни.
Пример 1.
Доказать, что сумма Sn внутренних углов любого выпуклого многоугольника равна (п
- 2)π, где п
— число сторон этого многоугольника:Sn = (п
- 2)π (1). Это утверждение имеет смысл не для всех натуральных п
, а лишь для п
>
3, так как минимальное число углов в треугольнике равно 3. 1) При п
= 3 наше утверждение принимает вид: S 3 = π. Но сумма внутренних углов любого треугольника действительно равна π. Поэтому при п
= 3 формула (1) верна. 2) Пусть эта формула верна при n=k
, то есть S k
= (k
- 2)π, где k
>
3. Докажем, что в таком случае имеет место и формула:S k+
1 = (k
- 1)π. Пусть A 1 A 2 ... A k
A k+
1 —произвольный выпуклый (k
+ 1) -угольник (рис. 338). Соединив точки A 1 и A k
, мы получим выпуклый k
-угольник A 1 A 2 ... A k
— 1 A k
. Очевидно, что сумма углов (k
+ 1) -угольника A 1 A 2 ... A k
A k+
1 равна сумме углов k
-угольника A 1 A 2 ... A k
плюс сумма углов треугольника A 1 A k
A k+
1 . Но сумма углов k
-угольника A 1 A 2 ... A k
по предположению равна (k
- 2)π, а сумма углов треугольника A 1 A k
A k+
1 равна π. Поэтому S k+
1 = S k
+ π = (k
- 2)π + π = (k
- 1)π. Итак, оба условия принципа математической индукции выполняются, и потому формула (1) верна при любом натуральном п
>
3. Пример 2.
Имеется лестница, все ступени которой одинаковы. Требуется указать минимальное число положений, которые гарантировали бы возможность «забраться» на любую по номеру ступеньку. Все согласны с тем, что должно быть условие. Мы должны уметь забраться на первую ступень. Далее должны уметь с 1-ой ступеньки забраться на вторую. Потом во второй - на третью и т.д. на n-ую ступеньку. Конечно, в совокупности же «n» утверждений гарантирует нм то, что мы сможем добраться до n-ой ступеньки. Посмотрим теперь на 2, 3,…., n положение и сравним их друг с другом. Легко заметить, что все они имеют одну и ту же структуру: если мы добрались до k ступеньки, то можем забраться на (k+1) ступеньку. Отсюда становится естественной такая аксиома для справедливости утверждений, зависящих от «n»: если предложение А(n), в котором n - натуральное число, выполняется при n=1 и из того, что оно выполняется при n=k (где k - любое натуральное число), следует, что оно выполняется и для n=k+1, то предположение А(n) выполняется для любого натурального числа n. Приложение
Задачи с применением метода математической индукции при поступлении в ВУЗы.
Заметим, что при поступление в высшие учебные заведения также встречаются задачи, которые решаются данным методом. Рассмотрим их на конкретных примерах. Пример 1.
Доказать, что любом натуральном п
справедливо равенство 1) При п=1
мы получаем верное равенство Sin. 2) Сделав предположение индукции, что при n=k
равенство верно, рассмотрим сумму, стоящую в левой части равенства, при n=k+1;
3) Используя формулы приведения преобразуем выражение: Тогда, в силу метода математической индукции равенство верно для любого натурального n. Пример 2.
Доказать, что для любого натурального n значение выражения 4n +15n-1 кратно 9. 1) При n=1: 2 2 +15-1=18 - кратно 9 (т.к.18:9=2) 2) Пусть равенство выполняется для n=k:
4 k +15k-1 кратно 9. 3) Докажем, что равенство выполняется и для следующего числа n=k+1
4 k+1 +15(k+1)-1=4 k+1 +15k+15-1=4.4 k +60k-4-45k+18=4(4 k +15k-1)-9(5k-2) 4(4 k +15k-1) - кратно 9; 9(5k-2) - кратно 9; Следовательно и все выражение 4(4 k +15k-1)-9(5k-2) кратно 9, что и требовалось доказать. Пример 3.
Доказать, что при любом натуральном числе п
выполняется условие: 1∙2∙3+2∙3∙4+…+ п(п+1)(п+2)=.
1) Проверим, что данная формула верна при п=1:
Левая часть = 1∙2∙3=6.
Правая часть= .
6 = 6; верно при п=1.
2) Предположим, что данная формула верна при n=k:
1∙2∙3+2∙3∙4+…+k(k+1)(k+2)=.
S k
=.
3) Докажем, что данная формула верна при n=k+1:
1∙2∙3+2∙3∙4+…+(k+1)(k+2)(k+3)=.
S k+1
=.
Доказательство: Итак, данное условие верно в двух случаях и доказали, что верно при n=k+1,
следовательно она верно при любом натуральном числе п.
Заключение
Подведем итоги, в процессе исследования я выяснил, в чем заключается индукция, которая бывает полной или неполной, познакомился с методом математической индукции, основанном на принципе математической индукции, рассмотрел множество задач с применением данного метода. Также я узнал много новой информации, отличной от той, что включена в школьную программу.Изучая метод математической индукции я использовал различную литературу, ресурсы интернета, а также консультировался с педагогом. Вывод:
Обобщив и систематизировав знания по математической индукции, убедился в необходимости знаний по данной теме в реальной действительности. Положительным качеством метода математической индукции является его широкое применение в решении задач: в области алгебры, геометрии и реальной математики. Также эти знания повышают интерес к математике, как к науке. Я уверен, что навыки, приобретенные в ходе работы, помогут мне в будущем.
Список литературы
Соминский И.С. Метод математической индукции. Популярные лекции по математике, выпуск 3-М.: Наука, 1974г. Л. И. Головина, И. М. Яглом. Индукция в геометрии. — Физматгиз, 1961. — Т. 21. — 100 с. — (Популярные лекции по математике). Дорофеев Г.В., Потапов М.К., Розов Н.Х. Пособие по математике для поступающих в вузы (Избранные вопросы элементарной математики) - Изд.5-е, перераб., 1976 - 638с. А. Шень. Математическая индукция. — МЦНМО, 2004. — 36 с. M.Л.Галицкий, А.М.Гольдман, Л.И.Звавич Сборник задач по алгебре: учеб.пособие для 8-9 кл. с углубл. изучением математики 7-е изд.— М.: Просвещение, 2001.—271 с Ма-ка-ры-чев Ю.Н., Мин-дюк Н.Г До-пол-ни-тель-ные главы к школь-но-му учеб-ни-ку ал-геб-ры 9 клас-са. - М.: Про-све-ще-ние, 2002. Википедия- свободная энциклопедия.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF