Viber Закажи час

+381 62 16 43 066

Математичка индукција

Ако предикат (реченица) P(n)P\left( n \right), чија променљива nn   узима вредности из скупа природних бројева, задовољава следећа два услова:

  1. P(1)P\left( 1 \right) је тачан исказ,
  2. Из предпоставке да је P(k)P\left( k \right) тачан исказ за неки природан број kk, следи да је P(k+1)P\left( {k + 1} \right) тачан исказ, тј. P(k)⇒P(k+1)P\left( k \right) \Rightarrow P\left( {k + 1} \right) је тачан исказ, онда је P(n)P\left( n \right) тачан исказ за сваки природан број nn

Ово тврђење се у математици користи као метод за доказивање разних теорема. При том се доказ састоји из два корака. У првом, који се назива база индукције, доказује се тачност исказа P(1)P\left( 1 \right)., а у другом, који се назива индуктивни корак, доказује се тачност импликације P(k)⇒P(k+1)P\left( k \right) \Rightarrow P\left( {k + 1} \right). Исказ P(k)P\left( k \right) се назива индуктивна хипотеза (предпоставка). Ако P(n)P\left( n \right) важи за свако n⩾n0∈Nn \geqslant {n_0} \in \mathbb{N}, тада за базу индукције имамо, уместо P(1)P\left( 1 \right) , исказ P(n0)P\left( {{n_0}} \right).

Биномни коефицијенти

Факторијал

Факторијал n!n! произвољног целог броја n⩾0n \geqslant 0 је дефинисан са

0!=1,n!=(n−1)!⋅n,n=N0! = 1,\quad n! = \left( {n - 1} \right)! \cdot n,\quad n = \mathbb{N}.

Следи

n!=1⋅2⋅⋅⋅(n−1)⋅n,n∈Nn! = 1 \cdot 2 \cdot \cdot \cdot \left( {n - 1} \right) \cdot n,\quad n \in \mathbb{N}

Биномни коефицијет (nk)\left( {\begin{array}{cccccccccccccccccccc} n \\ k \end{array}} \right) се дефинише за  n∈Rn \in \mathbb{R}

