Jacobsthalov niz svoj naziv duguje njemačkom matematičaru Ernstu Jacobsthalu (1882.–1965.). Spomenimo da je, osim po proučavanju ovoga niza, Jacobsthal poznat i po dokazu da se svaki prost broj oblika 4\cdot k+1, pri čemu je k\in\mathbb{N}, može prikazati kao zbroj kvadrata dvaju prirodnih brojeva. Taj je dokaz Jacobsthal 1906. godine izložio u svojoj doktorskoj disertaciji ,,Primjena jedne formule iz teorije kvadratnih ostataka”.

Jacobsthalov niz definiran je rekurzivno s: Iz (1) se lako dobiva prvih nekoliko članova Jacobsthalova niza: 0, 1, 1, 3, 5, 11, 21, 43, \dots
Osnovna rekurzija reda 2 navedena u (1) može se pojednostavniti svođenjem na rekurziju reda 1. Točnije, vrijedi sljedeća propozicija:

U nastavku ćemo odrediti zatvorenu formulu za opći član niza, tj. propis realne funkcije f jedne realne varijable takve da je J_{n}=f(n) . Vrijedi sljedeća propozicija:

Formula (4) može se izvesti i pomoću funkcije izvodnice za Jacobsthalov niz. Izvedimo najprije zatvorenu formu za tu funkciju. Podsjetimo, funkcija izvodnica za niz \left(a_{n}\right)_{n\in\mathbb{N}} je izraz Desna strana te jednakosti je formalni red potencija. Ako je moguće, treba odrediti zatvoreni oblik funkcije f , odnosno prikazati je kao izraz koji se sastoji od konačno mnogo članova i faktora. Pritom problem konvergencije desne strane jednakosti (6) zanemarujemo.

Prethodnu propoziciju dokazat ćemo na još jedan način.


Napomenimo da je niz (1) poseban slučaj poopćenoga Lucasova niza \left(L_{n}\right)_{n\in\mathbb{N}}. Taj se niz zadaje tako da se odaberu x,y\in\mathbb{Z} sa svojstvom x^{2}-4y\gt 0, pa se definira redom: Lako se provjeri da izborom x=1 i y=-2 dobivamo Jacobsthalov niz. Detalje ovdje izostavljamo, a mogu se naći u [1].


U ovoj ćemo točki dokazati nekoliko zanimljivih jednakosti vezanih uz Jacobsthalov niz. Najprije ćemo izračunati zbroj prvih n članova toga niza. Vrijedi sljedeća propozicija.

Poznato je da za niz Fibonaccijevih brojeva \left(F_{n}\right){}_{n\in\mathbb{N}} definiran s vrijedi Cassinijev identitet: (Detalji se mogu naći npr. u [4]). Analogon Cassinijeva identiteta za Jacobsthalov niz izriče sljedeća propozicija.

Posljednju propoziciju moguće je dokazati i na drugačiji način. Pokazat ćemo najprije da Jacobsthalove brojeve možemo izračunavati pomoću F-matrice koja je analogon Q-matrici1Q=\left(\begin{array}{cc} 1& 1\\\ 1& 0 \end{array}\right) za Fibonaccijeve brojeve. Točnije, vrijedi sljedeća propozicija.


U sljedeće dvije propozicije povezat ćemo članove Jacobsthalova niza i binomne koeficijente. Najprije ćemo pokazati da se svaki element Jacobsthalova niza može dobiti kao svojevrsna „linearna kombinacija“ potencija broja 2 s nenegativnim cjelobrojnim eksponentom čiji su „koeficijenti“ određeni binomni koeficijenti.

Iz Propozicija 3 i 13 izravno slijedi sljedeći identitet. Promotrimo sada svojevrsni obrat Propozicije 13, tj. „linearnu kombinaciju“ članova Jacobsthalova niza čiji su „koeficijenti“ binomni koeficijenti iz istoga retka Pascalova trokuta. (Detaljnije o binomnim koeficijentima i Pascalovu trokutu može se naći u [5].) Pomoću takvih „linearnih kombinacija“ mogu se dobiti sve potencije broja 3 kojima je eksponent nenegativan cijeli broj. Točnije, vrijedi sljedeća propozicija.

