Točno
31. srpnja 2013. 18:58 (10 godine, 11 mjeseci)
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Kliknite ovdje kako biste prikazali rješenje.
Lako se indukcijom dokaže da je
parno za parne
, odnosno neparno za neparne
.
Nadalje, lako se pokaže sljedeća jednakost, za sve
:
Motivacija za tu jednakost je raspisivanje rekurzije za elemente niza s desne strane jednakosti iz teksta zadatka,
puta.
Iz te jednakosti, za parne
(
) i za
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}).](/media/m/9/d/c/9dcd0706852061f1725610cd9535034d.png)
Sada se dalje opet dokazuje indukcijom: ako
, tada (po pretpostavci indukcije)
, pa onda iz zadnje jednakosti zaključujemo
, jer je
neparan broj.
![a_n](/media/m/1/f/f/1ff6f81c68b9c6fb726845c9ce762d7a.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
Nadalje, lako se pokaže sljedeća jednakost, za sve
![k < n](/media/m/1/0/d/10dfb93470e543461f7c54e7ae3d2dd5.png)
![a_n = a_{n-k}a_{k+1}+a_{n-k-1}a_{k}.](/media/m/9/c/8/9c88bb00b039f00103576d4ee02098a7.png)
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
Iz te jednakosti, za parne
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n=2m](/media/m/4/e/4/4e421abee0a2da25eba7f4807f5082d8.png)
![k=m](/media/m/d/e/a/deac00471e7dd161b412d15fbf30dd4f.png)
![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}).](/media/m/9/d/c/9dcd0706852061f1725610cd9535034d.png)
Sada se dalje opet dokazuje indukcijom: ako
![2^k || m](/media/m/a/3/1/a31a6e5d65909bd50b384d2708f4b3d5.png)
![2^k || a_m](/media/m/5/9/9/59956d24a427297ff0db911037c09dde.png)
![2^{k+1} || a_{2m}](/media/m/f/c/b/fcb8b882a2a07597470be007ef20bd83.png)
![a_m+a_{m-1}](/media/m/b/f/3/bf3dff2a732a8e9ab0c0eadaeaf916c9.png)