Математическая индукция — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (>= → \ge)
(Определение)
(не показано 9 промежуточных версий 3 участников)
Строка 1: Строка 1:
Математическая индукция - способ рассужжения, заключающийся в следующем:
+
[[Категория:Математический анализ 1 курс]]
 +
== Определение ==
 +
Математическая индукция {{---}} способ рассуждения, применяемый, в частности, в [[Математический анализ 1 курс|математическом анализе]], заключающийся в следующем:
 +
 
 +
Пусть имеется последовательность свойств <tex> P_1, P_2 \dots P_n \dots </tex>
 +
# <tex> P_1 </tex> {{---}} истина
 +
# <tex> P_k \Rightarrow P_{k+1} </tex> {{---}} шаг индукции
 +
# Тогда все <tex> P_n </tex> {{---}} истинны
 +
 
 +
== Примеры использования ==
  
Пусть имеется последовательность свойств <tex> P_1, P_2 \dots P_n </tex>
+
=== Неравенство Бернулли ===
# <tex> P_1 </tex> - истина
 
# <tex> P_n \Rightarrow P_{n+1} </tex> - шаг индукции
 
# Тогда все <tex> P_n </tex> - истинны
 
 
 
{{Утверждение
 
{{Утверждение
 
|about =  
 
|about =  
Строка 12: Строка 17:
 
<tex> \forall n \in N; \forall x > -1 : {(1 + x)}^n \ge 1 + nx </tex>
 
<tex> \forall n \in N; \forall x > -1 : {(1 + x)}^n \ge 1 + nx </tex>
 
|proof = <br />
 
|proof = <br />
# <tex> n = 1: 1 + x >= 1 + x </tex> - верно
+
# <tex> n = 1: 1 + x \ge 1 + x </tex> {{---}} верно
# <tex> {(1 + x)}^{n + 1} = {(1 + x)}^n (1 + x) >= (1 + nx) (1 + x) = </tex><br /><tex> = 1 + x + nx + nx^2 >= 1 + (n + 1)x - P_{n+1} </tex>
+
# <tex> {(1 + x)}^{n + 1} = {(1 + x)}^n (1 + x) \ge (1 + nx) (1 + x) = </tex><br /><tex> = 1 + x + nx + nx^2 = 1 + (n + 1)x + nx^2</tex>, так как <tex> nx^2 \ge 0 </tex>, то <tex> {(1 + x)}^{n + 1} \ge 1 + (n + 1)x </tex>
 
}}
 
}}
 +
 +
=== Конечный бином Ньютона ===
  
 
Для того, чтобы сформировать следующее утверждение, определим систему чисел, называемую биномиальными коэффициентами: <br />
 
Для того, чтобы сформировать следующее утверждение, определим систему чисел, называемую биномиальными коэффициентами: <br />
 
:<tex> 0! = 1 \\ n! = n(n-1)! = n (n-1) (n-2) \dots 1 </tex>
 
:<tex> 0! = 1 \\ n! = n(n-1)! = n (n-1) (n-2) \dots 1 </tex>
:<tex> m <= n: C_n^m = \frac {n!} {(n-m)!m!} \\  
+
:<tex dpi = "150"> m \le n: C_n^m = \frac {n!} {(n-m)!m!} \\ \\
C_{n+1}^m = C_n^m + C_n^{m-1} = \\
+
C_{n+1}^m = C_n^m + C_n^{m-1} = \\ = C_n^m + C_n^{m-1} = \frac {n!} {(n-m)!m!} + \frac {n!} {(n-m+1)!(m-1)!} = \\
= C_n^m + C_n^{m-1} = \frac {n!} {(n-m)!m!} + \frac {n!} {(n-m+1)!(m-1)!} = \\
 
 
  = \frac {n!((n - m + 1) + m)} {m!((n+1) - m)!} = \frac {n!(n+1)} {((n+1)-m)!m!} = C_{n+1}^m </tex>
 
  = \frac {n!((n - m + 1) + m)} {m!((n+1) - m)!} = \frac {n!(n+1)} {((n+1)-m)!m!} = C_{n+1}^m </tex>
  
