Hej allesammans,
Ursäkta att jag är sen med denna tråd. Hursomhelst vill jag säga tack till er som deltog under träffen. Det märks att ni verkligen har en brinnande passion för matte, vilket är extremt kul att se! Nedan följer förslag på hur ni kan gå tillväga för att lösa uppgifterna
Uppgift 1:
- - - - - - - - -
Detta är ett klassiskt problem inom dynamisk problem där målet är att kunna hitta ett rekursivt samband och på så sätt finna lösningar till delproblem som sedan resulterar i att man kan lösa huvudproblemet. Det formella beviset för denna uppgift görs med hjälp av matematisk induktion, men jag tror ni vinner mer på att få en bra intuition för hur man kommer fram till formeln. Med det sagt kan man visa följande:
Låt \(f(n)\) vara antalet möjligheter för \(n\) trappsteg. Då gäller att
\(f(1) = 1\)
\(f(2) = 2\)
\(f(n) = f(n-1) + f(n-2) , n \geq 3\)
Basfallen \(n=1\) och \(n=2\) tror jag inte behöver mycket motivering. Det är bara att rita upp så ser ni varför det stämmer. Det rekursiva sambandet är lite knepigare. Men om vi tänker oss att vi redan befinner oss på toppen, hur kunde vi hamnat där? Jo det enda sättet är om vårt sista hopp gjordes från antingen trappsteg \(n-1\) eller trappsteg \(n-2\). Användning av induktion hade tillåtit oss att anta att \(f(n-1)\) och \(f(n-2)\) är korrekt uträknade och därmed kan vi vara säkra på att \(f(n) = f(n-1) + f(n-2)\).
Uppgift 2:
- - - - - - - -
a) Detta är en konsekvens av triangelolikheten. Sätt \(x = a-b\) och \(y =b-c\). Då gäller att \(x + y = a-c\). Triangelolikheten tillämpad på \(x\) och \(y\) (d.v.s. \(|x+y| \leq |x| + |y|\)) ger oss nu det önskade resultatet.
b) Inför vektorerna \(c = (c_{1} , ..., c_{n})\) och \(d =(d_{1} , ..., d_{n})\) där vi definierar \(c_{i}\) och \(d_{i}\) enligt
\(c_{i} = log(a_{i})\)
och
\(d_{i} = b_{i}^2\)
Resultatet följer nu omedelbart av Cauchy Schwartz Olikhet tillämpad på vektorerna \(c\) och \(d\).
Uppgift 3:
- - - - - - - -
Låt oss tänka oss att vi vill fördela elementen över två namngivna mängder \(M_{1}\) och \(M_{2}\). Vi fokuserar på att göra valen för \(M_{1}\) då resterande element automatiskt hamnar i \(M_{2}\). Vi kan välja som minst \(1\) element för \(M_{1}\) och som mest \(n-1\) (annars får vi ju ingen partition). Så att antalet fördelningar vi kan göra över \(M_{1}\) och \(M_{2}\) måste vara precis
\(\sum_{k=1}^{n-1} \binom{n}{k}\).
Men för en partition råder det ingen skillnad mellan mängderna (de har inga titlar) och notera att för varje uppdelning så finns det en ekvivalent uppdelning där elementen från \(M_{1}\) nu istället ligger i \(M_{2}\) och tvärtom. Därför måste vi dela summan med \(2\).
Att
\( \frac{1}{2} \sum_{k=1}^{n-1} \binom{n}{k} = 2^{n-1} -1\)
kan argumenteras på två sätt. Antingen kombinatoriskt eller genom att använda binomialsatsen. Det kombinatoriska argumentet bygger på att summan faktiskt räknar antalet delmängder av storlek \(1\) till och med storlek \(n-1\). För en mängd av storlek \(n \geq 0\) så finns exakt \(2^{n}\) delmängder (varför?). Men detta inkluderar den tomma och den fulla delmängden. Så att antalet delmängder av storlek \(1\) till och med storlek \(n-1\) ges av \(2^{n} - 2\). Division med \(2\) ger nu det önskade resultatet. Den andra argumentet bygger på att man binomialutvecklat summan (Notera att summan är lika med summan som går från \(0\) till \(n\), minus den första och den sista termen).
Jag kommer tyvärr inte att delta under nästa seminarium vilket är tråkigt :( men tveka inte att höra av er till mig ifall ni har något på hjärtat (mail: emil.eriksson@math.su.se). Allt gott och ta hand om er!
Med vänliga hälsningar,
Emil