Matematička indukcija - primeri

itc »Strukture podataka i algoritmi » Matematička indukcija » Primeri

Pretpostavimo da želimo da dokažemo iskaz:

(1)
\begin{align} 1+2+3+ ... + n = \frac{n(n+1)}{2} \end{align}

Za sve prirodne brojeve $n$.

Obeležimo ovaj iskaz sa $P(n)$.
Ovo je jednostavna formula za sumu pozitivnih prirodnih brojeva manjih ili jednakih broju $n$.
Dokaz da je ovaj iskaz tačan za sve prirodne brojeve $n$ sledi.

1. Proverimo da li je iskaz tačan za $n=1$:

Suma samog broja 1 je prosto 1. Takodje je i

(2)
\begin{align} \frac{1(1+1)}{2} = 1 \end{align}

što znači da je izraz tačan za $n=1$.


Sada moramo da pokažemo da ako iskaz važi kada je $n = m$, onda on takođe važi i kada je $n = m + 1$. Ovo se može izvesti na sledeći način.

Pretpostavimo da je iskaz tačan za n = m, tj,

(3)
\begin{align} 1+2+3+ ... + m = \frac{m(m+1)}{2} \end{align}

Dodavanjem $m + 1$ sa obe strane se ne menja jednakost:

(4)
\begin{align} 1+2+3+ ... +m+(m+1) = \frac{m(m+1)}{2} +(m+1) \end{align}

Algebarskom manipulacijom, sa desne strane dobijamo

(5)
\begin{align} = \frac{m(m+1)}{2} +\frac{2(m+1)}{2} = \frac{(m+2)(m+1)}{2} = \frac{(m+1)(m+2)}{2} = \frac{(m+1)((m+1)+1)}{2} \end{align}

Na kraju imamo

(6)
\begin{align} 1+2+3+ ... + (m+1) = \frac{(m+1)((m+1)+1)}{2} \end{align}

Primetimo da je ovo ekvivalentno tvrđenju $P(m + 1)$. Ovaj dokaz je kondicionalan: načinili smo pretpostavku da je $P(m)$ tačno, i iz toga smo izveli $P(m + 1)$. Stoga, ako je $P(m)$ tačno, onda i $P(m + 1)$ mora biti tačno. Simbolički, pokazali smo da

(7)
\begin{align} P(m) \Rightarrow P(m+1) \end{align}

Sada, kako bismo završili, koristimo proces matematičke indukcije:

1. Znamo da je $P(1)$ tačno.
2. Kako $P(1)$ implicira $P(1 + 1)$, tačno je i $P(2)$.
3. Slično, kako $P(2)$ implicira $P(2 + 1)$, dobijamo $P(3)$.
4. Sa $P(3)$, dobijamo $P(4)$.
5. Iz $P(4)$, sledi $P(5)$.
6. I tako dalje. (ovde nastupa aksioma matematičke indukcije.)
7. Možemo da zaključimo da $P(n)$ važi za svaki prirodan broj $n$.

Unless otherwise stated, the content of this page is licensed under GNU Free Documentation License.