Bevis for AM-GM

[mrcreosote]

En av de mest kjente ulikhetene vi har, er ulikheta som sier at det aritmetiske gjennomsnittet av n positive reelle tall er større eller lik det geometriske gjennomsnittet av de samme talla:

[tex]x_1\dots x_n\le\left(\frac{x_1+\dots+x_n}n\right)^n[/tex]

for reelle og positive x_j. Denne oppgava går ut på å vise dette med et stilig induksjonsbevis.

a) Vis at ulikheta er riktig for n=2.
b) Vis at hvis ulikheta er riktig for n=k, er den også riktig for n=k-1 (sic).
c) Vis at hvis ulikheta er riktig for n=2 og n=k, er den også riktig for n=2k.
d) Konkluder.

[Karl_Erik]

a) [tex] sqrt{ab} \leq \frac {a+b} 2 \Leftrightarrow 0 \leq (sqrt a + sqrt b)^2[/tex] som opplagt er sant fordi kvadratet av to reelle tall er ikkenegativt.



b) Anta at ulikheten holder for [tex]k[/tex] variabler, som vil si at
[tex]\prod a_i \leq \left ( \frac {\sum a_i } k \right )^k[/tex] for alle [tex]a_i[/tex] der produkt- og summasjonsindeksene her går fra [tex]i=1[/tex] til [tex]i=k[/tex], men er utelatt for leselighet. Sett [tex]a_k=\frac 1 {k-1} \sum _{i=1} ^{k-1} a_i[/tex], dvs at vi setter en variabel lik det aritmetiske snittet av alle de andre. Da blir ulikheten [tex]\left ( \frac 1 {k-1} \sum a_i \right ) \prod a_i \leq \left ( \frac {\sum a_i } {k-1} \right )^k[/tex] der summasjonsindeksene går fra 1 til [tex]k-1[/tex], som ved divisjon blir til
[tex]\prod a_i \leq \left ( \frac {\sum a_i } {k-1} \right )^{k-1}[/tex], som er AM-GM-ulikheten i [tex]k-1[/tex] variable. Altså har vi at om ulikheten holder for [tex]k[/tex] variable holder den også for [tex]k-1[/tex] variable.



c) Anta at ulikheten holder for [tex]k[/tex] og 2 variabler. Da har vi
[tex]\prod a_i \leq \left ( \frac {\sum a_i } k \right )^k[/tex] og [tex]\prod b_i \leq \left ( \frac {\sum b_i } k \right )^k[/tex] Multipliserer vi disse ulikhetene får vi at
[tex]\prod a_i \prod b_i \leq \left ( \frac {\left ( \sum a_i \right ) \left ( \sum b_i \right ) } {k^2} \right )^k[/tex]
Bruker vi antagelsen om at ulikheten holder i to variabler har vi at [tex]\left ( \sum a_i \right ) \left ( \sum b_i \right ) \leq \left ( \frac {\sum a_i + \sum b_i} 2 \right )^2[/tex], så
[tex]\prod a_i \prod b_i \leq \left ( \frac {\left ( \sum a_i \right ) \left ( \sum b_i \right ) } {k^2} \right )^k \leq \left ( \frac {\left ( \sum a_i + \sum b_i \right ) ^2} {(2k)^2} \right )^k =\left ( \frac { \sum a_i + \sum b_i} {2k} \right )^{2k}[/tex]
som er det samme som at det geometriske snittet av [tex]2k[/tex] reelle, positive tall er mindre enn eller lik det aritmetiske snittet av de samme [tex]2k[/tex] tallene. Altså har vi at om AM-GM holder for [tex]k[/tex] variable og for 2 variabler holder den for [tex]2k[/tex] variable, som var det vi ville vise.

d) Av a) har vi at ulikheten holder for 2 variabler. Siden ulikheten holder for 2 variabler holder den av c) også for 4 variabler, og igjen av c) også for 8 og så videre av c) generelt for [tex]2^m[/tex] variabler. Av b) har vi at om ulikheten holder for [tex]N[/tex] variabler holder den også for [tex]N-1[/tex] variabler, og derfor også for [tex]N-2[/tex] variabler og på samme måte holder den for alle antall variabler mindre enn [tex]N[/tex]. Av b) og c) har vi derfor at den holder for alle antall variabler mindre enn eller lik [tex]2^m[/tex] for en vilkårlig stor [tex]m[/tex], og derfor holder den for alle antall variabler, og ulikheten er bevist.

[mrcreosote]

Ser bra ut! Det er lov å poste andre bevis for AM-GM også.

[Karl_Erik]

Zivert viste meg et bevis ved Jensens ulikhet. [tex]f(x)=ln(x)[/tex] er en konkav funksjon, så [tex]\frac 1 n \sum _{i=1} ^n ln(x_i) \leq ln \left ( \frac 1 n \sum _{i=1} ^n x_i \right )[/tex], som er ekvivalent med [tex]\left ( \prod_{i=1} ^n x_i \right ) ^{\frac 1 n} \leq \frac 1 n \sum _{i=1} ^n x_i[/tex] og vi er ferdige. Beviset for Jensens ulikhet overlates til leseren.

[Bogfjellmo]

Dette er egentlig et godt eksempel på et teorem hvor det er enklere å bevise en sterkere form for teoremet.

Vektet AM-GM, dvs.

[tex]a_1^{p_1} a_2^{p_2} \cdots a_n^{p_n} \leq p_1 a_1+ p_2 a_2 +\cdots +p_n a_n[/tex]

Hvor [tex]\sum_{i=1}^n p_i=1.[/tex]

Kan bevises med et mer standard induksjonsbevis. Basis-tilfellet for [tex]n = 2[/tex] er dessverre noe vanskeligere.