Indukcja matematyczna

Indukcja matematyczna jest szczególnym sposobem na udowodnienie prawdy matematycznej. Można ją wykorzystać do udowodnienia, że coś jest prawdą dla wszystkich liczb naturalnych (wszystkich dodatnich liczb całkowitych). Chodzi o to, że

Coś jest prawdziwe w pierwszym przypadku
To samo zawsze dotyczy następnego przypadku.

następnie

To samo odnosi się do każdego przypadku

W uważnym języku matematyki:

Podaj, że dowód będzie przez indukcję nad n {\i0} . ( n {\i1}jest zmienną indukcyjną.{\i0}
Pokaż, że stwierdzenie jest prawdziwe, gdy n {\i0}jest 1.
Załóżmy, że to stwierdzenie jest prawdziwe dla dowolnej liczby naturalnej n {\i1} . (Nazywa się to krokiem indukcyjnym.)

Pokaż wtedy, że oświadczenie jest prawdziwe dla następnej liczby, n + 1 {\i1} $n+1$ .

Ponieważ jest to prawda dla 1, potem jest to prawda dla 1+1 (=2, przez stopień indukcji), potem jest to prawda dla 2+1 (=3), potem jest to prawda dla 3+1 (=4), i tak dalej.

Przykład dowodu przez indukcję:

Udowodnić, że dla wszystkich liczb naturalnych n:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\i1} styropian 1+2+3+.... $1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)$

Dowód:

Po pierwsze, oświadczenie można napisać: dla wszystkich liczb naturalnych n

2 ∑ k = 1 n k = n ( n + 1 ) {\i1 ) {\i0}sum _{k=1}^{n}k=n(n+1)} $2\sum _{k=1}^{n}k=n(n+1)$

Przez indukcję na n,

Po pierwsze, za n=1:

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\i0}sum _{k=1}^{1}k=2(1)=1(1+1)} $2\sum _{k=1}^{1}k=2(1)=1(1+1)$ ,

więc to jest prawda.

Następnie załóżmy, że dla niektórych n=n0 stwierdzenie jest prawdziwe. To znaczy,:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\i1}styl 2\i0}sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)$

Następnie dla n=n0+1:

2 ∑ k = 1 n 0 + 1 k {\i1}styl 2\i0}sum _{k=1}^{{n_{0}}+1}k} $2\sum _{k=1}^{{n_{0}}+1}k$

może zostać przepisany

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\i1}k+(n_{0}+1)\i1}K+(n_{0}+1)\i1} $2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)$

Since 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\i1}displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),$

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\i1} {\i1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+1)(n_{0}+2)} $2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)$

Dlatego dowód jest prawidłowy.

Podobne dowody

Indukcja matematyczna jest często podawana z wartością początkową 0 (a nie 1). W rzeczywistości, będzie ona działać równie dobrze z różnymi wartościami początkowymi. Oto przykład, kiedy wartość początkowa wynosi 3. Suma kątów wewnętrznych n {\i1} - bocznego wielokąta n{\i0} wynosi ( n - 2 ) 180 {\i1} $(n-2)180$ stopni.

Początkowa wartość początkowa wynosi 3, a kąty wewnętrzne trójkąta wynoszą ( 3 - 2 ) 180 {\i0} $(3-2)180$ stopni. Załóżmy, że kąt wewnętrzny wielokąta bocznego n wynosi ( n - 2 ) 180 $(n-2)180$ stopni. Dodaj trójkąt, który czyni figurę n + 1. - $n+1$ wielokąt boczny, a to zwiększa liczbę kątów o 180 stopni ( n - 2 ) 180 + 180 = ( n + 1 - 2 ) 180 {\i1} stopni styropianu (n-2)180+180=(n+1-2)180} $(n-2)180+180=(n+1-2)180$ stopni. Udowodnione.

Istnieje wiele obiektów matematycznych, na które działają dowody poprzez indukcję matematyczną. Termin techniczny to uporządkowany zestaw.

Indukcyjna definicja

Ten sam pomysł może zadziałać zarówno w celu zdefiniowania, jak i udowodnienia.

Zdefiniuj styl kuzyna stopnia:

$1$ .
A n + 1 {\i1} $n+1$ st. kuzyn to dziecko rodzica n{\i1} st. kuzyna.

Istnieje zestaw aksjomatów do arytmetyki liczb naturalnych, który jest oparty na indukcji matematycznej. Nazywa się to "Peano's Axioms". Niezdefiniowane symbole to |i =. Aksjomatami są

|jest naturalną liczbą
Jeśli n {\i1}jest liczbą naturalną, to n {\i1} $n|$ {\i1}jest liczbą naturalną.{\i0}
If n | = m | {\i1}displaystyle n|=m|} $n|=m|$ then n = m {\i1}displaystyle n=m} $n=m$

Następnie można zdefiniować operacje dodawania i mnożenia i tak dalej poprzez indukcję matematyczną. Na przykład:

m + | = m | {\i1}Displastyla m+|=m|} $m+|=m|$
m + n | = ( m + n ) | {\i1}(m+n)|=(m+n)|} $m+n|=(m+n)|$

Pytania i odpowiedzi

P: Co to jest indukcja matematyczna?

A: Indukcja matematyczna to specjalny sposób dowodzenia prawdy matematycznej, który można wykorzystać do udowodnienia, że coś jest prawdziwe dla wszystkich liczb naturalnych lub liczb dodatnich od pewnego momentu.

P: Jak przebiega dowód przez indukcję?

O: Dowód przez indukcję zwykle przebiega w ten sposób, że stwierdza się, że dowód będzie przeprowadzony dla liczby n, pokazuje się, że twierdzenie jest prawdziwe, gdy n wynosi 1, zakłada się, że twierdzenie jest prawdziwe dla dowolnej liczby naturalnej n, a następnie pokazuje się, że jest prawdziwe dla kolejnej liczby (n+1).

P: Co to znaczy zakładać coś w kroku indukcyjnym?

O: Założenie czegoś w kroku indukcyjnym oznacza przyjęcie tego za prawdę bez podania dowodów. Jest to punkt wyjścia do dalszych badań.

P: Jakich liczb używa się w indukcji matematycznej?

O: W indukcji matematycznej zazwyczaj używa się liczb naturalnych lub od pewnego momentu liczb dodatnich.

P: Jak wykazać, że coś jest prawdziwe dla kolejnej liczby (n+1)?

O: Aby wykazać, że coś jest prawdą dla następnej liczby (n+1), należy najpierw udowodnić, że jest to prawdą, gdy n=1, a następnie wykorzystać założenie z kroku indukcyjnego, aby wykazać, że jest to również prawdą dla n+1.