Školjka

%V0 Lako se indukcijom dokaže da je$ a_n$ parno za parne $n$, odnosno neparno za neparne $n$. Nadalje, lako se pokaže sljedeća jednakost, za sve $k < n$: $$ a_n = a_{n-k}a_{k+1}+a_{n-k-1}a_{k}. $$ Motivacija za tu jednakost je raspisivanje rekurzije za elemente niza s desne strane jednakosti iz teksta zadatka, $k$ puta. Iz te jednakosti, za parne $n$ ($n=2m$) i za $k=m$ vrijedi $$ a_{2m} =a_m a_{m+1} + a_{m-1} a_{m} = a_m (2 a_m + a_{m-1} ) + a_{m-1} a_{m} = \ldots= 2 a_{m} (a_{m}+a_{m-1}).$$ Sada se dalje opet dokazuje indukcijom: ako $ 2^k || m$, tada (po pretpostavci indukcije) $ 2^k || a_m$, pa onda iz zadnje jednakosti zaključujemo $ 2^{k+1} || a_{2m}$, jer je $a_m+a_{m-1}$ neparan broj.