Posebno je zanimljiva veza članova Jacobsthalova niza s alternirajućim konvergentnim geometrijskim redom. Koristi se jednakost koja se dobiva tako da se u formulu za zbroj konvergentnoga geometrijskoga reda uvrsti x=-\frac{1}{2}. Međutim, n-ti djelomični zbroj reda (16) definiran s usko je povezan s Jacobsthalovim brojevima. O tome govori sljedeća propozicija.

Iz razmatranja ispred Propozicije 16 ili iz Propozicije 3 slijedi

Grubo rečeno, stanični automat je model dinamičnog fizikalnog sustava u kojem su vrijeme i prostor diskretizirani, a interakcije su samo lokalne. Svaki stanični automat sastoji se od regularne n-dimenzionalne rešetke, odnosno n-dimenzionalnog polja stanica (ćelija) od kojih je svaka u jednom od mogućih stanja. Ukupan broj takvih stanja je konačan.

Najjednostavnija klasa jednodimenzionalnih staničnih automata su elementarni stanični automati. Njegove stanice mogu biti u točno dva moguća stanja (0 ili 1). Stanice smještene neposredno lijevo i neposredno desno od promatrane stanice nazivamo susjedne stanice. Stanica i njezine dvije susjedne stanice tvore strukturu koju nazivamo konfiguracija. Svaka konfiguracija može imati ukupno 2^{3}=8 stanja. Za svaku konfiguraciju definiramo pravilo odlučivanja o vrijednostima stanica u sljedećem retku rešetke. To pravilo je funkcija koja svakoj stanici u 2., 3., 4,\dots, retku rešetke pridružuje 0 ili 1 zavisno o konfiguraciji smještenoj neposredno iznad te stanice. Zbog toga postoji ukupno 2^{8}=256 mogućih pravila pridruživanja.

Pravila za izgradnju rešetke elementarnih staničnih automata definirao je i opisao Stephen Wolfram 1983. godine. (Za detalje vidjeti [3].) Mi ćemo izdvojiti tzv. Pravilo 28. Ovo pravilo prikazano je na slici 1 kao i razvoj jedne crne ćelije nakon 15 koraka. Istaknimo da se „izgradnja“ rešetke zasniva na jednakosti (28)_{10}=(00011100)_{2}.

Formalno gledajući, Pravilo 28 je funkcija f:\left\lbrace 0,1\right\rbrace ^{3}\rightarrow\left\lbrace 0,1\right\rbrace definirana propisom

(Detaljnije o Pravilu 28 može se naći u [2] ili [3].) Ovo pravilo pregledno možemo zapisati u obliku tablice 1.

Promotrimo sliku 1, pa zaključimo kako smo na temelju prvoga retka dobili drugi redak. Kao osnovnu stanicu najprije uzimamo jedinu crnu ćeliju u prvom retku. Njezini lijevi i desni susjedi su bijele ćelije, pa imamo konfiguraciju „bijela–crna–bijela“ (vidjeti sliku 2).

Primjenom Pravila 28 na navedenu konfiguraciju kao rezultat dobivamo jednu crnu ćeliju (vidjeti sliku 3).

To znači da će prva ćelija u drugom retku rešetke biti crna (vidjeti sliku 4).

Pomaknimo se za točno jedno mjesto udesno od crne ćelije u prvom retku rešetke. Sada je osnovna stanica bijela ćelija. Njezin lijevi susjed je crna, a desni bijela ćelija, pa imamo konfiguraciju „crna–bijela–bijela“. Primjena Pravila 28 na tu konfiguraciju kao rezultat daje crnu ćeliju (vidjeti sliku 5).

Zbog toga će druga ćelija u drugomu retku rešetke također biti crna (vidjeti sliku 6).

