Anula o 11:53, 22 maj 2015

2015-05-22T11:53:42Z

Anula: Utworzono nową stronę "NOTOC ==Zasada indukcji matematycznej== Zbiór liczb naturalnych posiada bardzo ważną własność, której często się używa w dowodach. Mówi ona że: Niech..."

2015-05-22T11:49:41Z

Utworzono nową stronę "__NOTOC__ ==Zasada indukcji matematycznej== Zbiór liczb naturalnych posiada bardzo ważną własność, której często się używa w dowodach. Mówi ona że: Niech..."

Nowa strona

__NOTOC__

==Zasada indukcji matematycznej==

Zbiór liczb naturalnych posiada bardzo ważną własność, której często się używa w dowodach. Mówi ona że:

Niech będzie dana jakaś własność liczb naturalnych (nazwijmy ją '''tezą indukcyjną''') <math>T_n\;</math>,która spełnia następujące warunki:
<equation id="eq:1">Liczba 1 posiada tę własność (tzn. teza <math>T_1\;</math> jest prawdziwa),</equation>
<equation id="eq:2">Jeśli liczba <math>n\;</math> posiada tę własność, to posiada ją również liczba <math>n+1\;</math> (tzn. prawdziwa jest implikacja: <math>T_n\Longrightarrow T_{n+1}\;</math>)</equation>

'''Zasada indukcji''' oznacza, że przy powyższych założeniach, ''każda'' liczba naturalna posiada tę własność (tzn. teza <math>T_n\;</math> jest prawdziwa dla każdej <math>n\in \mathbb N\;</math>). Zasada indukcji odpowiada następującej intuicji: Jeśli prawdziwa jest teza <math>T_1\;</math>, to — na mocy <xr id="eq:2">(%i)</xr> — prawdziwa jest również teza <math>T_2\;</math>. Skoro tak, to z <xr id="eq:2">(%i)</xr> prawdziwa jest również teza <math>T_3\;</math>, i znów używając <xr id="eq:2">(%i)</xr> prawdziwa jest teza <math>T_4\;</math> itd.

===Przykład — Nierówność Bernoulliego===

Dla każdej liczby naturalnej <math>n\;</math> i każdej liczby rzeczywistej <math>a\geq -1\;</math> zachodzi wzór
<equation id="eq:3">
<math>(1+a)^n \geq 1+ n a \;
</math>
</equation>

#Sprawdzamy prawdziwość tezy <math>T_1\;</math>, tzn. czy nierówność jest prawdziwa dla <math>n=1\;</math>. Mamy: <math>1+a \geq 1+ a\;</math> czyli ok.
#Sprawdzamy prawdziwość implikacji <math>T_n\Longrightarrow T_{n+1}\;</math>.
Zapiszmy prawą stronę <math>T_{n+1}\;</math>:
<center><math>
(1+a)^{n+1} = (1+a)^n(1+a) \geq (1+na)(1+a) = 1+(n+1)a + na^2 \geq 1+ (n+1)a\;</math></center>
(korzystamy z założenia o prawdziwości T_n oraz że <math>(1+a)\geq 0 \;</math>)<br>
czyli, zakładając prawdziwósć tezy <math>T_n\;</math>, otrzymaliśmy prawdziwość; tezy <math>T_{n+1}\;</math>. Z zasady indukcji wynika więc, że teza <math>T_n\;</math> jest prawdziwa dla każej <math>n\in \mathbb N\;</math> — tzn. że nierówność <xr id="eq:3">(%i)</xr> jest prawdziwa <math>\forall \, n\in \mathbb N\;</math>

===Przykład — Dwumian Newtona===

Najsampierw jednak zdefiniujemy (a dla tych, co znają, przypomnimy) symbol ''silnia'': <math>n!=1\cdot 2 \cdot 3 \dots (n-1) \cdot n\;</math>, (przyjmujemy też, że <math>0!=1\;</math>), a następnie ''współczynniki Newtona''
<equation id="eq:4"><math>\begin{matrix}
\left(
\begin{matrix}
n\\k
\end{matrix}
\right)
&=&
\frac{n(n-1)(n-2)\dots(n-k+1)}{1\cdot 2 \cdot 3 \dots \cdot k}
\\
&=& \frac{n!}{k!(n-k)!}
\end{matrix}\;\;
</math></equation>
zakładamy, że <math>n\;</math> i <math>k\;</math> są to liczby naturalne, oraz <math>n\geq k\;</math>. Mamy:
<center><math>
\left(
\begin{matrix}
n\\0
\end{matrix}
\right) = 1, \;\;\;\;\; \left(\begin{matrix} n\\n \end{matrix}
\right)=1.
\;</math></center>

Pokażemy teraz, że <math>\forall\, n, k \in \mathbb N\;</math>, <math>n\geq k\;</math> zachodzi
<center><math>
\left(
\begin{matrix} n\\k\end{matrix}\right)+\left(\begin{matrix}n\\k-1\end{matrix}\right)=\left(\begin{matrix} n+1\\k \end{matrix}
\right).\;</math></center>

Liczymy bezpośrednio:
<center><math>
\left( \begin{matrix}n\\k\end{matrix}\right)+\left(\begin{matrix}n\\k-1 \end{matrix}\right)=\frac{n(n-1)(n-2)\dots(n-k+1)}{1\cdot 2 \cdot 3 \dots \cdot k}+\frac{n(n-1)(n-2)\dots(n-k+2)}{1\cdot 2 \cdot 3 \dots \cdot (k-1)}\cdot\frac{k}{k}
\;</math></center>

