МАТЕМАТИ́ЧЕСКАЯ ИНДУ́КЦИЯ

МАТЕМАТИ́ЧЕСКАЯ ИНДУ́КЦИЯ, ме­тод до­ка­за­тель­ст­ва ма­те­ма­тич. ут­вер­жде­ний, ос­но­ван­ный на сле­дую­щем прин­ци­пе: ут­вер­жде­ние $A(x)$, за­ви­ся­щее от на­ту­раль­но­го па­ра­мет­ра $x$, счи­та­ет­ся до­ка­зан­ным для всех на­ту­раль­ных $x$, ес­ли до­ка­за­но ут­вер­жде­ние $A(1)$ и для лю­бо­го на­ту­раль­но­го чис­ла $n$ из пред­по­ло­же­ния, что вер­но ут­вер­жде­ние $A(n)$, сле­ду­ет, что вер­но так­же ут­вер­жде­ние $A(n+1)$. Этот прин­цип на­зы­ва­ет­ся прин­ци­пом ма­те­ма­тич. ин­дук­ции.

При­мер. Пусть для лю­бо­го на­ту­раль­но­го чис­ла $n$ тре­бу­ет­ся до­ка­зать фор­му­лу

$1+3+5+...+(2n-1)=n^2.\tag 1$

При $n=1$ эта фор­му­ла да­ёт вер­ное ра­вен­ст­во $1=1^2$. Что­бы до­ка­зать пра­виль­ность фор­му­лы (1) при лю­бом $n$, до­пус­ка­ют, что её уже уда­лось до­ка­зать для не­ко­то­ро­го на­ту­раль­но­го чис­ла $N$, т. е. пред­по­ла­га­ют, что

$1+3+5+...+(2N-1)=N^2, \tag 2$

и, опи­ра­ясь на это до­пу­ще­ние, до­ка­зы­ва­ют пра­виль­ность фор­му­лы (1) для чис­ла $n=N+1$. В дан­ном слу­чае дос­та­точ­но до­ба­вить к пра­вой и ле­вой час­тям ра­вен­ст­ва (2) сла­гае­мое $2N+ 1$, при этом по­лу­чит­ся ра­вен­ст­во

$1+3+5+...+(2N-1)+(2N+1)=N^2+(2N+1)$.

Т. к. пра­вая часть это­го ра­вен­ст­ва есть $(N+1)^2$, то из спра­вед­ли­во­сти (1) при $n=N$ вы­те­ка­ет спра­вед­ли­вость (1) при $n=N+ 1$ (ка­ко­во бы ни бы­ло $N$), т. е. (1) спра­вед­ли­во при всех на­ту­раль­ных $n$.

До­ка­за­тель­ст­во ут­вер­жде­ния $A(1)$ со­став­ля­ет пер­вый шаг (ба­зис) ин­дук­ции, а до­ка­за­тель­ст­во ут­вер­жде­ния $A(n+1)$ в пред­по­ло­же­нии, что вер­но $A(n)$, на­зы­ва­ет­ся ша­гом ин­дук­ции или ин­дук­ци­он­ным пе­ре­хо­дом. При этом $n$ на­зы­ва­ет­ся па­ра­мет­ром ин­дук­ции, а пред­по­ло­же­ние $A(n)$ при до­ка­за­тель­ст­ве ут­вер­жде­ния $A(n+1)$ на­зы­ва­ет­ся ин­дук­тив­ным пред­по­ло­же­ни­ем.

Прин­цип М. и. яв­ля­ет­ся так­же ос­но­ва­ни­ем для ин­дук­тив­ных оп­ре­де­ле­ний. Про­стей­шим при­ме­ром та­ко­го оп­ре­де­ле­ния яв­ля­ет­ся оп­ре­де­ле­ние свой­ст­ва «быть сло­вом дли­ны $n$ в дан­ном ал­фа­ви­те $𝒜=\{ a_1,a_2,...,a_k \}$». Ба­зис ин­дук­ции: ка­ж­дая бу­к­ва ал­фа­ви­та $𝒜$ есть сло­во дли­ны 1. Ин­дук­ци­он­ный пе­ре­ход: ес­ли $E$ – сло­во дли­ны $n$ в $𝒜$, то ка­ж­дое сло­во $Ea_i$, где к сло­ву $E$ спра­ва при­пи­сы­вает­ся бук­ва $a_i$, где $1 ⩽ i ⩽ k$, есть так­же сло­во дли­ны $n+ 1$ в $𝒜$. Ин­дук­ция мо­жет на­чи­нать­ся с $n=0$, т. е. с пус­то­го сло­ва.

М. и. мо­жет при­ме­нять­ся для до­ка­за­тель­ст­ва ут­вер­жде­ний $A(x)$, в ко­то­рых па­ра­метр $x$ про­бе­га­ет то или иное мно­же­ст­во, впол­не упо­ря­до­чен­ное по не­ко­то­ро­му транс­фи­нит­но­му ти­пу; в этом слу­чае го­во­рят о транс­фи­нит­ной ин­дук­ции.