Pomaknimo se za još jedno mjesto udesno. Osnovna stanica je bijela ćelija čiji su i lijevi i desni susjed također bijele ćelije. Stoga imamo konfiguraciju „bijela–bijela–bijela“. Primjena Pravila 28 na ovu konfiguraciju kao rezultat daje bijelu ćeliju (vidjeti sliku 7).

Stoga će treća ćelija u drugom retku rešetke biti bijela (vidjeti sliku 8).

Daljnjim pomicanjem udesno u prvom retku rešetke opet dolazimo na bijelu ćeliju kojoj su susjedi bijele ćelije, pa primjenom Pravila 28 kao rezultat opet dobivamo bijelu ćeliju. Tako zaključujemo da će sve ostale ćelije u drugom retku biti bijele i ne moramo ih dalje promatrati. U svakom retku rešetke uočimo blok ćelija koji počinje i završava crnom ćelijom, te takav da su lijevo i desno od toga bloka isključivo bijele ćelije. Takav blok sigurno postoji jer se u svakom retku rešetke nalazi barem jedna crna ćelija (dobivena primjenom Pravila 28 ili na konfiguraciju „bijela–crna–bijela“ ili „bijela–crna–crna“). Svakoj crnoj ćeliji uočenoga bloka pridružimo broj 1, a svakoj bijeloj broj 0. Na taj način svakom bloku bijektivno pridružujemo binarni broj koji počinje i završava znamenkom 1. Zapišemo li te binarne brojeve u dekadskom zapisu, dobivamo redom: Dobiveni brojevi tvore niz 1,3,5,11,21,\dots Iz ispisa prvih nekoliko članova Jacobsthalova niza naslućujemo da je dobiveni niz zapravo podniz Jacobsthalova niza. Pokazat ćemo da je ova slutnja točna, tj. da rešetka elementarnih staničnih automata dobivena primjenom Pravila 28 na gore opisani način zapravo generira podniz Jacobsthalova niza.

Pogledajmo najprije koje se sve konfiguracije mogu pojaviti unutar jednoga bloka. Pokažimo da se ni u jednom bloku ne mogu pojaviti „jednobojne“ konfiguracije, tj. konfiguracije „bijela–bijela–bijela“ i „crna–crna–crna“, kao ni konfiguracije „bijela–bijela–crna“ i „crna–bijela–bijela“. Najprije dokažimo da se ni u jednom bloku ne može pojaviti konfiguracija „crna–crna–crna“. Radi jednostavnosti, označimo tu konfiguraciju s C.

Pretpostavimo suprotno, tj. neka je n prvi redak u kojemu se pojavljuje C. Pogledajmo kako iz ćelija u (n-1)-vom retku rešetke može nastati C. Prema Pravilu 28 postoje tri mogućnosti.

Prva crna ćelija u C ne može nastati iz konfiguracije „crna–bijela–bijela“. Primjena Pravila 28 na konfiguraciju „bijela–bijela–bijela“, odnosno „bijela–bijela–crna“ kao rezultat daje bijelu, a ne crnu ćeliju. Zbog toga druga ćelija u C mora biti bijela, što je suprotno pretpostavci da C sadrži blok od tri crne ćelije.

Prva crna ćelija u C ne može nastati ni iz konfiguracije „bijela–crna–crna“. Primjena Pravila 28 na konfiguraciju „crna–crna–bijela“ kao rezultat daje bijelu ćeliju. Stoga je drugu crnu ćeliju u C moguće dobiti isključivo primjenom Pravila 28 na konfiguraciju „crna–crna–crna“. To bi značilo da se C pojavljuje i u (n-1)-vom retku, što je suprotno pretpostavci da je n prvi redak u kojemu se pojavljuje C.

Prva crna ćelija u C ne može nastati ni iz konfiguracije „bijela–crna–bijela“. Drugu crnu ćeliju u C tada bismo mogli dobiti isključivo iz konfiguracije „crna–bijela–bijela“, pa kao u prvoj mogućnosti zaključujemo da iz konfiguracije koja počinje dvjema bijelim ćelijama ni u kojem slučaju ne možemo dobiti treću crnu ćeliju u C.

