Vrijeme: 02:03

Primjer 6: indukcija

Zadatak: Neka je (x_n)_{n\in\mathbb{N}} čiji članovi zadovoljavaju rekurzivnu formulu x_{n+1}=x_n+2n+1. Ukoliko je prvi član niza jednak 1 dokažite da je x_{2022} djeljiv s 36.

Rješenje Primjetimo specifičnost rekurzije koja je zadana. Ukoliko bi umjesto x_n pisalo n^2 imalo bismo da je x_{n+1}=n^2+n+1=(n+1)^2, dakle i za (n+1)-vi član niza bismo dobili da je jednak kvadratu svojeg rednog broja. Dakle, slutimo da je zadani niz zapravo niz kvadrata prirodnih brojeva, odnosno x_n=n^2. Ukoliko to pokažemo tada iz 2022=6\cdot 337 dobivamo x_{2022}=2022^2=36\cdot 337^2 iz čega slijedi 36\mid x_{2022}.

Činjenicu da je x_n=n^2 možemo dobiti na dva načina: ili ju korištenjem dane rekurzije dobijemo direktno (takozvani "glavom-kroz-zid" pristup ili "gruba sila"; najčešće treba zbrojiti neke članove tog niza) ili ju dokažemo korištenjem principa matematičke indukcije.

Gruba sila

Ukoliko u rekurzivno zadanom nizu sljedeći član niza na jednostavan način ovisi o prethodnom često se isplati zbrojiti prvih n članova niza \begin{aligned}
x_1+x_2+\ldots+x_n&=1+(x_1+2\cdot 1+1)+(x_2+2\cdot 2+1)+\ldots+\left[x_{n-1}+2\cdot(n-1)+1\right]\\
&=(x_1+x_2+\ldots+x_{n-1})+[2\cdot1+2\cdot2+\ldots+2\cdot(n-1)]+(\underbrace{1+1+\ldots+1}_{n-\text{puta}})\\
&=(x_1+x_2+\ldots x_{n-1})+2[1+2+\ldots+(n-1)]+n.
\end{aligned} Slijedi da je n-ti član niza jednak x_n=2[1+2+\ldots+(n-1)]+n. Primjetimo da u zagradi imamo sumu prvih (n-1) prirodnih brojeva. Budući da je suma prvih m prirodnih brojeva jednaka S_m=\frac{m(m+1)}{2} slijedi da je \begin{aligned}
x_n&=2\cdot\frac{(n-1)n}{2}+n\\
&=n^2-n+n\\
&=n^2.
\end{aligned}

Korištenje principa matematičke indukcije

Tvrdimo da za svaki prirodan broj n vrijedi x_n=n^2.

\begin{enumerate}
\item[\textbf{Baza indukcije}:]
Uvrštavanjem $n=1$ dobivamo $x_1=n^2=1^2=1$ za što iz teksta zadatka znamo da vrijedi.
\item[\textbf{Pretpostavka indukcije}:]
Pretpostavimo da tvrdnja vrijedi za neki prirodan broj $n$, dakle
$x_n=n^2$.
\item[\textbf{Korak indukcije}:]
Dokažimo da tada tvrdnja vrijedi i za sljedeći prirodan broj, $n+1$.

Iz formule rekurzije imamo da je $x_{n+1}=x_n+2n+1$, pa uvrštavanjem jednakosti iz pretpostavke indukcije dobivamo da je $$x_{n+1}=n^2+2n+1=(n+1)^2,$$ što smo i trebali dokazati.
\end{enumerate} Po principu matematičke indukcije slijedi da tvrdnja vrijedi za svaki prirodan broj n.

Napomena: Kao rješenje unesite 1.