Koduülesannete lahendused

Reimo Palm

1. Jagame trepi pikkuse mõtteliselt n võrdseks lõikuks. Iga lõigu puhul on meil valida: kas tõsta see järgmise astme kõrgusele või jätta samaks. Kokku on vaja moodustada m astet, selleks tuleb n lõigust valida välja m kohta. Võimalusi selleks on

   æ è n m ö ø .

   Alternatiivid võivad tekkida seeläbi, kuidas toimida punktide A ja B ümbruses. Kui trepp peab algama astmega, siis jääb järele n-1 kohta, kuhu tuleb ära paigutada m-1 astet. Sellisel juhul on võimalusi C(n-1,m-1). Kui trepp peab lõppema astmega (st kogukõrgus on saavutatud juba enne punkti B jõudmist), siis on arutlus analoogiline ja võimalusi on samapalju. Kui pole muid kitsendusi peale selle, et trepi pindjoon peab algama punktist A ja lõppema punktis B, siis on sellel joonel n-1 võimalikku pöördekohta, millest tuleb välja valida need m, kus joon pöördub ülespoole. Siis on võimalusi C(n+1,m).

2. Kui binoomkordaja esimene indeks on väiksem kui teine, siis on binoomkordaja väärtus 0, sest pole ühtegi võimalust võtta vajalikku arvu elemente. Faktoriaale sisaldav arvutusvalem kehtib binoomkordaja puhul ainult siis, kui esimene indeks ei ole teisest väiksem.

   Tõestame võrduse induktsiooniga n järgi.

   Induktsiooni baas. Kui n = 0, siis taandub võrdus kujule

   0 å k = 0  æ è k m ö ø = æ è 1 m ö ø .

   Kui lisaks m = 0, siis on võrduse mõlema poole väärtus 1; kui aga m ³ 0, siis on mõlema poole väärtus 0.

   Induktsiooni samm. Eeldame, et võrdus kehtib n = s korral. Näitame, et siis kehtib võrdus ka n = s+1 korral. Tõepoolest,

   s+1 å k = 0  æ è k m ö ø = s å k = 0  æ è k m ö ø + æ è s+1 m ö ø = æ è s+1 m+1 ö ø + æ è s+1 m ö ø = æ è s+2 m+1 ö ø

   Paneme tähele, et siin me tõestasime ühekorraga mitu induktsiooni: vastavalt parameetri m väärtustele m = 1, m = 2, ....

3. Neid võrdusi võib samuti tõestada induktsiooniga.

   Esimene võrdus. Kui n = 1, siis on tõestataval võrdusel kuju F₁ = F₂. See võrdus kehtib, sest F₁ = F₂ = 1. Eeldame, et võrdus kehtib n = k korral. Näitame, et siis kehtib võrdus ka n = k+1 korral. Siis

   F1 + F3 + ... + F2k-1 + F2k+1 = F2k + F2k+1 = F2k+2,

   mida oligi tarvis tõestada.

   Teine võrdus. Kui n = 1, siis on tõestataval võrdusel kuju F₀ - F₁ + F₂ = F₁ - 1. See võrdus kehtib, mõlema poole väärtus on 0. Eeldame, et võrdus kehtib n = k korral. Näitame, et siis kehtib võrdus ka n = k+1 korral. Siis

   F0 - F1 + ... + F2k - F2k+1 + F2k+2 = F2k-1 - 1 - F2k+1 + F2k+2.

   Paremal poolel asendame F_2k+2 = F_2k+1 + F_2k, millega saame parema poole väärtuseks

   F2k-1 - 1 - F2k+1 + F2k+1 + F2k = F2k-1 + F2k - 1 = F2k+1 - 1,

   mida oligi tarvis tõestada.

   Kolmas võrdus. Kui n = 0, siis on tõestataval võrdusel kuju F₀² = F₀F₁. See võrdus kehtib, sest F₀ = 0. Eeldame, et võrdus kehtib n = k korral. Näitame, et siis kehtib võrdus ka n = k+1 korral. Siis

   F02 + F12 + ... + Fk2 + Fk+12 = FkFk+1 + Fk+12 = Fk+1(Fk + Fk+1).

   Fibonacci arvude definitsiooni põhjal on viimane avaldis võrdne arvuga F_k+1F_k+2.

4. Otsime A_n avaldist kujul A_n = qⁿ. Asendame selle rekurrentsesse võrrandisse ja taandame seejärel pooli arvuga q^n-1. Tulemuseks saame ruutvõrrandi

   q2 = q + 1,

   mille lahenditeks leiame

   q1 = 1+Ö5 2       q2 = 1-Ö5 2 .

   Antud võrrandi üldlahend avaldub järelikult kujul

   An = C1q1n + C2q2n.

   Kordajate määramiseks valime n = 0 ja n = 1 ning kasutame algtingimusi. Niiviisi saame lineaarse võrrandisüsteemi

   C1 + C2	=	1
   C1(1+Ö5)/2 + C2(1-Ö5)/2	=	3

   Lahendades selle süsteemi, saame

   C1	=	(1+Ö5)/2
   C2	=	(1-Ö5)/2

   Asendades need väärtused üldlahendi avaldisse, saame otsitava erilahendi

   An = ( 1+Ö5 2 )n+1 + ( 1-Ö5 2 )n+1.

5. Jagame kõik otsitavad n-elemendilised jadad kaheks vastavalt esimese elemendi väärtusele. Kui esimene element on 0, siis peab teine element olema 1 ja ülejäänud n-2 elementi moodustavad vajaliku omadusega jada. Kui esimene element on 1, siis moodustavad ülejäänud n-1 elementi vajaliku omadusega jada. Ilmselt saab suvalisest n-2-elemendilisest või n-1-elemendilisest jadast moodustada n-elemendilise jada, lisades jada algusesse vastavalt kas 01 või 1. Seetõttu kehtib seos

   sn = sn-1 + sn-2.

   Kui n = 1, siis leidub kaks jada: 0 ja 1. Kui n = 2, siis leidub kolm jada: 01, 10 ja 11. Kuna arvud s_n rahuldavad sama seost nagu Fibonacci arvud ja algliikmed on kaks järjestikust Fibonacci arvu 2 ja 3, siis langeb jada s_n kokku Fibonacci arvude jadaga, ainult indeksites on nihe. See tähendab,

   sn = Fn.

   Teades Fibonacci arvude üldavaldist, võime kohe välja kirjutada avaldise ka arvude s_n jaoks:

   sn = 1 Ö5 ( 1+Ö5 2 )n+2 - 1 Ö5 ( 1-Ö5 2 )n+2.