5. Zadatak

Prvo rješenje

Ako broj $a_n$ završava s određenim brojem devetki, onda broj $a_n+1$ završava s isto toliko nula. Definirajmo niz $(b_n)$ tako da je $b_n=a_n+1$. Treba dokazati da $b_{11}$ završava s barem $2011$ nula. Vrijedi $b_0=10$.

Uvrštavanjem $a_k=b_k-1$ i $a_{k+1}=b_{k+1}-1$ u danu relaciju dobivamo

$$b_{k+1}-1=3(b_k-1)^4+4(b_k-1)^3,$$

odnosno

$$\begin{aligned} b_{k+1}-1={}&3(b_k^4-4b_k^3+6b_k^2-4b_k+1)\\ &+4(b_k^3-3b_k^2+3b_k-1), \end{aligned}$$

pa je

$$b_{k+1}=3b_k^4-8b_k^3+6b_k^2=b_k^2(3b_k^2-8b_k+6).$$

Iz dobivene formule zaključujemo da, ako $b_k$ završava s $m$ nula, onda $b_{k+1}$ završava s barem $2m$ nula. Kako $b_0$ završava s jednom nulom, slijedi da $b_1$ završava s dvije nule, $b_2$ s četiri nule, $b_3$ s $8$ nula, i općenito $b_k$ završava s (barem) $2^k$ nula. Broj $b_{11}$ završava s barem $2^{11}=2048$ nula, pa $a_{11}$ završava s barem $2048$ devetki. Time je tvrdnja dokazana.

Drugo rješenje

Pretpostavimo da $a_k$ završava s $l$ devetki, tj. da je

$$a_k=A\cdot10^l-1$$

za neki $A\in\mathbb N$. Tada je

$$a_{k+1}=3(A\cdot10^l-1)^4+4(A\cdot10^l-1)^3,$$

odnosno

$$\begin{aligned} a_{k+1} &=(A\cdot10^l-1)^3(3A\cdot10^l+1)\\ &=3A^4\cdot10^{4l}-8A^3\cdot10^{3l}+6A^2\cdot10^{2l}-1\\ &=10^{2l}\left(3A^4\cdot10^{2l}-8A^3\cdot10^l+6A^2\right)-1. \end{aligned}$$

A to znači da $a_{k+1}$ završava s $2l$ devetki. Kako $a_0$ završava s jednom devetkom, $a_1$ završava s dvije devetke, $\ldots$, $a_{11}$ završava s $2^{11}=2048$ devetki, čime je tvrdnja dokazana.