Opgaver – Store Dag#
Opgave 1: Repetitionsopgave om rekursion#
Der defineres rekursivt en følge af tal \(c_0,c_1,c_2,\dots\) på følgende måde:
\(c_0=0\), \(c_1=1\), \(c_2=2\) og for \(n \ge 3\) gælder \(c_n=c_{n-1}c_{n-2}+c_{n-3}.\)
Hvilken værdier har \(c_3,c_4\) og \(c_5\)?
Svar
\(c_3=c_2c_1+c_0=2\cdot 1+0=2\)
\(c_4=c_3c_2+c_1=2\cdot 2+1=5\)
og
\(c_5=c_4c_3+c_2=5\cdot 2+2=12.\)
Opgave 2: Afledte funktioner og induktion#
Som kendt fra gymnasiet, gælder for alle \(n \in \mathbb{Z}_{\ge 1}\) at den afledte af \(x^n\) er lig med \(nx^{n-1}\), dvs. \((x^n)'=nx^{n-1}\). I denne opgave vises det ved hjælp af induktion. I må i denne opgave bruge at den afledte af \(x\) er \(1\), samt produktreglen \((f(x)\cdot g(x))'=f(x)'\cdot g(x)+f(x) \cdot g(x)'.\)
Spørgsmål a#
Formuler induktionsstarten (på engelsk: “base case of the induction”). Tjek bagefter at induktionsstarten holder.
Hint
Fordi der skal vises at \((x^n)'=nx^{n-1}\) for alle \(n \in \mathbb{Z}_{\ge 1}\), er induktionsstarten tilfældet hvor \(n=1\). Sæt derfor nu \(n=1\) ind i ligningen \((x^n)'=nx^{n-1}\) for at se helt præcist hvad man skal tjekke i induktionsstarten.
Svar
Induktionsstarten er udsagnet at formlen \((x^n)'=nx^{n-1}\) holder for \(n=1\). Med andre ord: induktionsstarten er udsagnet \((x^1)'=1\). Hvis man nu bruger at \(x^1=x\), \(x'=1\) og \(x^0=1\), følger resultatet efter nogle få mellemregninger.
Spørgsmål b#
Formuler nu induktionsskridtet. Hvad er induktionshypotesen i dette tilfælde?
Svar
Induktionshypotesen er at ligningen \((x^{n-1})'=(n-1)x^{n-2}\) holder for et vist \(n \ge 2\).
Spørgsmål c#
Vis at induktionsskridtet holder. Induktionsprincippet medfører nu at formlen \((x^n)'=nx^{n-1}\) holder for alle \(n \in \mathbb{Z}_{n \ge 1}.\)
Hint
Bemærk at \(x^n=x^{n-1} \cdot x\). Udforsk først hvad produktreglen siger hvis der vælges \(f(x)=x^{n-1}\) og \(g(x)=x\). Brug induktionshypotesen bagefter.
Svar
Produktreglen kombineret med induktionshypotesen giver at \((x^n)'=(n-1)x^{n-2} \cdot x+x^{n-1} \cdot 1=n x^{n-1}\).
Bemærk i øvrigt at formlen \((x^n)'=n x^{n-1}\) faktisk holder for alle reelle tal \(n\) og ikke kun for naturlige tal \(n\). At vise dette er dog ikke en del af opgaven.
Opgave 3: Summen af ulige tal og induktion#
Spørgsmål a#
Beregn for \(n=1,2,3,4\) summen af de første \(n\) ulige naturlige tal. Med andre ord: bestem værdien af \(\sum_{k=1}^n (2k-1)\) for \(n \in \{1,2,3,4\}.\) Er der et mønster i de fundne værdier? Find/gæt nu et kort udtryk for \(\sum_{k=1}^n (2k-1)\) som giver det rigtige svar for \(n \in \{1,2,3,4\}\) og check at dit gæt også giver den rigtige værdi for \(\sum_{k=1}^n (2k-1)\) hvis \(n=5.\)
Hint
De fundne værdier er altid kvadrater.
Svar
\(\sum_{k=1}^1 (2k-1) = 1\), \(\sum_{k=1}^2 (2k-1) = 4\), \(\sum_{k=1}^3 (2k-1) = 9\) og \(\sum_{k=1}^4 (2k-1) = 16\).
Baseret på ovenstående er det rimeligt at gætte at \(\sum_{k=1}^n (2k-1)=n^2\) er sandt for alle \(n\). For \(n=5\) passer gættet også: \(5^2=25\) og \(1+3+5+7+9=25\).
Spørgsmål b#
Lad \(P(n)\) være det logiske udsagn at \(\sum_{k=1}^n (2k-1)\) er lig med det korte udtryk du fandt i spørgsmål a. Målet er nu at vise at \(P(n)\) er sandt for alle naturlige tal \(n\) (dvs. for alle \(n \in \mathbb{N}=\mathbb{Z}_{\ge 1}\)).
Vis at induktionsstarten holder.
Hint
Induktionsstarten er udsagnet \(P(1)\). Med andre ord, for at vise at induktionsstarten holder, skal man skal vise at \(P(1)\) er sandt.
Svar
\(P(1)\) er udsagnet at \(\sum_{k=1}^1 (2k-1) = 1^2\), men det holder pga. spørgsmål a. Faktisk ved man fra spørgsmål a at \(P(n)\) holder for \(n \in \{1,2,3,4,5\}\), men i induktionsstarten behøver man her kun at tjekke for \(n=1\).
Spørgsmål c#
Gennemfør nu induktionsskridtet og brug bagefter induktionsprincippet til at konkludere at \(P(n)\) er sandt for alle naturlige tal \(n\).
Hint
I induktionsskridtet skal man vise for et vilkårligt heltal \(n \ge 2\) at implikationen \(P(n-1) \Rightarrow P(n)\) er sandt. Med andre ord: i induktionsskridtet man må antage at \(P(n-1)\) er sandt og derudfra vise at \(P(n)\) også er sandt.
Hint
I induktionsskridtet kan den rekursive definition af sum-tegnet som givet i Ligning (5.5) i lærebogen være nyttigt.
Opgave 4: At gange ind i parenteser#
Lad \(n \in \mathbb{Z}_{\ge 2}\) og \(a,b_1,\dots,b_n\) være komplekse tal. Vis følgende ved hjælp af induktion efter \(n\):
Man må bruge at ligningen holder for \(n=2\), ved at henvise til Theorem 3.2.2, 3. del fra lærebogen.
Hint
Induktionsstartet følger fra Theorem 3.2.2 hvis man i denne sætning vælger \(z_1=a\), \(z_2=b_1\) og \(z_3=b_2\).
Hint
Til indukstionsskridet: \(b_1+\cdots+b_n\) kan også skrives som \(\sum_{k=1}^n b_k\). Kan Ligning (5.5) fra lærebogen bruges?
Hint
Fra Ligning (5.5) i lærebogen ses \(\sum_{k=1}^n b_k = \left( \sum_{k=1}^{n-1} b_k\right)+b_n\). Derfor gælder
Kan Theorem 3.2.2 (3. del) nu bruges til at komme videre?
Opgave 5: Den geometriske række: del 1#
Spørgsmål a#
En hoppebold slippes to meter over gulvet. Efter at have ramt gulvet hopper den én meter op igen, anden gang en halv meter, en kvart meter tredje gang, osv. Altså faldhøjden halveres, for hvert påbegyndt nyt fald. Lad nu \(n\) være et naturligt tal. Hvilken afstand har bolden tilbagelagt, når den rammer gulvet for \(n\)’te gang?
Hint
Første gang bolden rammer gulvet har bolden tilbagelagt en afstand på to meter, fordi bolden holdes på to meters højde i starten: i alt altså \(2\) meter. Anden gang hopper bolden først en meter op igen for så at falde en meters afstand til den rammer gulvet: i alt har bolden derfor på det tidspunkt tilbagelagt \(2+2\cdot 1=4\) meter. Tredje gang hoppen den først en halv meter op og falder bagefter en halv meter ned: i alt fås nu \(2+2\cdot (1+\frac12)\) meter. Fjerde gang fås i alt på ligende måde: \(2+2\cdot (1+\frac12+\frac14)\). Kan du se et mønster og udtrykke det ved hjælp af sumtegnet?
Svar
Hvis \(n=1\) er svaret \(2\) meter, for \(n \ge 2\) er svaret \(2+2\cdot \sum_{j=0}^{n-2} \frac{1}{2^j}.\)
Opgave 6: Den geometriske række: del 2#
Lad \(r \in \mathbb{C} \setminus \{1\}\) være et komplekst tal og \(n\) et naturligt tal. I denne opgave vises følgende identitet:
Spørgsmål a#
Hvorfor må \(r\) ikke være lig med \(1\) i identiteten?
Svar
Hvis \(r=1\), så er nævneren i brøken \(\frac{r^{n+1}-1}{r-1}\) lig med nul. Derfor er brøken ikke defineret hvis \(r=1\).
Spørgsmål b#
Tjek at identiteten holder for \(n=1\).
Hint
Hvis man betragter udtrykket \(r^2-1\) som et polynomium i variablen \(r\), så har polynomiet rødder \(1\) og \(-1\). Brug nu Lemma 4.6.2 fra lærebogen til at skrive \(r^2-1\) som produkt af to førstegradspolynomier.
Spørgsmål c#
Vis at identiteten \(1+r+\cdots + r^n= \frac{r^{n+1}-1}{r-1}\) holder for alle naturlige tal \(n\).
Hint
Brug induktion efter \(n\). Bemærk at induktionsstarten allerede blev klaret i spørgsmål c.
Hint
Til induktionstrinnet: induktionshypotesen er at \(1+r+\cdots + r^{n-1}= \frac{r^{n}-1}{r-1}\). Brug nu at \(1+r+\cdots + r^{n}=(1+r+\cdots + r^{n-1})+r^n\) og bagefter induktionshypotesen.
Spørgsmål d#
Vi vender tilbage til hoppebolden fra Opgave 5. Hvor mange meter når hoppebolden at tilbagelægge inden den ligger stille på gulvet?
Hint
Hvis du vælger \(r\) og \(n\) klogt, så kan du simplificere udtrykket du blev bedt om at finde i Opgave 5 ved at bruge identiteten
Hvad får man nu når \(n\) går mod uendelig?
Svar
\(6\) meter.
Opgave 7: En ulighed#
En følge af reelle tal \(a_0,a_1,\dots\) bliver defineret rekursivt som følger:
\(a_1=0\) og \(a_n=\sqrt{2+a_{n-1}}\) hvis \(n \ge 2\).
Spørgsmål a#
Beregn \(a_1,a_2,a_3\) og \(a_4\).
Svar
\(a_1=0\), \(a_2=\sqrt{2}\), \(a_3=\sqrt{2+\sqrt{2}}\) og \(a_4=\sqrt{2+\sqrt{2+\sqrt{2}}}.\)
Eventuelt numerisk:
\(a_1=0.00000000000000000000000000000\).
\(a_2=1.41421356237309504880168872421\).
\(a_3=1.84775906502257351225636637879\).
\(a_4=1.96157056080646089825236447227\).
Spørgsmål b#
Påstanden er nu at der for alle naturlige tal \(n\) gælder, at \(a_n<2\). Bevis det vha. induktion efter \(n\).
Hint
I induktionsskridtet må man bruge at kvadratrodsfunktionen \(f: \mathbb{R}_{\ge 0} \to \mathbb{R}\) givet ved \(x\mapsto \sqrt{x}\), er strengt voksende.
Opgave 8: En sum med brøker#
Vis at identiteten
gælder for alle \(n \in \mathbb{N}.\)
Opgave 9: Areal under en parabel#
Lad \(N\) være et positivt reelt tal og \(n\) et naturligt tal. Vi definerer \(d=N/n\). Som kendt fra gymnasiet kan arealet mellem parablen og første aksen fra \(x=0\) til \(x=N\) beregnes som følger:
I denne opgave undersøges i hvilken grad dette areal tilnærmes med den endelige sum \(\sum_{k=1}^n d\cdot(kd)^2\). Situationen illustreres i følgende figur:
Spørgsmål a#
Brug tegningen til at indse at
Spørgsmål b#
Brug resultatet fra Opgave 4 til at indse at
Spørgsmål c#
Brug induktion efter \(n\) til at indse at \(\sum_{k=1}^n k^2=\frac13 n(n+1/2)(n+1)\) for alle naturlige tal \(n\).
Hint
I induktionsskridtet når man på et tidspunkt til formlen
Man kan gange alt ud og se om det giver det rigtige, men det kan bespare en hel del arbejde først at tage \(n\) udenfor parenteser:
Prøv nu først at indse at udtrykket indenfor parenteserne er lig med \(\frac13 (n+1/2)(n+1).\)
Svar
Induktionsstarten: Hvis \(n=1\), så gælder formlen, fordi \(\sum_{k=1}^1 k^2=1^2=1\) og \(\frac13 1(1+1/2)(1+1)=\frac{3}{3}=1\).
Induktionsskridtet: Hvis \(n \ge 2\) og der antages induktionshypotesen at \(\sum_{k=1}^{n-1} k^2=\frac13 (n-1)(n-1/2)n\), så fås
For eksempel ved at følge ovenstående vink, så kan man indse at \(\frac13 (n-1)(n-1/2)n+n^2=\frac13 n(n+1/2)(n+1)\), som betyder at induktionsskridtet holder. Induktionsprincippet medfører derfor at formlen \(\sum_{k=1}^n k^2=\frac13 n(n+1/2)(n+1)\) holder for alle naturlige tal \(n\).
Spørgsmål d#
Vis nu at \(\sum_{k=1}^n d\cdot (kd)^2=\frac{1}{3}N(N+d/2)(N+d)\).
Bemærkning: ligningen medfører at hvis \(N\) holdes fast og \(n\) går mod uendeligt, så går \(d\) mod nul og summen går derfor mod \(\frac13 N^3,\) som netop er arealet under parablen.
Svar
Fra de forrige spørgsmål fås
I den sidste lighed bruges at \(N=dn\).