Lukujono

Lukujono tai yksinkertaisesti jono on järjestetty luettelo tietyn lukujoukon alkioista. 
Lukujono on "äärellinen" eli "päättyvä", jos sen pituus on rajattu, ja se on puolestaan "ääretön" eli "päättymätön", jos siinä ei ole viimeistä jäsentä. Esimerkiksi (1, 2, 3, 4) ja (9, 66, 102, 9, 102) ovat päättyviä, (e, e, e, e...) ja (2, 4, 6...) päättymättömiä lukujonoja.
Määritelmä.
Tarkemmin lukujonolla (an) tarkoitetaan kuvausta
formula_1
missä formula_2 on luonnollisten lukujen joukko ja formula_3 mikä tahansa lukujoukko. Usein K=N, Q, R tai C.
Lukujonoa merkitään a(n) = an. Indeksoinnin ei välttämättä tarvitse alkaa nollasta, Katso esimerkiksi osajono. Lukuja a0, a1, a2... nimitetään lukujonon jäseniksi. Jos lukujonon jäsenet ovat reaalilukuja, sanotaan, että (an) on reaalilukujono, jos taas jäsenet ovat rationaalilukuja, sanotaan, että (an) on rationaalilukujono, jne.
Jono on kasvava, jos kaikilla "n" pätee "xn" ≤ "xn+1" ja aidosti kasvava, jos kaikilla "n" pätee "xn" &lt; "xn+1". Vastaavasti määritellään vähenevä ja aidosti vähenevä lukujono. Lukujono on monotoninen, jos se on joko kasvava tai vähenevä.
Erikoistapauksia.
Aritmeettinen lukujono.
Aritmeettinen lukujono on sellainen lukujono, jonka peräkkäisten jäsenten erotus formula_4 on vakio. Aritmeettisen lukujonon yleinen termi on formula_5.
Geometrinen lukujono.
Geometrinen lukujono on sellainen lukujono, jonka peräkkäisten jäsenten osamäärä formula_6 on vakio. Jos formula_6 on esimerkiksi 1,1, tarkoittaa se sitä, että lukujonon seuraava jäsen on aina 10% edellistään suurempi. Esim. formula_8 . 
Geometrisen lukujonon yleinen termi on formula_9.
Esimerkkejä.
1. formula_10 tarkoittaa luonnollisten lukujen jonoa, joka on määritelty analyyttisesti ja jossa formula_11 ...
2. formula_13 tarkoittaa luonnollisten lukujen jonoa, jossa formula_14
3. Fibonaccin luvut määritellään rekursiivisesti:
 formula_15
4. Kun määritellään
formula_17
 saadaan lukujono 2, 22 = 4, 42 = 16, 162 = 256, 2562 = 65536..., ts. a0=2, a1=4, a2=16, a3=256...
5. Lukujono 1, 2, 3, 5, 7, 11, 15, 22, 30, 42... kuvaa sitä, kuinka monella tavalla postitiiviset kokonaisluvut 1, 2, 3... voidaan jakaa kokonaislukupartitioihin eli kokonaislukuihin, joiden summaksi tulee luku itse. Esim. luvulle viisi saadaan seitsemän erilaista ryhmää: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1 ja 1+1+1+1+1.
6. Lukujono 1, 2, 6, 19, 63, 216, 760, 2725, ... kuvaa ns. kiinnitettyjen (ts. esim. peilikuvat katsotaan erillisiksi tapauksiksi) polyominojen lukumäärää alkioiden lukumäärän n (1, 2, 3, ...) funktiona. Polyominoja voi tutkia myös piirtämällä ruutupaperille pisteitä viivojen risteyskohtiin siten, että mikään piste ei ole muusta kuviosta erillään. Esimerkiksi kolmen pisteen tapauksessa saadaan kuusi hahmoa:
Lukujonon maksimi ja minimi.
Riippumatta äärellisen lukujonon jäsenten määrästä äärellisellä lukujonolla on aina olemassa maksimi ja minimi eli suurin ja pienin alkio. Väite todistetaan induktiolla. 
Todistus.
Alkuaskel.
Olkoon joukko formula_18, joten sen maksimi (ja minimi) on itsestään selvästi luku formula_19. Väite siis pätee, kun joukon alkioiden lukumäärä on yksi. 
Induktio-oletus.
Oletetaan, että mielivaltaisessa äärellisessä joukossa formula_20 on formula_21 määrä alkiota eli formula_22 ja että väite pätee. Tällöin joukolla formula_20 on olemassa maksimi eli formula_24. 
Induktioaskel.
Olkoon formula_25 mielivaltainen joukko, jossa on formula_26 määrä alkiota. Poistetaan joukosta formula_25 sen jokin alkio formula_28. Nyt saadaan joukko formula_29, jossa on formula_21 määrä alkiota, joten sillä on olemassa induktio-oletuksen nojalla formula_31. Täten myös joukolla formula_25 on olemassa maksimi, joka on formula_33. 
Induktioperiaatteen nojalla mille tahansa mielivaltaiselle äärelliselle joukolle formula_34, jolla formula_35, löydetään aina maksimi. Vastaavalla tavalla todistetaan minimin olemassaolo.
Osajono.
Kun lukujonosta vähennetään nolla tai enemmän alkioita ja järjestys säilytetään, nimitetään tällaista lukujonoa osajonoksi. 
Esimerkiksi
Olkoon ("a1, a2, a3, a4, a5", ... ) (termejä äärettömän monta) jono "a". 
Tällöin jono ("a2, a4, a5", ...) (termejä silti äärettömän monta) on eräs jonon "a" osajono. 
Huomioitavaa on, että lukujono on myös itse itsensä eräs osajono. 
Osajonon indeksitkin muodostavat oman jononsa (osajono voidaan tällöin esittää muodossa: "ay1, ay2, ay3, ay4", ...) jota merkitään joskus esimerkiksi "y" = ("y1, y2, y3", ...). Tällöin pätee aina: "yn" ≥ "n". 
Todistus induktiolla: 
Alkuaskel: "n" = 1, jolloin "y1" on minimissään (maksimista ei luonnollisesti tarvitse välittää) 1. Tällöin pätee 1 ≤ "y1". 
Induktio-oletus: "n" ≤ "yn". 
Induktio-askel: "n"+1 ≤ "yn"+1. Koska indeksit ovat luonnollisia lukuja, niin pätee "yn"+1 ≤ "yn+1", mistä seuraa: "n"+1 ≤ "yn+1", MOT.
Jokaisella lukujonolla on monotoninen osajono.
Todistus.
Olkoon joukko formula_36. 
formula_37 Joukossa formula_38 on ääretön määrä alkoita. 
formula_39, jolle pätee formula_40 ja formula_41 kaikilla formula_42. Täten osajono formula_43 on kasvava. 
formula_44 Joukko formula_38 on äärellinen. 
formula_46 Joukko formula_38 on tyhjä, jolloin valitaan formula_48. 
formula_49 Joukko formula_38 on epätyhjä, jolloin valitaan formula_51. 
Nyt koska formula_52, niin on olemassa formula_53 siten, että formula_54. Induktiolla voidaan osoittaa, että kaikilla formula_42 on olemassa formula_56 siten, että formula_57 ja formula_58. Täten osajono formula_59 on aidosti laskeva. 
Ollaan siis löydetty lukujonolle formula_60 kasvava osajono formula_43 tai aidosti laskeva osajono formula_59 eli joka tapauksessa monotoninen osajono. formula_63