3. Применение метода математической индукции в различных разделах математики.

Пример 2

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

1. Одна прямая разбивает плоскость на две части, две – на 2 + 2, три- на

2+ 2 +3, четыре на 2 + 2 + 3 + 4, … , n прямых – на

2+ 2 + 3+ 4 + …+ n = 1+ n(n + 1) /2

2. n – прямых на F(n) = 1 + n(n + 1) /2. F(n +1) = 1 + (n + 2)(n + 1) /2.

3. Проведем ( n +1)- ую прямую, она разобьется n прямыми на n + 1 часть, каждая из них разделит содержащую ее часть на две части, т.е.

добавится еще ( n +1) – прямая:

F(n +1) = 1 + n(n + 1) /2 + n + 1 = 1 + (n + 2)(n + 1) /2.

На основании принципа математической индукции утверждение верно для любого натурального n.

Пример 3

Внутри выпуклого многогранника объема 1 отмечено 3( 2ⁿ -1) точки.

Докажите, что из него можно вырезать выпуклый многогранник объема (1/2)ⁿ , не содержащий внутри себя ни одной точки.

Индукция и делимость

Пример 4

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

1.n =1, 1³ +2³ +3³ = 36: 9 =4

2. Если k³ +( k+1)³ +(k+2)³ делится на 9, то (k+1)³ +(k+2)³ +(k+3)³делится

на 9.

3.(k+1)³ +(k+2)³ +(k+3)³ + k³ - k³ = k³ +( k+1)³ +(k+2)³ +( k+3)³ - k³ =

(k³ +( k+1)³ +(k+2)³ ) + (9k² +27 k +27) –делится на 9, так как первое слагаемое суммы делится на 9 по предположению, а второе – содержит множитель 9.

На основании принципа математической индукции утверждение верно для любого натурального n.

Пример 5

Докажите, что 7ⁿ – 1 делится на 6 при любом натуральном n.

1. n =1, 7¹ – 1- делится на 6.

2. Покажем, что если (7^k – 1) делится на 6, то и (7^k+1 – 1) делится на 6.

7^k+1 – 1 = (6+1)· 7^k – 1 =(7^k – 1)+ 6· 7^k - делится на 6, так как первое слагаемое суммы делится на 6 по предположению, а второе – содержит множитель 6.

3. На основании принципа математической индукции утверждение верно для любого натурального n.

Пример 6

Докажите, что 11ⁿ⁺² + 12^{2n +1} делится на 133.

Доказательство неравенств

Пример 7

Докажите, что (1+ α)ⁿ > 1 + nα, α >-1, α ≠ 0, n > 1, n .

Пример 8

Докажите, что любое целое число рублей большее 7, можно заплатить без сдачи денежными купюрами в 3 и 5 рублей.

Аксиомы Пеано — система аксиом, задающая структуру ряда натуральных чисел (натурального ряда), то есть чисел, возникших первоначально счета предметов. Система аксиом Пеано включает пять аксиом, из которых выводятся все свойства натуральных чисел:

1 является натуральным числом;

Число, следующее за натуральным, также является натуральным; 

1 не следует ни за каким натуральным числом; 

 Если натуральное число a непосредственно следует как за числом b, так и за числом c, то b и c тождественны;

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

Литература

1. Соминский И.С. Метод математической индукции - М.,1956 г.

2. Головина Л. И., Яглом И. М. Индукция в геометрии - М.,1961г.

3. Виленкин Н.Я. Индукция. Комбинаторика. - М.,1976г.

4. Литвиненко В. Н., Мордкович А.Г., Практикум по элементарной математике. - М.,1999.

Целые числа. Делимость целых чисел. Признаки делимости

План

1. Множество целых чисел. Свойства и операции.

2. Теоремы о делимости.

3. Деление с остатком.

1

Множество целых чисел – это натуральные, им противоположные и ноль.

Свойства целых чисел (Z).

1. Множество целых чисел замкнуто относительно операций сложения, вычитания, умножения: это значит, что результат указанных операций над целыми числами так же принадлежит множеству целых чисел.

2. Дискретно: для любого целого числа можно указать следующее за ним, между двумя соседними целыми числами нет целого числа.

