Lukujono
Lukujono tai yksinkertaisesti jono on luettelo tietyn joukon alkioita.
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.
Tarkemmin lukujonolla (a) tarkoitetaan kuvausta
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) = a. Indeksoinnin ei välttämättä tarvitse alkaa nollasta, Katso esimerkiksi osajono. Lukuja a, a, a... nimitetään lukujonon jäseniksi. Jos lukujonon jäsenet ovat reaalilukuja, sanotaan, että (a) on reaalilukujono, jos taas jäsenet ovat rationaalilukuja, sanotaan, että (a) on rationaalilukujono, jne.
Jono on kasvava, jos kaikilla "n" pätee "x" ≤ "x" ja aidosti kasvava, jos kaikilla "n" pätee "x" < "x". Vastaavasti määritellään vähenevä ja aidosti vähenevä lukujono. Lukujono on monotoninen, jos se on joko kasvava tai vähenevä.
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 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.
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:
4. Kun määritellään
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:
Riippumatta äärellisen lukujonon jäsenten määrästä äärellisellä lukujonolla on aina olemassa maksimi ja minimi. Todistus:
Todistetaan väite induktiolla:
1. Alkuaskel: Olkoon joukko "X" =: {"x"}, jolloin sen maksimi (ja minimi) ovat selvästi luku "x". Eli väite pätee, kun joukossa on yksi alkio.
2. Induktio-oletus: Oletetaan, että mielivaltaisessa joukossa "A" on "n" alkiota eli #"A" = "n", ja että väite pätee eli joukolla "A" on maksimi, max "A".
3. Induktioaskel: Olkoon mielivaltaisessa joukossa "B" "n" + 1 alkiota. Poistetaan joukosta "B" jokin joukon alkio "b". Nyt saadussa joukossa, "C" =: "B"\{"b"}, on "n" alkiota, joten sillä on olemassa kohdan 2. nojalla maksimi, max "C". Täten myös joukolla "B" on olemassa maksimi ja se on max {max "C", "b"}. Induktioaskel pätee, joten väite on todistettu.
Samalla tavoin todistetaan minimin olemassaolo.
Kun lukujonosta vähennetään nolla tai enemmän alkioita ja järjestys säilytetään, nimitetään tällaista lukujonoa osajonoksi.
Esimerkiksi
Olkoon ("a, a, a, a, a", ... ) (termejä äärettömän monta) jono "a".
Tällöin jono ("a, a, a", ...) (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: "a, a, a, a", ...) jota merkitään joskus esimerkiksi "y" = ("y, y, y", ...). Tällöin pätee aina: "y" ≥ "n".
Todistus induktiolla:
Alkuaskel: "n" = 1, jolloin "y" on minimissään (maksimista ei luonnollisesti tarvitse välittää) 1. Tällöin pätee 1 ≤ "y".
Induktio-oletus: "n" ≤ "y".
Induktio-askel: "n"+1 ≤ "y"+1. Koska indeksit ovat luonnollisia lukuja, niin pätee "y"+1 ≤ "y", mistä seuraa: "n"+1 ≤ "y", MOT.
Jokaisella lukujonolla on monotoninen (eli nouseva tai laskeva) osajono.
Todistus:
1.) Joukossa "S" on ääretön määrä alkoita:
"S" = {"s, s, s, s, s", ... ), jossa siis "s" < "s" < "s" < ... < "s" < "s" < ... etc.
Jos "s" kuuluu joukkoon "S", niin "x" ≤ "x" eli osajono "x(s)" on nouseva.
2.) Joukko "S" on äärellinen:
"i".) Jos joukko "S" on tyhjä, valitaan "r" = 1.
"ii".) Jos joukko "S" ei ole tyhjä, valitaan "r" =: max "S" + 1.
Koska "r" ei kuulu joukkoon "S", on olemassa "r" > "r" siten, että "x" > "x".
Koska "r" ei kuulu joukkoon "S", on olemassa "r" > "r" siten, että "x" > "x".
etc.
Saadaan siis osajono, jossa "x" > "x", joka on siis aidosti laskeva.