IMO-ulikhet

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

IMO-ulikhet

Innlegg mingjun » 17/04-2017 09:38

Følgen av reele tall $ a_0, a_1, a_2, \dots $ er definert ved
\[a_0 = -1 \text{ }, \sum_{k=0}^n \frac{a_{n-k}}{k+1} = 0\text{, for } n \ge 1. \]

Vis at ${} a_n > 0 $ for $ n \ge 1 $.

(Imo shortlist 2006, Poland)

Edit: formatering.
mingjun offline
Noether
Noether
Innlegg: 42
Registrert: 18/11-2016 21:13
Bosted: Trondheim

Re: IMO-ulikhet

Innlegg DennisChristensen » 20/04-2017 21:17

mingjun skrev:Følgen av reele tall $ a_0, a_1, a_2, \dots $ er definert ved
\[a_0 = -1 \text{ }, \sum_{k=0}^n \frac{a_{n-k}}{k+1} = 0\text{, for } n \ge 1. \]

Vis at ${} a_n > 0 $ for $ n \ge 1 $.

(Imo shortlist 2006, Poland)

Edit: formatering.


Basistilfelle: $n = 1$. Her har vi at $\frac{a_1}{1} + \frac{a_0}{2} = 0,$ så $a_1 = \frac{1}{2} > 0.\text{ }\text{ }\text{ } \checkmark$

Induksjon: Anta at ulikheten gjelder opp til $n-1,\text{ }n \geq 2$. Merk at $$\begin{align*} 0 & = \sum_{k=0}^n\frac{a_{n-k}}{k+1} \\
& = a_n + \sum_{k=1}^n\frac{a_{n-k}}{k+1} \\
& = a_n + \int_0^1\sum_{k=1}^n a_{n-k} x^k dx \\
& = a_n + \int_0^1x \sum_{k=1}^n a_{n-k} x^{k-1} dx \\
& = a_n + \left[x\sum_{k=1}^n\frac{a_{n-k}}{k} x^k\right]_0^1 - \int_0^1 \sum_{k=1}^n \frac{a_{n-k}}{k}x^k dx \text{ }\text{ (bruker delvis integrasjon)} \\
& = a_n + \left[\sum_{k=0}^{n-1}\frac{a_{(n-1)-k}}{k+1}\right] - \sum_{k=1}^n \frac{a_{n-k}}{k(k+1)} \\
& = a_n - \sum_{k=1}^n \frac{a_{n-k}}{k(k+1)}\text{ }\text{ (fra definisjonen av }a_{n-1}). \end{align*}$$

Dette gir oss to uttrykk for $a_n$, nemlig $$a_n = \begin{cases} -\sum_{k=1}^n \frac{a_{n-k}}{k+1} & \text{(fra definisjonen)} \\ \sum_{k=1}^n\frac{a_{n-k}}{k(k+1)} & \text{(fra utregningen ovenfor)}\end{cases}.$$

Dermed ser vi at $$\begin{align*} \left(1 + \frac{1}{n}\right)a_n & = a_n + \frac{1}{n}a_n \\
& = \sum_{k=1}^n\frac{a_{n-k}}{k(k+1)} - \frac{1}{n}\sum_{k=1}^n \frac{a_{n-k}}{k+1} \\
& = \frac{a_0}{n(n+1)} + \sum_{k=1}^{n-1}\frac{a_{n-k}}{k(k+1)} - \frac{a_0}{n(n+1)} - \frac{1}{n}\sum_{k=1}^{n-1}\frac{a_{n-k}}{k+1} \\
& = \sum_{k=1}^{n-1}\left[\frac{1}{k(k+1)} - \frac{1}{n(k+1)}\right]a_{n-k}, \end{align*}$$ som er positivt ettersom alle koeffisientene i summen er positive ($k < n$), og vi at antatt at $a_1, \dots, a_{n-1} > 0$ som induksjonshypotese. Dermed er $(1+\frac{1}{n})a_n > 0$, så $a_n > 0$ og ulikheten bevist ved induksjon.

