Aufgabe #52 (IrMO) < MO andere Länder < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 12:17 Sa 09.07.2005 | | Autor: | Hanno |
Hallo an alle!
Es sei [mm] $f:\IN\to\IN$ [/mm] mit $f(1)=2$ und [mm] $f(n+1)=(f(n))^2-f(n)+1, [/mm] n=1,2,...$. Beweise, dass für alle [mm] $n\geq [/mm] 2$ die Ungleichungskette
[mm] $1-\frac{1}{2^{2^{n-1}}}<\frac{1}{f(1)}+\frac{1}{f(2)}+\cdots+\frac{1}{f(n)}<1-\frac{1}{2^{2^{n}}}$
[/mm]
gilt.
Liebe Grüße,
Hanno
|
|
| |
|
Hallo Hanno.
> Es sei [mm]f:\IN\to\IN[/mm] mit [mm]f(1)=2[/mm] und [mm]f(n+1)=(f(n))^2-f(n)+1, n=1,2,...[/mm].
> Beweise, dass für alle [mm]n\geq 2[/mm] die Ungleichungskette
> [mm]1-\frac{1}{2^{2^{n-1}}}<\frac{1}{f(1)}+\frac{1}{f(2)}+\cdots+\frac{1}{f(n)}<1-\frac{1}{2^{2^{n}}}[/mm]
> gilt.
Es lässt sich induktiv zeigen, dass
[mm]\frac{1}{f(1)}+\frac{1}{f(2)}+\cdots+\frac{1}{f(n)} = \frac{f(n+1)-2}{f(n+1)-1}[/mm]
Induktionsanfang (f(1)=2, f(2)=3, f(3)=7):
[mm]\frac{1}{f(1)}+\frac{1}{f(2)}=\frac{5}{6}=\frac{f(3)-2}{f(3)-1}[/mm]
Ind.-Schritt:
[mm]\frac{f(n+1)-2}{f(n+1)-1}+\frac{1}{f(n+1)}=\frac{f(n+1)^2-2f(n+1)+f(n+1)-1}{f(n+1)^2-f(n+1)}=\frac{f(n+2)-2}{f(n+2)-1}[/mm]
Desweiteren ist
[mm]\frac{f(n+1)-2}{f(n+1)-1}=1-\frac{1}{f(n+1)-1}[/mm]
Es bleibt zu zeigen, dass
[mm]1-\frac{1}{2^{2^{n-1}}}<1-\frac{1}{f(n+1)-1}<1-\frac{1}{2^{2^{n}}}[/mm]
[mm]\Leftrightarrow 2^{2^{n-1}}
[mm]\Leftrightarrow 2^{2^{n-1}}+1
Die linke Seite kann man wie folgt induktiv zeigen:
Ind.-Anfang: [mm]f(3)=7>5=2^{2^{2-1}}+1[/mm]
Ind.-Schritt: [mm]f(n+2)=f(n+1)(f(n+1)-1)+1>(2^{2^{n-1}}+1)2^{2^{n-1}}+1=2^{2^n}+2^{2^{n-1}}+1>2^{2^n}+1[/mm]
Die rechte Seite der Ungleichung lautet:
[mm]f(n+1)<2^{2^{n}}+1[/mm]
Beweist man, dass [mm]f(n+1)<2^{2^{n}-1}[/mm], so ist diese bewiesen.
Dies wird wiederum induktiv gezeigt:
Ind.-Anfang: [mm]f(3)=7<8=2^{2^2-1}[/mm]
Ind.-Schritt:
[mm]f(n+2)=f(n+1)^2-f(n+1)+1<2^{2^{n+1}-2}-2^{2^{n}-1}+1<2^{2^{n+1}-1}[/mm]
Ich hoffe das stimmt.
MfG
Jan
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:00 Mo 18.07.2005 | | Autor: | Hanno |
Hallo Jan!
Deine Abschätzungen am Ende scheinen sehr grob, ich konnte auf die Schnelle aber keinen Fehler entdecken! Meinen absoluten ![[respekt]](/images/smileys/respekt.gif "[respekt]") , die Idee mit der Induktion zu Beginn ist wirklich genial!
Ich stelle hier gliech noch eine weitere Aufgabe aus einer ehemaligen Bundesrunde der DeMO herein, die sich, wie man schnell einsieht, auf genau das gleiche Problem reduziert.
Liebe Grüße,
Hanno
|
|
|
|
