Side 1 av 1

IMO-ulikhet

Lagt inn: 17/04-2017 10:38
av mingjun
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.

Re: IMO-ulikhet

Lagt inn: 20/04-2017 22:17
av DennisChristensen
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.

Re: IMO-ulikhet

Lagt inn: 21/04-2017 22:23
av Gustav
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.

Re: IMO-ulikhet

Lagt inn: 23/04-2017 12:23
av Gustav
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?

Re: IMO-ulikhet

Lagt inn: 23/04-2017 13:27
av stensrud
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.

Re: IMO-ulikhet

Lagt inn: 23/04-2017 14:07
av DennisChristensen
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å.