Tako smo pokazali da se unutar jednoga bloka ne može pojaviti konfiguracija C. Potpuno analogno se pokazuje da se unutar jednoga bloka ne mogu pojaviti preostale tri spomenute konfiguracije. Detalje prepuštamo čitatelju.

Označimo s B_{n} prirodan broj čiji binarni zapis korespondira bloku u n-tom retku tablice elementarnih staničnih automata. Ne istaknemo li drugačije, pretpostavljamo da je n bilo koji prirodan broj. Pretpostavljamo i da je B_{n} zapisan u binarnom, a ne u dekadskom zapisu. Uočimo da je broj B_{n} neparan jer njegov binarni zapis završava znamenkom 1. (Dokaz tvrdnje da je prirodan broj neparan ako i samo ako njegov binarni zapis završava znamenkom 1 prepuštamo čitatelju.)



Budući da je B_{1}=1, iz Primjedbe 1 izravno slijedi da broj B_{n} u svojem zapisu ima točno n binarnih znamenaka.

Izračunajmo zbroj Z_{n}:=B_{n}+_{2}B_{n+1}. (S +_{2} označeno je binarno zbrajanje.) Broj Z_{n} je zbroj dvaju strogo pozitivnih prirodnih brojeva od kojih prvi ima n, a drugi n+1 znamenaka, pa Z_{n} ima ili n + 1 ili n + 2 znamenaka. Tvrdimo da je Z_{n} ima točno n + 2 znamenaka i da je jedino vodeća znamenka broja Z_{n} jednaka 1.

Brojevi B_{n} i B_{n+1} imaju posljednju znamenku jednaku 1. Stoga je posljednja znamenka broja Z_{n} jednaka 1 +_{2} 1 = 0. Navedenim zbrajanjem „nastaje“ jedinica koja se prenosi u zbroj znamenaka na pretposljednjim mjestima brojeva B_{n} i B_{n+1}.

Prema konstrukciji brojeva B_{n} navedenoj u Primjedbi 1, točno jedan od brojeva B_{n} i B_{n+1} ima pretposljednju znamenku 1, a drugi pretposljednju znamenku 0. Točnije, ako je n paran broj, onda je pretposljednja znamenka broja B_{n} jednaka 1 (jer smo broju B_{n-1} zdesna nadopisali 1), a pretposljednja znamenka broja B_{n+1} jednaka je 0 (jer smo između posljednje dvije znamenke broja B_{n} umetnuli nulu). Ako je n neparan broj, onda B_{n} ima pretposljednju znamenku 0, a B_{n+1} pretposljednju znamenku 1. U svakom je slučaju, dakle, pretposljednja znamenka broja Z_{n} jednaka 1 +_{2} 1 = 0. I na ovom mjestu opet „nastaje“ jedinica koja se prenosi u zbroj znamenaka na neposredno sljedećoj poziciji.

Neka je i prva pozicija (gledajući zdesna nalijevo) na kojoj broj Z_{n} ima znamenku 1. Pretpostavimo da je i\leq n. (Iz gornjih razmatranja slijedi i\geq 3.) Na i-toj poziciji broja Z_{n} dobit ćemo znamenku 1 ako i samo ako brojevi B_{n} i B_{n+1} na i-toj poziciji imaju jednake znamenke. Naime, (i-1)-va znamenka broja Z_{n} jednaka je nuli, pa se i-ta znamenka broja Z_{n} dobiva zbrajanjem i-te znamenke broja B_{n}, i-te znamenke broja B_{n+1} i jedinice „nastale“ zbrajanjem kojim je dobivena nula na (i-1)-voj poziciji. Ako bi brojevi B_{n} i B_{n+1} na i-toj poziciji imali različite znamenke, onda bi i-ta znamenka broja Z_{n} bila jednaka nuli, što je suprotno pretpostavci da je i prva pozicija na kojoj broj Z_{n} ima znamenku 1.

