MetaMath '22 - Školjka

Vrijeme: 11:51

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$ .

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$. \textbf{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. \textbf{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}$$ \textbf{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$. \textbf{Napomena}: Kao rješenje unesite $1$.