<center><math>
=
\frac{n(n-1)(n-2)\dots(n-k+2)(n-k+1+k)}{1\cdot 2 \cdot 3 \dots \cdot k} = \left(\begin{matrix} n+1\\k\end{matrix}\right).
\;</math></center>

Teraz przystępujemy do udowodnienia ''wzoru dwumiennego Newtona'':
====Twierdzenie====

<math>\forall\, a,b \in \mathbb R\;</math>, <math>\forall\, n\in \mathbb N\;</math> zachodzi <br>
<equation id="eq:5"><math>
(a+b)^n= a^n + \left(\begin{matrix}n\\1\end{matrix}\right)a^{n-1}b+\left(\begin{matrix} n\\2\end{matrix}\right)a^{n-2}b^2+\dots+\left(\begin{matrix}n\\k\end{matrix}\right) a^{n-k}b^k+\dots
+\left(\begin{matrix}n\\n\end{matrix}\right)b^n.
\;</math></equation>

====Uwaga====

Dla <math>n=1\;</math> wzór <xr id="eq:5">(%i)</xr> jest oczywisty. Dla <math>n=2\;</math> i <math>n=3\;</math> wzór wzór <xr id="eq:5">(%i)</xr> powinien być znany ze szkoły średniej (a jeśli nie jest, niech Czytelnik sprawdzi, że <math>(a+b)^2=a^2+2ab+b^2\;</math>; <math>(a+b)^3=a^3+ 3 a^2 b + 3 a b^2 + b^3\;</math>).

====Dowód====
Tak więc, zgodnie ze schematem dowodu indukcyjnego:
<ol>
<li>Teza <math>T_1\;</math> jest prawdziwa.</li>
<li> Aby pokazać wynikanie <math>T_n\Longrightarrow T_{n+1}\;</math>, weźmy prawą stronę równości <xr id="eq:5">(%i)</xr> dla <math>n+1\;</math>. Mamy <math>(a+b)^{n+1} = (a+b)^n(a+b) = (a+b)^n a + (a+b)^n b, \;</math> i korzystając teraz z założenia o prawdziwości <math>T_n\;</math>, mamy
<center>
<math>\begin{matrix} (a+b)^{n+1} =\;a^{n+1} +\left(\begin{matrix}n\\1\end{matrix}\right)a^{n}b+\left(\begin{matrix}n\\2\end{matrix}\right)a^{n-1}b^2+\dots+\left(\begin{matrix}n\\k\end{matrix}\right)a^{n-k+1}b^k+\dots+\left(\begin{matrix}n\\n\end{matrix}\right)a b^n + a^n b +\left(\begin{matrix}n\\1\end{matrix}\right)a^{n-1}b^2+\ldots\\+\left(\begin{matrix}n\\k-1\end{matrix}\right)a^{n-k+1}b^k+\ldots+\left(\begin{matrix}n+1\\n\end{matrix}\right)a b^{n}+b^{n+1}= a^{n+1} +\left(\begin{matrix} n+1\\1\end{matrix}\right) a^{n}b+ \dots+\left(\begin{matrix}n+1\\k\end{matrix}\right) a^{n-k+1}b^k+\dots+\left(\begin{matrix}n+1\\n\end{matrix}\right) a b^n + b^{n+1}\end{matrix},\;</math>
</center>
a jest to właśnie lewa strona równości <xr id="eq:5">(%i)</xr> dla <math>n+1\;</math>. Zatem, możemy zakończyć dowód mówiąc, że</li>
<li> Równość <xr id="eq:5">(%i)</xr> jest prawdziwa dla każdego <math>n\in \mathbb N\;</math>.</li>
</ol>
====Uwaga====
Wzór na dwumian Newtona daje się zapisać o wiele krócej używając symbolu ''sumy'':
<math>
(a+b)^n = \sum^{n}_{k=0} \left(
\begin{matrix}
n\\k
\end{matrix}
\right)
a^{n-k} b^k
\;</math>

Tu symbol: <math>\sum^{n}_{k=0} A_k\;</math> oznacza, że należy utworzyć sumę <math>n+1\;</math> składników, które powstają z wyrażenia <math>A_k\;</math> przez podstawianie na miejsce <math>k\;</math> kolejno liczb <math>0, 1, 2,\dots, n\;</math>.

===Przykład===

(startuje się od <math>n_0>1\;</math>) Pokazać, że <math>\forall n>4\;</math> zachodzi <math>2^n>n^2\;</math>.

===Przykład===

(używa się tezy nie tylko <math>T_n\;</math>, ale też <math>T_{n-1}\;</math> aby pokazać prawdziwość <math>T_{n+1}\;</math>) ''Ciąg Fibonacciego''. Określony jest on rekurencyjnie: <math>F_1 =F_2=1, F_n = F_{n-1} + F_{n-2}\;</math>. Pokazać, że dla dowolnego <math>n\in \mathbb N\;</math> zachodzi
<center><math>
F_n= \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right]
\;</math></center>

Funkcja wykładnicza i logarytmiczna - Historia wersji

Anula o 11:53, 22 maj 2015

Anula: Utworzono nową stronę "__NOTOC__ ==Zasada indukcji matematycznej== Zbiór liczb naturalnych posiada bardzo ważną własność, której często się używa w dowodach. Mówi ona że: Niech..."

Anula: Utworzono nową stronę "NOTOC ==Zasada indukcji matematycznej== Zbiór liczb naturalnych posiada bardzo ważną własność, której często się używa w dowodach. Mówi ona że: Niech..."