(nk)={1,n(n−1)(n−2)(n−3)⋅⋅⋅(n−k+1)k!, k=0,k∈N.\left( {\begin{array}{cccccccccccccccccccc} n \\ k \end{array}} \right) = \left\{ {\begin{array}{cccccccccccccccccccc} {1,} \\ {\frac{{n(n - 1)(n - 2)(n - 3) \cdot \cdot \cdot (n - k + 1)}}{{k!}}} \end{array}{\text{, }}\begin{array}{cccccccccccccccccccc} {k = 0,} \\ {k \in \mathbb{N}.} \end{array}} \right.

Нека је k⩽nk \leqslant n и k,n∈Nk,n \in \mathbb{N}. Тада је

(nk)=n!k!(n−k)!; (nk)=(nn−k); (n−1k)+(n−1k−1)=(nk).\left( {\begin{array}{cccccccccccccccccccc} n \\ k \end{array}} \right) = \frac{{n!}}{{k!\left( {n - k} \right)!}};{\text{ }}\left( {\begin{array}{cccccccccccccccccccc} n \\ k \end{array}} \right) = \left( {\begin{array}{cccccccccccccccccccc} n \\ {n - k} \end{array}} \right);{\text{ }}\left( {\begin{array}{cccccccccccccccccccc} {n - 1} \\ k \end{array}} \right) + \left( {\begin{array}{cccccccccccccccccccc} {n - 1} \\ {k - 1} \end{array}} \right) = \left( {\begin{array}{cccccccccccccccccccc} n \\ k \end{array}} \right).

Биномна формула

Нека је a,b∈Ra,b \in \mathbb{R} и n∈Nn \in \mathbb{N}. Тада је

(a+b)n=(n0)an+(n1)an−1b+(n2)an−2b2+⋅⋅⋅+(nn−1)abn−1+(nn)bn,{\left( {a + b} \right)^n} = \left( {\begin{array}{cccccccccccccccccccc} n \\ 0 \end{array}} \right){a^n} + \left( {\begin{array}{cccccccccccccccccccc} n \\ 1 \end{array}} \right){a^{n - 1}}b + \left( {\begin{array}{cccccccccccccccccccc} n \\ 2 \end{array}} \right){a^{n - 2}}{b^2} + \cdot \cdot \cdot + \left( {\begin{array}{cccccccccccccccccccc} n \\ {n - 1} \end{array}} \right)a{b^{n - 1}} + \left( {\begin{array}{cccccccccccccccccccc} n \\ n \end{array}} \right){b^n},

или краће

(a+b)n=∑k=0n(nk)an−kbk.{\left( {a + b} \right)^n} = \sum\limits_{k = 0}^n {\left( {\begin{array}{cccccccccccccccccccc} n \\ k \end{array}} \right){a^{n - k}}{b^k}.}

Математичка индукција доказује да тврђење P(n)P(n) важи за сваки природан број nn. Доказ има два корака. База индукције: проверите да је P(1)P(1) тачно. Индуктивни корак: претпоставите да важи P(k)P(k) (индуктивна хипотеза) и из тога изведите P(k+1)P(k+1). Као код низа домина: прва пада, а свака обара следећу, па падају све. Ако тврђење важи тек од неког n0n_0, база је P(n0)P(n_0).

Индукцијом се доказује и биномна формула (a+b)n=∑k=0n(nk)an−kbk(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k, где је (nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k!(n-k)!}. Најчешће грешке су да се база прескочи или да се у кораку не искористи хипотеза.

135791113579110
11
У k редова
66
Нови ред
12
У k + 1 редова
78
Плава пирамида има kk редова и по хипотези k(k+1)2\frac{k(k+1)}{2} лименки. Са зеленим редом од k+1k + 1 лименке укупно их је (k+1)(k+2)2\frac{(k+1)(k+2)}{2}, а то је иста формула за k+1k + 1 редова.

Програмери индукцијом доказују да петља или рекурзивна функција даје тачан резултат за сваки улаз, а не само за улазе које су испробали.

Пирамида од лименки

Радник у продавници слаже лименке у пирамиду уза зид: у горњем реду је једна лименка, а сваки ред испод има једну више. Докажите индукцијом да у nn редова има n(n+1)2\frac{n(n+1)}{2} лименки, па израчунајте колико лименки треба за пирамиду од 12 редова.

Решење

  1. Тврђење P(n)P(n) гласи 1+2+⋯+n=n(n+1)21 + 2 + \cdots + n = \frac{n(n+1)}{2}. База: за n=1n = 1 лева страна је 1, а десна 1⋅22=1\frac{1 \cdot 2}{2} = 1.
  2. Хипотеза: за неко kk важи 1+2+⋯+k=k(k+1)21 + 2 + \cdots + k = \frac{k(k+1)}{2}.
  3. Корак: пирамиди од kk редова додамо ред од k+1k + 1 лименке. По хипотези их је укупно k(k+1)2+(k+1)=(k+1)(k+2)2\frac{k(k+1)}{2} + (k + 1) = \frac{(k+1)(k+2)}{2}, а то је формула за n=k+1n = k + 1.
  4. Формула зато важи за свако nn, па за 12 редова треба 12⋅132=78\frac{12 \cdot 13}{2} = 78 лименки.

Одговор: За пирамиду од 12 редова потребно је 78 лименки.

Задатак за вежбу

Докажите индукцијом да је 1+3+5+⋯+(2n−1)=n21 + 3 + 5 + \cdots + (2n - 1) = n^2, па израчунајте збир првих 15 непарних бројева.

Прикажи решење

База: 1=121 = 1^2. Корак: из хипотезе 1+3+⋯+(2k−1)=k21 + 3 + \cdots + (2k - 1) = k^2 следи k2+(2k+1)=(k+1)2k^2 + (2k + 1) = (k + 1)^2. Збир првих 15 непарних бројева је 152=22515^2 = 225.