Opgaver – Lille Dag#
Opgave 1: Python opgave#
Rekursive definitioner kan i den grad bruges til at lave computerberegninger. I denne opgave gives nogle eksempler på det.
Spørgsmål a#
Fakultetsfunktionen blev defineret i Example 5.1.1 fra lærebogen. Især blev der givet en rekursiv definition i Ligning (5.1) og en pseudokode beskrivelse i starten af eksempet (Algorithm 8). Om nødvendigt, genopfrisk din hukommelse, især hvad angår pseudokoden. Følgende Pythonkoden er en direkte “oversættelse” til Python af pseudokoden fra Algorithm 8 i lærebogen.
def fac(n):
if n == 1: # This is the base case
return 1
else: # This is the recursive case
return(fac(n-1)*n)
Kopier Pythonkoden ved at klikke i det grå tekstfelt øverst til høje. Indsæt bagefter teksten i command console Python. Afprøv nu kommandoen fac(5). Giver det resultatet du forventer? Hvad med fac(500) og fac(1000)?
Trouble shooting
Hvis af en eller anden grund prompten i command consolen ser ud som ... efter man har indført Pythonkoden, tryk på Enter-knappen indtil prompten skifter udseende til >>>. Nu burde man kunne indtaste kommandoen fac(5).
Svar
fac(5) og fac(500) giver de rigtige svar.
fac(1000) giver dog som regel en fejlmelding, fordi funktionen kalder sig selv for mange gange. Matematisk set er der ikke noget galt, men alle computersystemer har deres grænser. Her opdager man at der er en grænse for hvor mange gange en funktion må kalde sig selv rekursivt i Python. Standard Python har en såkaldt rekursionsdybde på 1000.
Spørgsmål b#
For at afprøve rekursive definitioner yderligere, skriver nogen følgende Python kode for at definere en funktion \(h: \mathbb{N} \to \mathbb{R}\) rekursivt:
def h(n):
if n == 1: # This is the base case
return 11
else: # This is the recursive case
return(h(n**2-5*n+7))
Kopier koden ind i command console Python og kør kommandoerne h(1), h(2), h(3) og h(4). Check i hånden at outputtet er hvad det skulle være.
Spørgsmål c#
Prøv nu at beregne \(h(5)\) i hånden. Hvad er problemet? Afprøv alligevel kommandoen h(5) i Python, men husk at man kan afbryde Pythonprogrammet med Ctrl-c (dvs. tryk på Ctrl knappen, hold den indtrykket, mens man trykker på c knappen).
Hint
Der et lignende problem med den rekursive definition af funktionen \(g\) lige inden Example 5.1.2 i lærebogen.
Svar
Hvis man prøver at beregne \(h(5)\) i hånden, fås
Man ser derfor at i hvert iteration, \(h\) kalder sig selv for en større inputværdi end før. Derfor afslutter rekursionen aldrig.
Opgave 2: Rekursioner af dybde to.#
Spørgsmål a#
En følge af tal \(c_1,c_2,c_3,\dots\) er defineret som følger:
\(c_1=3\), \(c_2=1\) og \(c_{n}=n\cdot c_{n-1}+c_{n-2}\) hvis \(n \ge 3\).
Beregn i hånden \(c_6\).
Hint
Læs eventuelt først den rekursive definition af Fibonacci-tallene i Example 5.1.2 i lærebogen.
Hint
Tallene \(c_1\) og \(c_2\) er kendte. Derfor kan man beregne \(c_3\) ud fra den rekursive definition. Den giver nemlig formlen \(c_3=3c_2+c_1\) for \(n=3\). Bagefter kan \(c_4\) beregnes, så \(c_5\) osv.
Svar
\(c_6=811\) (undervejs i beregningen vil man også have fået at \(c_3=6\), \(c_4=25\) og \(c_5=131\)).
Spørgsmål b#
En anden følge af tal \(d_1,d_2,d_3,\dots\) er defineret som følger:
\(d_1=1\), \(d_2=2\) og \(d_{n}=d_{n-1}d_{n-2}-n+1\) hvis \(n \ge 3\).
Tjek at \(d_6=7\).
Hint
Ligesom i spørgsmål a er det en god strategi at beregne \(d_3\) først, så \(d_4\), osv.
Hint
Rekursionen giver at \(d_3=d_2d_1-3+1\), \(d_4=d_3d_2-4+1\), osv.
Svar
Mens man regner, vil man få at \(d_3=0\), \(d_4=-3\), \(d_5=-4\) og til sidst \(d_6=7\).
Opgave 3: Priknotation#
Givet et naturligt tal \(n\) og komplekse tal \(a_1,\dots,a_n\), så betegnes summen af disse komplekse tal med \(a_1+\cdots+a_n\) eller nogle gange også med \(a_1+a_2+\cdots+a_n\). I denne opgave undersøges nogle eksempler.
Spørgsmål a#
Der defineres \(a_k=2k\) for \(k=1,2,3,4\). Hvad er \(a_1+\cdots+a_n\) hvis \(n=4\)? Og hvad hvis \(n=3\)?
Svar
\(n=4\): \(a_1+a_2+a_3+a_4=2+4+6+8=20\).
\(n=3\): \(a_1+a_2+a_3=2+4+6=12\).
Spørgsmål b#
Det samme spørgsmål, men nu for \(n=2\) og for \(n=1\).
Svar
\(n=2\): \(a_1+a_2=2+4=6\). Det vil sige at “prikkerne” egentlig bare skal ignoreres i notation \(a_1+\cdots+a_n\) hvis \(n=2\).
\(n=1\): Nu er svaret blot \(a_1=2\). Det vil sige at notation \(a_1+\cdots+a_n\) for \(n=1\) kan være lidt misvisende, fordi man egentlig ikke har en sum med flere led, men blot leddet \(a_1\). Dette er en af grundene at nogle foretrække at bruge sumtegn-notationen (\(\sum\)-notationen).
Spørgsmål c#
Betragt funktionen \(f: \mathbb{N} \to \mathbb{C}\) med forskrift \(f(k)=k^2-k\). Beregn \(f(1)+\cdots + f(n)\) for \(n=1,2,3\) og \(4\).
Svar
\(n=1\): \(f(1)=0\).
\(n=2\): \(f(1)+f(2)=0+2=2\).
\(n=3\): \(f(1)+f(2)+f(3)=2+f(3)=2+6=8\).
\(n=4\): \(f(1)+f(2)+f(3)+f(4)=8+f(4)=8+12=20\).
Opgave 4: Sumtegnet#
Sumtegnet blev defineret rekursivt i Ligning (5.5) i lærebogen. Dette spørgsmål handler om sumtegnet.
Spørgsmål a#
Beregn \(\sum_{k=1}^4 k^2\). Hvad er \(\sum_{k=1}^1 k^2\)?
Svar
\(\sum_{k=1}^4 k^2=1^2+2^2+3^2+4^2=30.\)
\(\sum_{k=1}^1 k^2=1^2=1.\)
Spørgsmål b#
Vi skriver \(k!\) for \(k\) facultet i denne opgave og benytter også den sædvanlige definition \(0!=1\).
Beregn \(\sum_{k=0}^4 1/k!\).
Svar
\(\sum_{k=0}^4 k^2=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}=\frac{1}{1}+\frac{1}{1}+\frac{1}{2}+\frac{1}{6}+\frac{1}{24}=\frac{65}{24}.\)
Bemærkning: det kan vises at summen \(\sum_{k=0}^n 1/k!\) går mod tallet \(e\), hvis \(n\) går mod uendelig.
Opgave 5: Hermite polynomier.#
I denne opgave vil vi definere en følge af polynomier \(\mathrm{He}_0(Z), \mathrm{He}_1(Z), \dots \) med heltalskoefficienter som kaldes Hermitepolynomierne. Disse polynomier optræder i mange sammenhænge, blandt andet i signalbehandling, sandsynlighedsregning og kvantemekanik. Hermitepolynomierne kan defineres rekursivt som følger:
\(\mathrm{He}_0(Z)=1\), \(\mathrm{He}_1(Z)=Z\) og \(\mathrm{He}_n(Z)=Z\mathrm{He}_{n-1}(Z)-(n-1)\mathrm{He}_{n-2}(Z)\) hvis \(n \ge 2\).
Hvad er \(\mathrm{He}_n(Z)\) for \(n=0,1,\dots,4\)?
Svar
\(\mathrm{He}_0(Z)=1\), \(\mathrm{He}_1(Z)=Z\), \(\mathrm{He}_2(Z)=Z^2-1\), \(\mathrm{He}_3(Z)=Z^3-3Z\) og \(\mathrm{He}_4(Z)=Z^4-6Z^2+3\).
Opgave 6: En rekursiv defineret stamfunktion#
I Opgave 6 fra Uge 2 Lille Dag blev formlen \(\mathrm{arctan}'(x)=1/(1+x^2)\) nævnt. Det betyder at
Hvis \(n\) er et naturligt tal, kan man ligeledes spørge om der findes en lignende formel til den ubestemte integral
Det viser sig at der er en rekursiv løsning til dette spørgsmål.
Spørgsmål a#
Produktreglen siger at \((f(x)\cdot g(x))'=f(x)' \cdot g(x)+f(x) \cdot g(x)'\) (se eventuelt Appendix A.2 fra lærebogen for denne og andre regler angående differentiation). Gør rede for at
Denne formel kaldes for partiel integration.
Hint
Funktionen \((f(x)\cdot g(x))'\) har stamfunktion \(f(x) \cdot g(x)\). På den anden side kan man omskrive \((f(x)\cdot g(x))'\) ved hjælp af produktreglen.
Spørgsmål b#
Anvend partiel integration på \(f(x)=x\) og \(g(x)=1/(1+x^2)^n\) for at indse at
Spørgsmål c#
Brug nu formlen
for at konkludere at
Løs nu for \(\int \frac{1}{(1+x^2)^{n+1}}dx\) i den sidste formel og konkluder at hvis \(n \ge 1\), så gælder
Dette formel er præcist hvad vi skulle bruge! Formlen udtrykker stamfunktionen til \(1/(1+x^2)^{n+1}\) som en sum af funktionen \(\frac{x}{2n(1+x^2)^n}\) og stamfunktionen af \(1/(1+x^2)^{n}\). Derfor kan formlen bruges til at finde stamfunktionen til \(1/(1+x^2)^{n+1}\) på en rekursiv måde.
Spørgsmål d#
Brug den fundne rekursion til at bestemme stamfunktionen til \(1/(1+x^2)^2\).
Svar