3. Упорядоченно: для любых целых чисел можно установить отношение порядка ( a>b, a<b, a=b).

Свойства операций с целыми числами

1. a + b = b + a ( коммутативный закон сложения)

2. (a + b) +с = a + (b +c) ( ассоциативный закон сложения)

3. a - a = 0

4. a + 0 = a

5. a b = b a ( коммутативный закон умножения)

6. (a b) с = a (b c) ( ассоциативный закон умножения)

7. (a + b) с = a с + b c (дистрибутивный закон умножения относительно сложения)

8. 1·a = a

Определение

Если a : b = с , то a называется кратным b, а b – делителем числа a.

Теорема о единственности разложения натурального числа на простые множители.( Основная теорема арифметики).

Существует и при том единственное разложение всякого натурального

числа ( кроме 1) на простые множители.

Представление натурального числа в виде n = , где

p_1, p_2, p_{3, …} p_n – простые числа, называется каноническим разложением натурального числа на простые множители.

Например, 36 = 3²2², 195=3¹·5¹·13¹.

Задача

Сколько всего делителей имеет натуральное число, если его каноническое разложение имеет вид n = ?

Пример 60 = 2²3¹5¹

Его делители 1, 2, 3,4, 5, 6, 10, 12,15,20, 30, 60 – всего 12.

Как подсчитать число делителей, не перечисляя их?

Число вариантов( способов) вхождения в делители данного числа делителя с основанием 2 всего три:

1. совсем нет такого делителя,

2. 2¹

3. 2²

Число вариантов(способов) вхождения делителя с основанием 3 всего 2

1. совсем нет такого делителя,

2. 3¹.

Число вариантов( способов) вхождения делителя с основанием 5 всего 2

1- совсем нет такого делителя,

2- 5¹.

Каждый из первых трех вариантов можно объединить с каждым из двух вторых, всего получится 3·2=6. Каждый из этих 6 вариантов можно объединить с любым из двух способов вхождения числа 5 в делители данного числа, всего получится 3·2·2= 12.

Аналогичное этому доказательство в общем виде приводит к результату:

Количество всевозможных делителей числа n = равно

(α₁+1)( α₂+1) ( α₃+1)…( α_n+1).

Теорема о бесконечности ряда простых чисел

Не существует наибольшего простого числа.

Доказательство

Предположим, что p – наибольшее простое число.

Рассмотрим число 2·3·5·…· p + 1- это число либо само простое, большее p, либо делится на простое число, не содержащееся среди чисел

2, 3, 5, …,p, а следовательно, большее p. Получили противоречие, доказывающее теорему.

Связь между НОД и НОК.

Обозначим НОД( а; b) = d, НОК(a;b)= m.

Так как НОД( а; b) = d, то a = a₁d, b = b₁d, (a₁;b₁)=1.

Так как НОK( а; b) = m, то m = a_1·d· b₁, тогда а·b = a_1·d· b_1·d = m d.

Таким образом, НОД( а;b) ·НОК(a;b)= ab.

2

Теоремы о делимости

1.Если a : m, b : m, то (a +b ): m, (a -b ): m.

2. Если a : m, b : n, то a b: mn.

3. Если a : m, aⁿ : mⁿ.

4. Если сумма нескольких слагаемых делится на m и известно, что все слагаемые, кроме одного, делятся на m, то и оставшееся слагаемое делится на m.

5. Если хотя бы один из множителей произведения делится на m, то и произведение делится на m.

Пример

Докажите, что произведение n(n+1)(n+2) делится на 6 при любом натуральном n.

Доказательство

Если n – нечетное, то n +1 – четное, следовательно, произведение делится на 2. Если n – не кратно 3 (значит при делении на 3 дает остаток 1 или 2), то n +2 или n + 1 кратно 3. Таким образом, произведение n(n+1)(n+2) делится на 2 и на 3, а так как эти числа взаимно простые, то оно делится на 6.

Признаки делимости

1.Для того, чтобы натуральное число делилось на 3( 9) необходимо и достаточно, чтобы сумма цифр этого числа делилась на 3(9).

2. Для того, чтобы натуральное число делилось на 11 необходимо и достаточно, чтобы разность между суммой цифр этого числа стоящих на четных местах и суммой цифр этого числа стоящих на нечетных местах делилась на 11.

