2. Zadatak

Prvo rješenje.

Matematičkom indukcijom po $n$ dokazujemo da brojevi u $n$-tom retku čine aritmetički niz s razlikom $2^{n-1}$.

Za $n=2$ tvrdnja vrijedi, što vidimo direktno iz činjenice da su u drugom retku napisani uzastopni neparni brojevi.

Pretpostavimo da tvrdnja vrijedi za $n-1$ ($n>1$). Neka su $A$, $B$ i $C$ tri uzastopna broja u $(n-1)$-om retku te $A+B$ i $B+C$ uzastopni brojevi u $n$-tom retku. Prema pretpostavci indukcije vrijedi $B-A=C-B=2^{n-2}$, pa je

$$(B+C)-(A+B)=(C-B)+(B-A)=2^{n-2}+2^{n-2}=2^{n-1}.$$

Time smo pokazali da brojevi u $n$-tom retku čine aritmetički niz s razlikom $2^{n-1}$.

Neka je $a_n$ prvi broj u $n$-tom retku. Za sve $n\in\{2,\ldots,2016\}$ vrijedi

$$a_n=a_{n-1}+a_{n-1}+2^{n-2}=2a_{n-1}+2^{n-2}.$$

Koristeći ovu relaciju i $a_1=1$, indukcijom lako dokazujemo da je $a_n=(n+1)\cdot2^{n-2}$. Dakle, traženi broj je

$$a_{2016}=2017\cdot2^{2014}.$$

Drugo rješenje.

Uočimo da brojeve u drugom retku možemo zapisati na sljedeći način: $3=1+2$, $5=2+3$, $\ldots$, $4031=2015+2016$. To nazivamo standardnim rastavom elemenata drugog retka.

Za elemente u $n$-tom retku rekurzivno možemo definirati standardni rastav. Tako je standardni rastav $j$-tog elementa u $n$-tom retku zbroj oblika

$$\sum_{k=1}^{2016}p_{n,j,k}\cdot k,$$

pri čemu brojevi $p_{n,j,k}$, zbog načina na koji dobivamo elemente, zadovoljavaju relaciju

$$p_{n,j,k}=p_{n-1,j,k}+p_{n-1,j+1,k}.$$

Za $n=1$ imamo $p_{1,j,k}=0$ ako je $j\ne k$ te $p_{1,k,k}=1$.

Za fiksni $k\in\{1,\ldots,2016\}$ trokut koji formiraju elementi možemo prekriti Pascalovim trokutom kojemu je vrh u broju $k$ u prvom retku. Za $j$-ti element u $n$-tom retku pripadni $p_{n,j,k}$ iz standardnog rastava jednak je binomnom koeficijentu u Pascalovom trokutu iz $k$ koji prekriva taj element, tj. tvrdimo da vrijedi

$$p_{n,j,k}=\binom{n-1}{n-1+j-k}$$

za $\max\{1,k-n+1\}\le j\le\min\{k,2017-n\}$.

To možemo lako dokazati induktivnim zaključivanjem po $n$. Za $n=1$ je $p_{1,k,k}=1=\binom00$. Ako pretpostavimo da tvrdnja vrijedi za $n$ i $\max\{1,k-n+1\}\le j\le\min\{k,2017-n\}$, onda zbog Pascalove formule imamo

$$\begin{aligned} p_{n+1,j,k}&=p_{n,j,k}+p_{n,j+1,k}\\ &=\binom{n-1}{n-1+j-k}+\binom{n-1}{n+j-k}\\ &=\binom n{n+j-k}. \end{aligned}$$

Time je tvrdnja dokazana.

U zadnjem retku imamo jedan broj za čiji standardni rastav vrijedi $p_{2016,1,k}=\binom{2015}{2016-k}$, stoga je traženi broj jednak

$$\begin{aligned} \sum_{k=1}^{2016}k\binom{2015}{2016-k} &=\sum_{k=1}^{2016}k\binom{2015}{k-1}\\ &=\sum_{k=1}^{2016}(k-1)\binom{2015}{k-1}+\sum_{k=1}^{2016}\binom{2015}{k-1}\\ &=2015\sum_{k=2}^{2016}\binom{2014}{k-2}+\sum_{k=1}^{2016}\binom{2015}{k-1}\\ &=2015\cdot2^{2014}+2^{2015}=2017\cdot2^{2014}. \end{aligned}$$