Edit: Reddet mitt originale, feilaktige argument etter kritikk fra plutarco.
Sist endret av DennisChristensen den 23/04-2017 13:04, endret 2 ganger.
DennisChristensen offline
Ramanujan
Ramanujan
Innlegg: 287
Registrert: 09/02-2015 23:28
Bosted: Oslo

Re: IMO-ulikhet

Innlegg plutarco » 21/04-2017 21:23

Funker dette når $a_0$ er negativ da? Forstår ikke hvordan du kan trekke konklusjonen på slutten der når du har et ledd som er negativt.
plutarco offline
Tyrann
Tyrann
Innlegg: 3747
Registrert: 12/12-2008 12:44

Re: IMO-ulikhet

Innlegg plutarco » 23/04-2017 11:23

DennisChristensen skrev:$$\begin{align*}
& = a_n + \left[x\sum_{k=1}^n\frac{a_{n-k}}{k} x^k\right]_0^1 - \int_0^1 \sum_{k=1}^n \frac{a_{n-k}}{k}x^k dx \text{ }\text{ (bruker delvis integrasjon)} \\
& = a_n + \left[\sum_{k=0}^{n-1}\frac{a_{n-k}}{k+1}\right] - \sum_{k=1}^n \frac{a_{n-k}}{k(k+1)} \\ \end{align*}$$


Ikke for å være slem, men skal det ikke stå $a_{n-k-1}$ i det midte leddet etter indeksbyttet?
plutarco offline
Tyrann
Tyrann
Innlegg: 3747
Registrert: 12/12-2008 12:44

Re: IMO-ulikhet

Innlegg stensrud » 23/04-2017 12:27

Den gitte likheten kan skrives som
\[ \sum_{k=0}^n\frac{a_k}{n-k+1}=0, \]
som betyr at
\[ 0=\sum_{k=0}^{n}\frac{n+1}{n-k+1}a_k=\sum_{k=0}^{n+1}\frac{n+2}{n-k+2}a_k. \]
(Vi brukte den gitte likheten for $n$ og $n+1$, og ganget begge sider med henholdsvis $n+1$ og $n+2$). Vi trekker fra og får
\[ 0=\sum_{k=0}^{n+1}\frac{n+2}{n-k+2}a_k -\sum_{k=0}^{n}\frac{n+1}{n-k+1}a_k = (n+2)a_{n+1}+\sum_{k=0}^n\left( \frac{n+2}{n-k+2} - \frac{n+1}{n-k+1} \right)a_k.\]
Setter vi $c_k = \frac{n+1}{n-k+1}\frac{n+2}{n-k+2}$ så er det over ekvivalent med
\[ (n+2)a_{n+1}=\sum_{k=0}^nc_ka_k. \]
Siden hver $c_k>0$ følger det at alle $a_i>0$ ved induksjon.
stensrud offline
Jacobi
Jacobi
Innlegg: 340
Registrert: 08/11-2014 21:13
Bosted: Ski

Re: IMO-ulikhet

Innlegg DennisChristensen » 23/04-2017 13:07

plutarco skrev:
DennisChristensen skrev:$$\begin{align*}
& = a_n + \left[x\sum_{k=1}^n\frac{a_{n-k}}{k} x^k\right]_0^1 - \int_0^1 \sum_{k=1}^n \frac{a_{n-k}}{k}x^k dx \text{ }\text{ (bruker delvis integrasjon)} \\
& = a_n + \left[\sum_{k=0}^{n-1}\frac{a_{n-k}}{k+1}\right] - \sum_{k=1}^n \frac{a_{n-k}}{k(k+1)} \\ \end{align*}$$


Ikke for å være slem, men skal det ikke stå $a_{n-k-1}$ i det midte leddet etter indeksbyttet?


Jo, det skal det så klart. Hele poenget er jo at leddet kan kanselleres fra definisjonen til $a_{n-1}$. Da skal alt være i orden nå.

Veldig fin løsning fra Stensrud! Ser ut som samme tankegang som de har i løsningsforslaget. Litt artig å se forskjellige måter å angripe oppgaven på.
DennisChristensen offline
Ramanujan
Ramanujan
Innlegg: 287
Registrert: 09/02-2015 23:28
Bosted: Oslo

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 2 gjester