Строка 29: Строка 35:
 
<tex>a, b \in R; n \in N : {(a + b)}^n = \sum_{k=0}^n C_n^k a^k b^{n - k} </tex>
 
<tex>a, b \in R; n \in N : {(a + b)}^n = \sum_{k=0}^n C_n^k a^k b^{n - k} </tex>
 
|proof = <br />
 
|proof = <br />
# Для n = 1 - очевидно
+
# Для n = 1 {{---}} очевидно
 
# <tex> {(a + b)}^{n + 1} = a{(a + b)}^n + b{(a + b)}^n = </tex><br />
 
# <tex> {(a + b)}^{n + 1} = a{(a + b)}^n + b{(a + b)}^n = </tex><br />
:<tex> = \sum_{k = 0}^n C_n^k a^{k + 1} b^{n - k} + \sum_{k = 0}^n C_n^k a^k b^{n - k + 1} = </tex><br />
+
:<tex> = \sum\limits_{k = 0}^n C_n^k a^{k + 1} b^{n - k} + \sum\limits_{k = 0}^n C_n^k a^k b^{n - k + 1} = </tex>
:<tex> = \sum_{j = 1}^{n + 1} C_n^{j - 1} a^j b^{n - j + 1} + \sum_{i = 0}^n C_n^i a^i b^{n - i + 1} = </tex><br />
+
 
:<tex> = C_n^n a^{n + 1} b^0 + \sum_{j = 1}^n C_n^{j - 1} a^j b^{n - j + 1} + C_n^0 a^0 b^{n+1} + \sum_{i = 1}^n C_n^i a^i b^{n - i + 1} = :</tex> <br />
+
:<tex> = \sum\limits_{j = 1}^{n + 1} C_n^{j - 1} a^j b^{n - j + 1} + \sum\limits_{i = 0}^n C_n^i a^i b^{n - i + 1} = </tex>
:<tex> = 1 (a^{n + 1} + b^{n + 1}) + \sum_{j = 1}^n (C_n^{j - 1} + C_n^j) a^j b^{n - j + 1}</tex> <br />
+
 
:Так как <tex>1 = C_{n + 1}^{n + 1} = C_{n + 1}^0 </tex> , то <br />
+
:<tex> = C_n^n a^{n + 1} b^0 + \sum\limits_{j = 1}^n C_n^{j - 1} a^j b^{n - j + 1} + C_n^0 a^0 b^{n+1} + \sum\limits_{i = 1}^n C_n^i a^i b^{n - i + 1} = </tex>  
:<tex> = C_{n + 1}^{n + 1} a^{n + 1} b^0 + C_{n + 1}^0 a^0 b^{n + 1} + \sum_{j = 1}^n C_{n + 1}^j a^j b^{n - j + 1}</tex> <br />
+
 
:Занесем первые два слагаемых под знак суммы и получим: <br />
+
:<tex> = 1 (a^{n + 1} + b^{n + 1}) + \sum\limits_{j = 1}^n (C_n^{j - 1} + C_n^j) a^j b^{n - j + 1}</tex>  
:<tex> = \sum_{j = 0}^{n + 1} C_{n + 1}^j a^j b^{n + 1 - j}</tex> , что есть разложение для <tex> {(a + b)}^{n + 1} </tex>  
+
 
 +
:Так как <tex>1 = C_{n + 1}^{n + 1} = C_{n + 1}^0 </tex> , то  
 +
 
 +
:<tex> = C_{n + 1}^{n + 1} a^{n + 1} b^0 + C_{n + 1}^0 a^0 b^{n + 1} + \sum\limits_{j = 1}^n C_{n + 1}^j a^j b^{n - j + 1}</tex>  
 +
 
 +
:Занесем первые два слагаемых под знак суммы и получим:
 +
 
 +