3. Для того, чтобы натуральное число делилось на 4 необходимо и достаточно, чтобы число, образованное двумя последними цифрами этого числа делилось на 4.

Докажем 2.

p= a_n10ⁿ + a_n-110^n-1 + a_n-210^n-2 +…..+ a₁10¹+ a₀ = a_n (11-1)ⁿ + a_n-1 (11-1)^n-1 + a_n-2 (11-1)^n-2 +…..+ a₁ (11-1)¹+ a₀ = 11K + (a_n (-1)ⁿ + a_n-1 (-1)^n-1 + a_n-2 (-1)^n-2 +…..+ a₁ (-1)¹+ a₀ ).

Если число p делится на 11, то второе слагаемое (a_n (-1)ⁿ + a_n-1 (-1)^n-1 + a_n-2 (-1)^n-2 +…..+ a₁ (-1)¹+ a₀ ) суммы делится на 11 и обратно: для того, чтобы число p делилось на 11, достаточно, чтобы это слагаемое делилось на 11.

Второе слагаемое суммы в зависимости от четности или нечетности n

равняется (a_n - a_n-1 + a_n-2 -…..-a₁ + a₀ ) или (-a_n+a_n-1 - a_n-2 +…..-a₁ + a₀ ), т.е.

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

4. Если число делится на 1001, то оно делится на 7, 11, 13.

Деление с остатком

Теорема о делении с остатком

Каковы бы ни были целые числа a и b, найдутся два таких целых числа q и r, что a = b· q + r, где 0≤ r <│b│.

Доказательство

Пусть b > 0 .

Рассмотрим ряд чисел: …-2b, -1b,0b, 1b, 2b,…

В этой последовательности найдется наибольшее число, которое не превосходит a, т.е. b· q ≤ a < b· (q +1) или 0≤ a - b· q < b. Обозначим

a - b· q = r, получим: a = b· q + r, где 0≤ r <│b│, что и требовалось доказать.

Случай b ≤ 0 доказать самостоятельно.

Единственность

Нахождение наибольшего общего делителя с помощью алгоритма

Евклида.

По теореме о делении с остатком для любых натуральных чисел a и b справедливо равенство a = b· q + r, где 0≤ r < b. Если d =(a;b), то по теореме 4 о делимости d =(r;b), тогда по теореме о делении с остатком для натуральных чисел r и b справедливо равенство:

b = r· q + r₁, где 0≤ r₁ < r, d =(r;r₁), далее

r= r₁· q + r₂, где 0≤ r₂ < r, d =(r₂; r₁),

r₁= r₂· q + r₃, где 0≤ r₂ < r, d =(r₂; r₃),

…………………………………………..

r_n-1= r_n· q , d =(r_n-1; r_n) = r_n

Поскольку остатки при делении уменьшаются, то на каком-то шаге появится остаток, равный нулю. r_n-1= r_n· q , d =(r_n-1; r_n) = r_n

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

Пример

Найти (899; 493) = 29

899│493

493 1

493│406

406 1

406│ 87

348 4

87│ 58

58 1

58│ 29

58 2

0

Применение теоремы о делении с остатком.

Множество целых чисел можно разбить на классы, в зависимости от остатков при делении целых чисел на некоторое данное натуральное число. Вообще при делении на число b могут быть остатки:

0, 1,2,3…, b-1.

Пример

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

Разобьем множество целых чисел на классы, в зависимости от остатков при делении на 3.

Если число имеет вид 3к, то n² +1= 9k² +1 – не делится на 3.

Если число имеет вид 3к + 1, то n² +1= 9k² + 6k +2 – не делится на 3.

Если число имеет вид 3к + 2, то n² +1= 9k² + 12k +5 – не делится на 3.

Таким образом, число n² +1 не делится на 3.

Литература

1.Ананченко К.О. Алгебра – 8 - Мн.,2002

2. Рогановский Н.М., Рогановская Е. Н. Элементарная математика- Мн., 2000

Числовые неравенства и их свойства. Доказательство неравенств.

План

1. Числовые неравенства. Свойства числовых неравенств.

2. Методы доказательства неравенств.