Uzmimo najprije da brojevi B_{n} i B_{n+1} na i-toj poziciji imaju nule. To znači da je bijela ćelija koja odgovara nuli na i-toj poziciji broja B_{n+1} dobivena primjenom Pravila 28 na konfiguraciju koja započinje bijelom ćelijom (koja odgovara nuli na i-toj poziciji broja B_{n}). Jedine dvije konfiguracije koje dolaze u obzir su „bijela–bijela–bijela“ i „bijela–bijela–crna“. Ranije smo pokazali da se te konfiguracije ne mogu pojaviti unutar jednoga bloka rešetke. Stoga na i-toj poziciji u brojevima B_{n} i B_{n+1} ne mogu biti nule.

Uzmimo sada da brojevi B_{n} i B_{n+1} na i-toj poziciji imaju jedinice. To znači da je crna ćelija koja odgovara jedinici na i-toj poziciji broja B_{n+1} dobivena primjenom Pravila 28 na konfiguraciju koja započinje crnom ćelijom (koja odgovara jedinici na i-toj poziciji broja B_{n}). Jedina konfiguracija koja dolazi u obzir je „crna–bijela–bijela“. Ranije smo pokazali da se ta konfiguracija ne može pojaviti unutar jednoga bloka rešetke. Stoga na i-toj poziciji u brojevima B_{n} i B_{n+1} ne mogu biti jedinice.

Time smo iscrpili sve moguće slučajeve, pa zaključujemo da je pretpostavka i\leq n bila pogrešna. Dakle, i\geq n+1. Gledajući zdesna nalijevo, znamenka na (n + 1)-vom mjestu broja B_{n} jednaka je 0 (jer B_{n} ima točno n znamenaka), dok je znamenka na (n + 1)-vom mjestu broja B_{n+1} jednaka 1 (to je vodeća znamenka broja B_{n+1}). Stoga je (n + 1)-va znamenka broja Z_{n} jednaka 0 +_{2} 1 +_{2} 1 = 0. (Posljednja jedinica u ovom zbroju „nastaje“ zbrajanjem kojim je dobivena nula na n-toj poziciji broja Z_{n}.) Odatle slijedi da broj Z_{n} ima točno n + 2 znamenaka, te da vrijedi jednakost: Tako smo pokazali da niz brojeva (B_{n})_{n\in\mathbb{N}} zadovoljava sljedeće jednakosti: Iz (1), (3) i (17) proizlazi da je niz (B_{n})_{n\in\mathbb{N}} zapravo podniz Jacobsthalova niza čiji je prvi član J_{2}. Preciznije, zaključujemo da za svaki n\in\mathbb{N} vrijedi jednakost: Iz (4) i (18) odmah slijedi zatvorena formula za opći član niza (B_{n})_{n\in\mathbb{N}}: Odaberemo li npr. n=21 i uvrstimo tu vrijednost u (19), dobit ćemo Stoga će 21. redak rešetke elementarnih staničnih automata izgledati kao na slici 10.

Zaključno napomenimo sljedeće. Budući da nam konfiguracija „crna–crna–crna“ nije bitna u postupku „izgradnje“ rešetke elementarnih staničnih automata, toj konfiguraciji umjesto broja 0 (kao u Pravilu 28) možemo pridružiti broj 1, a da se postupak „izgradnje“ rešetke elementarnih staničnih automata time nimalo ne promijeni. To pridruživanje zapravo znači da broj (00011100)_{2}=(28)_{10} zamjenjujemo brojem (10011100)_{2}=(156)_{10}, odnosno umjesto Pravila 28 primjenjujemo Pravilo 156. Tako smo dokazali sljedeću tvrdnju. Čitatelja zainteresiranoga za daljnja svojstva i primjene Jacobsthalova niza upućujemo na literaturu navedenu u donjem popisu.