2. Zadatak

Matematičkom indukcijom dokazujemo da za svaki prirodni broj $n$ vrijedi

$$x_n^2-y_n^2=8^n.$$

Baza indukcije, $n=1$, glasi:

$$x_1^2-y_1^2=3^2-1^2=8.$$

Pretpostavimo da za neki prirodni broj $k$ vrijedi $x_k^2-y_k^2=8^k$. Tada je

$$\begin{aligned} x_{k+1}^2-y_{k+1}^2 &=(3x_k+y_k)^2-(x_k+3y_k)^2\\ &=9x_k^2+6x_ky_k+y_k^2-(x_k^2+6x_ky_k+9y_k^2)\\ &=8x_k^2-8y_k^2=8(x_k^2-y_k^2)\\ &=8\cdot8^k=8^{k+1}. \end{aligned}$$

Prema principu matematičke indukcije slijedi $x_n^2-y_n^2=8^n$ za svaki prirodni broj $n$. Budući da smo tvrdnju dokazali za sve prirodne brojeve $n$, tvrdnja posebno vrijedi i za $n=2017$, što je traženo u zadatku.

Službeni alternativni završetak.

Izrazimo li iz prve rekurzivne relacije $y_n=x_{n+1}-3x_n$ i uvrstimo u drugu, dobivamo

$$x_{n+2}=6x_{n+1}-8x_n.$$

Iz zadanih početnih uvjeta dobivamo $x_1=3$, $x_2=10$. Postupak za rješavanje linearnih rekurzija prelazi okvire srednjoškolskog gradiva. Taj postupak daje zatvorenu formulu

$$x_n=\frac12(4^n+2^n)=2^{2n-1}+2^{n-1},$$

koju učenici mogu naslutiti na temelju malih slučajeva i onda dokazati matematičkom indukcijom.

Slijedi da je

$$y_n=x_{n+1}-3x_n=2^{2n-1}-2^{n-1}$$

i

$$x_n^2-y_n^2=(x_n+y_n)(x_n-y_n)=2^{2n}\cdot2^n=8^n.$$