Induktionsschritt (beweis) < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:51 So 30.10.2005 | | Autor: | AriR |
weiß einer von euch den Induktionsschritt (Beweis) für
n² [mm] \ge 2^{n} [/mm] - 1 für alle n [mm] \ge [/mm] 4
ich bekomme den beweis einfach nicht hin für n -> n+1
in meiner letzen zeile steht: n² [mm] \le 2*(2^{n}-1)-2n
[/mm]
wie kann ich jetzt beweisen, dass dies eine wahre aussage ist?
danke im voraus... gruß ari
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> weiß einer von euch den Induktionsschritt (Beweis) für
>
> n² [mm]\ge 2^{n}[/mm] - 1 für alle n [mm]\ge[/mm] 4
>
> ich bekomme den beweis einfach nicht hin für n -> n+1
Hallo,
schon für n=5 dürfte man Schwierigkeiten haben, das da oben zu zeigen.
Da die Aussage nicht stimmt, kannst Du sie nicht zeigen.
Stimmen tut allerdings folgendes:
n² [mm] < 2^{n}[/mm] - 1 für alle n [mm] > [/mm] 4
Induktionsanfang: hier wäre Gültigkeit für n=5 zu zeigen.
Nun der Schritt von n [mm] \to [/mm] n+1:
Unter der Voraussetzung, daß die Behauptung für alle n>4 gilt, ist zu zeigen: es ist (n+1)² [mm] < 2^{n+1}[/mm] - 1.
Jetzt beginnt das große Abschätzen
[mm] (n+1)^2=n^2+2n+1<2^n-1+2n+1=2^n+2n [/mm]
-----Achtung! Jetzt kommt der Witz!!!----
[mm] <2^n+n^2<...
[/mm]
Und nun kommst Du alleine weiter.
Oder war die Aufgabe eine andere???
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:04 So 30.10.2005 | | Autor: | AriR |
kurze frage noch bitte, bei dem schritt hier
[mm] n^2+2n+1<2^n-1+2n+1
[/mm]
wo kommt auf der rechten seite das +2n+1 her?? wir haben doch links nur die binomische formel angewendet oder nicht, dann müsste doch die rechte immer noch [mm] 2^n-1 [/mm] sein oder nicht?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:17 So 30.10.2005 | | Autor: | Loddar |
Hallo AriR,
zunächst einmal ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !!
[mm] $(n+1)^2 [/mm] \ = \ [mm] \red{n^2}+2n+1 [/mm] \ > \ [mm] \red{2^n-1} [/mm] + 2n+1$
Hier wurde zunächst die binomische Formel auf die Klammer (wie von Dir erkannt) und anschließend auf den Term [mm] $\red{n^2}$ [/mm] die Induktionsvoraussetzung [mm] $n^2 [/mm] \ > \ [mm] 2^n-1$ [/mm] angewandt.
Daher verbleibt dann natürlich auch der "Rest" mit $+2n+1_$ .
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:35 So 30.10.2005 | | Autor: | AriR |
ok das mit den +2n+1 hab ich verstanden, aber wie mache ich jetzt weiter +g+..
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:45 So 30.10.2005 | | Autor: | Loddar |
Hallo AriR!
Angela hat es Dir doch bis zu $... \ < \ [mm] 2^n [/mm] + [mm] n^2$ [/mm] bereits vorgerechnet.
Wende nun auf [mm] $n^2$ [/mm] nochmals die Induktionsvoraussetzung an.
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:13 So 30.10.2005 | | Autor: | AriR |
entweder hab ich einen black out oder bin zu doof für diese aufgabe +g+
[mm] 2^{n}+2n [/mm] < $ [mm] <2^n+n^2<... [/mm] $ ??
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:39 So 30.10.2005 | | Autor: | Loddar |
Hallo AriR!
In diesem Schritt wurde schlicht und ergreifend $2n_$ gegen [mm] $n^2$ [/mm] abgeschätzt. Und dass gilt $2n \ < \ [mm] n^2$ [/mm] , ist ja offensichtlich wahr für $n \ > \ 2$ .
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:49 So 30.10.2005 | | Autor: | AriR |
müsste man dies dann nicht auch wieder beweisen, rein streng genommen, da wir es ja in einem beweis verwenden?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:04 So 30.10.2005 | | Autor: | Loddar |
Hallo Ari!
Ganz streng genommen, müsste man diese Abschätzung wirklich ebenfalls nachweisen.
[mm] $n^2 [/mm] \ > \ 2n$ [mm] $\gdw$ $n^2 [/mm] - 2n \ = \ n*(n-2) \ > \ 0$
Daraus ist das schon fast "abzulesen", da $n \ [mm] \in [/mm] \ [mm] \IN$ [/mm] ...
Gruß
Loddar
|
|
|
|