:<tex> = \sum\limits_{j = 0}^{n + 1} C_{n + 1}^j a^j b^{n + 1 - j}</tex> , что есть разложение для <tex> {(a + b)}^{n + 1} </tex>  
 
}}
 
}}
 
[[Категория:Математический анализ 1 курс]]
 

Версия 13:00, 14 февраля 2015

Определение

Математическая индукция — способ рассуждения, применяемый, в частности, в математическом анализе, заключающийся в следующем:

Пусть имеется последовательность свойств [math] P_1, P_2 \dots P_n \dots [/math]

  1. [math] P_1 [/math] — истина
  2. [math] P_k \Rightarrow P_{k+1} [/math] — шаг индукции
  3. Тогда все [math] P_n [/math] — истинны

Примеры использования

Неравенство Бернулли

Утверждение (неравенство Бернулли):
[math] \forall n \in N; \forall x \gt -1 : {(1 + x)}^n \ge 1 + nx [/math]
[math]\triangleright[/math]


  1. [math] n = 1: 1 + x \ge 1 + x [/math] — верно
  2. [math] {(1 + x)}^{n + 1} = {(1 + x)}^n (1 + x) \ge (1 + nx) (1 + x) = [/math]
    [math] = 1 + x + nx + nx^2 = 1 + (n + 1)x + nx^2[/math], так как [math] nx^2 \ge 0 [/math], то [math] {(1 + x)}^{n + 1} \ge 1 + (n + 1)x [/math]
[math]\triangleleft[/math]

Конечный бином Ньютона

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

[math] 0! = 1 \\ n! = n(n-1)! = n (n-1) (n-2) \dots 1 [/math]
[math] m \le n: C_n^m = \frac {n!} {(n-m)!m!} \\ \\ C_{n+1}^m = C_n^m + C_n^{m-1} = \\ = C_n^m + C_n^{m-1} = \frac {n!} {(n-m)!m!} + \frac {n!} {(n-m+1)!(m-1)!} = \\ = \frac {n!((n - m + 1) + m)} {m!((n+1) - m)!} = \frac {n!(n+1)} {((n+1)-m)!m!} = C_{n+1}^m [/math]
Утверждение (конечный бином Ньютона):
[math]a, b \in R; n \in N : {(a + b)}^n = \sum_{k=0}^n C_n^k a^k b^{n - k} [/math]
[math]\triangleright[/math]


  1. Для n = 1 — очевидно
  2. [math] {(a + b)}^{n + 1} = a{(a + b)}^n + b{(a + b)}^n = [/math]
[math] = \sum\limits_{k = 0}^n C_n^k a^{k + 1} b^{n - k} + \sum\limits_{k = 0}^n C_n^k a^k b^{n - k + 1} = [/math]
[math] = \sum\limits_{j = 1}^{n + 1} C_n^{j - 1} a^j b^{n - j + 1} + \sum\limits_{i = 0}^n C_n^i a^i b^{n - i + 1} = [/math]
[math] = C_n^n a^{n + 1} b^0 + \sum\limits_{j = 1}^n C_n^{j - 1} a^j b^{n - j + 1} + C_n^0 a^0 b^{n+1} + \sum\limits_{i = 1}^n C_n^i a^i b^{n - i + 1} = [/math]
[math] = 1 (a^{n + 1} + b^{n + 1}) + \sum\limits_{j = 1}^n (C_n^{j - 1} + C_n^j) a^j b^{n - j + 1}[/math]
Так как [math]1 = C_{n + 1}^{n + 1} = C_{n + 1}^0 [/math] , то
[math] = C_{n + 1}^{n + 1} a^{n + 1} b^0 + C_{n + 1}^0 a^0 b^{n + 1} + \sum\limits_{j = 1}^n C_{n + 1}^j a^j b^{n - j + 1}[/math]
Занесем первые два слагаемых под знак суммы и получим:
[math] = \sum\limits_{j = 0}^{n + 1} C_{n + 1}^j a^j b^{n + 1 - j}[/math] , что есть разложение для [math] {(a + b)}^{n + 1} [/math]
[math]\triangleleft[/math]