Induktionsbeweise Euklid < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:55 Do 08.08.2013 | | Autor: | svcds |
| Aufgabe | Widerlegen oder beweisen Sie:
a) [mm] (\parallel \parallel [/mm] x [mm] \parallel [/mm] - x [mm] \parallel)^{n} [/mm] = [mm] (\parallel [/mm] x [mm] \parallel)^{2n} [/mm] für n [mm] \ge [/mm] 1
b) [mm] \summe_{i=0}^{n} \bruch{i}{2} [/mm] < [mm] 2^{n-1} [/mm] für n [mm] \ge [/mm] 0 |
Hi,
also ich brüte bei diesen beiden Beweisen.
a) habe ich mit Induktion probiert:
dann habe ich die linke Seite: [mm] (\parallel \parallel [/mm] x [mm] \parallel [/mm] * x [mm] \parallel)^{1} [/mm] = [mm] \parallel \wurzel{(x_1)^{2}} [/mm] * [mm] x_{1} \parallel [/mm] = [mm] \wurzel{(x_{1})*(x_{1})} [/mm] = [mm] x_{1}
[/mm]
Rechte Seite: [mm] (\parallel [/mm] x [mm] \parallel)^{2} [/mm] = [mm] x_{1}^2 [/mm] -daraus folgt, Gleichung gilt nicht.
Oder hab ich einen Fehler gemacht?
bei der b) steht bei dem Induktionsschrittt (Induktionsanfang gilt hier da 0<0,5):
[mm] \summe_{i=0}^{n+1} \bruch{i}{2} [/mm] < [mm] 2^{n+1-1}
[/mm]
=> [mm] \summe_{i=0}^{n} \bruch{i}{2} [/mm] + [mm] \bruch{n+1}{2} [/mm] < [mm] 2^{n}
[/mm]
=> [mm] 2^{n-1} [/mm] + [mm] \bruch{n+1}{2} [/mm] < [mm] 2^{n}
[/mm]
Wenn ich da jetzt aber n=1 einsetze, steht dort 2<2 und das ist ja falsch. In meiner Musterlösung steht da aber auf einmal NICHT "<" sondern [mm] "\le".
[/mm]
Kann mir da jemand helfen?
LG
Knut
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:33 Do 08.08.2013 | | Autor: | abakus |
> Widerlegen oder beweisen Sie:
>
> a) [mm](\parallel \parallel[/mm] x [mm]\parallel[/mm] - x [mm]\parallel)^{n}[/mm] =
> [mm](\parallel[/mm] x [mm]\parallel)^{2n}[/mm] für n [mm]\ge[/mm] 1
> b) [mm]\summe_{i=0}^{n} \bruch{i}{2}[/mm] < [mm]2^{n-1}[/mm] für n [mm]\ge[/mm] 0
> Hi,
>
> also ich brüte bei diesen beiden Beweisen.
>
> a) habe ich mit Induktion probiert:
>
> dann habe ich die linke Seite: [mm](\parallel \parallel[/mm] x
> [mm]\parallel[/mm] * x [mm]\parallel)^{1}[/mm] = [mm]\parallel \wurzel{(x_1)^{2}}[/mm]
> * [mm]x_{1} \parallel[/mm] = [mm]\wurzel{(x_{1})*(x_{1})}[/mm] = [mm]x_{1}[/mm]
>
> Rechte Seite: [mm](\parallel[/mm] x [mm]\parallel)^{2}[/mm] = [mm]x_{1}^2[/mm] -daraus
> folgt, Gleichung gilt nicht.
>
> Oder hab ich einen Fehler gemacht?
Hallo,
zu a):
Heißt es nun mal oder minus???
>
> bei der b) steht bei dem Induktionsschrittt
> (Induktionsanfang gilt hier da 0<0,5):
>
> [mm]\summe_{i=0}^{n+1} \bruch{i}{2}[/mm] < [mm]2^{n+1-1}[/mm]
> => [mm]\summe_{i=0}^{n} \bruch{i}{2}[/mm] + [mm]\bruch{n+1}{2}[/mm] < [mm]2^{n}[/mm]
> => [mm]2^{n-1}[/mm] + [mm]\bruch{n+1}{2}[/mm] < [mm]2^{n}[/mm]
[mm]\summe_{i=0}^{n} \bruch{i}{2}[/mm] ist laut Induktionsvoraussetzung nicht gleich [mm]2^{n-1}[/mm], sondern kleiner als [mm]2^{n-1}[/mm] .
Wenn du einen kleineren durch einen größeren Summanden ersetzt musst du dich nicht wundern, wenn der linke Term größer als vorher wird.
Gruß Abakus
> Wenn ich da jetzt aber n=1 einsetze, steht dort 2<2 und das
> ist ja falsch. In meiner Musterlösung steht da aber auf
> einmal NICHT "<" sondern [mm]"\le".[/mm]
>
> Kann mir da jemand helfen?
>
> LG
> Knut
>
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:56 Do 08.08.2013 | | Autor: | svcds |
Zu a)da muss mal stehen, sorry für das Minus.
Heisst bei b) dass da dann kleiner gleich stehen Mann, dass das kein Fehler ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:12 Fr 09.08.2013 | | Autor: | Marcel |
Hallo,
> Heisst bei b) dass da dann kleiner gleich stehen Mann, dass
> das kein Fehler ist?
ich weiß auch nicht, was Du da machst. Das ist so ein typischer Fehler, der
mir immer wieder bei Induktionsaufgaben auffällt, dass die Leute da
schlampig arbeiten.
Wenn Du beweisen willst, dass eine Aussage [mm] $B\,$ [/mm] wahr ist, so kannst Du das
nicht tun, indem Du zeigst, dass $B [mm] \Rightarrow [/mm] A$ gilt und [mm] $A\,$ [/mm] wahr ist.
Du musst vielmehr zeigen, dass die Folgerung $A [mm] \Rightarrow [/mm] B$ wahr ist und dass
[mm] $A\,$ [/mm] wahr ist. Siehe auch
hier (klick!),
da habe ich das mal ausführlichst beschrieben.
Kurzgesagt, das, was Du hier geschrieben hattest
> $ [mm] \summe_{i=0}^{n+1} \bruch{i}{2} [/mm] $ < $ [mm] 2^{n+1-1} [/mm] $ => $ [mm] \summe_{i=0}^{n} \bruch{i}{2} [/mm] $ + $ [mm] \bruch{n+1}{2} [/mm] $ < $ [mm] 2^{n} [/mm] $
> => $ [mm] 2^{n-1} [/mm] $ + $ [mm] \bruch{n+1}{2} [/mm] $ < $ [mm] 2^{n} [/mm] $
bringt Dich so nicht weiter - es ist von der "Beweislogik" her einfach auch
"falsch herum".
Machen wir's mal richtig:
Zu beweisen ist, dass [mm] $\sum_{k=0}^n [/mm] k/2 [mm] \;\;<\;\; 2^{n-1}$ [/mm] für jedes $n [mm] \ge 0\,.$ [/mm] (Was man übrigens auch schnell
zu [mm] $\sum_{k=0}^n [/mm] k [mm] \;\;<\;\; 2^n$ [/mm] umformen könnte... und egal, wie man die Aufgabe nun
betrachtet: Man könnte auch mal den "kleinen Gauß" ins Spiel bringen...
Aber machen wir's mal ohne den!)
Den I.A. hast Du ja hinbekommen.
Im Induktionsschritt sei nun $n [mm] \ge [/mm] 0$ so, dass [mm] $\sum_{k=0}^n [/mm] k/2 [mm] \;\;<\;\; 2^{n-1}$ [/mm] wahr ist.
Behauptung: Daraus folgt, dass dann auch [mm] $\sum_{k=0}^{n+1} [/mm] k/2 [mm] \;\;<\;\; 2^{n}$ [/mm] wahr ist.
[mm] \textbf{Beweis:} [/mm] Es gilt
[mm] $\sum_{k=0}^{n+1}k/2 \;\;<\;\; 2^{n}$
[/mm]
[mm] $\red{\iff} (\sum_{k=0}^n [/mm] k/2)+(n+1)/2 [mm] \;\;<\;\; 2^n$
[/mm]
(Wenn Du jetzt sagst, dass Du das auch hattest, so ist das leider eben nicht
ganz richtig: Wichtig ist hier nämlich, wie wir gleich sehen werden, eben
die Folgerungsrichtung [mm] $\Longleftarrow$ [/mm] - auf die Richtung [mm] $\Longrightarrow$ [/mm] kann man
hier beim Beweis verzichten!)
Wir brauchen nun also nur zu zeigen, dass aus der Wahrheit der Ungleichung
[mm] $\sum_{k=0}^n [/mm] k/2 [mm] \;\;< \;\;2^{n-1}$
[/mm]
(diese ist ja nach I.V. als wahr vorausgesetzt) folgt, dass
[mm] $(\sum_{k=0}^n [/mm] k/2)+(n+1)/2 [mm] \;\;<\;\; 2^n$
[/mm]
auch wahr ist (denn mit [mm] $\Longleftarrow$ [/mm] bei [mm] $\red{\iff}$ [/mm] folgt dann die im Induktionsschritt
behauptete Aussage).
(Das, was wir bisher gemacht haben, ist quasi eine "kleine Beweisstrategie".
Der "richtige Beweis" folgt nun!)
Also:
Nach I.V. ist die Ungleichung
[mm] $\sum_{k=0}^n [/mm] k/2 [mm] \;\;<\;\;2^{n-1}$
[/mm]
für ein $n [mm] \ge [/mm] 0$ wahr. Wegen
[mm] $\sum_{k=0}^n [/mm] k/2 [mm] \;\;<\;\;2^{n-1}$
[/mm]
[mm] $\Longrightarrow (\sum_{k=0}^n [/mm] k/2) [mm] +(n+1)/2\;\;<\;\;2^{n-1}+(n+1)/2$
[/mm]
folgt also, dass auch die Ungleichung
[mm] $(\sum_{k=0}^n [/mm] k/2) [mm] +(n+1)/2\;\;<\;\;2^{n-1}+(n+1)/2\$
[/mm]
für dieses $n [mm] \ge [/mm] 0$ wahr ist.
Soweit klar, oder?
Was Du nun einfach noch tun kannst: Beweise, dass auch die Ungleichung
[mm] $(\star)\;\;\;\;\;\;2^{n-1}+(n+1)/2 \;\; \le \;\; 2^n$
[/mm]
für (dieses) $n [mm] \ge [/mm] 0$ eine wahre Aussage ist (in der Tat reicht es hier, dass in
[mm] $(\star)$ [/mm] ein [mm] $\le$ [/mm] steht: Mach' Dir klar, dass aus $a < [mm] b\,$ [/mm] und $b [mm] \le [/mm] c$ schon $a < [mm] c\,$ [/mm] folgt!).
Das beendet dann den Beweis.
Und wenn Du magst:
Schreib's Dir nochmal selbst - für Dich - auf. Mir ist's wichtig, dass Du erkennst,
dass man bei solchen Beweisen auch die "Beweisrichtungen" beachten soll
und damit nicht schludern sollte. So kann man z.B. leicht einsehen, dass
für jedes reelle $x > [mm] 2\,$ [/mm] gilt:
[mm] $x^2 [/mm] > 4.$
Wenn Du allerdings sagst:
[mm] $x^2 [/mm] > 4 [mm] \iff [/mm] (x+2)*(x-2) > 0 [mm] \red{\;\Rightarrow\;} [/mm] (x > 2 [mm] \text{ oder }x [/mm] < -2),$
so ist das auch richtig, beweist aber nicht $x > 2 [mm] \Rightarrow x^2 [/mm] > 4.$ Würdest Du
aber dort [mm] $\red{\Rightarrow}$ [/mm] durch [mm] $\iff$ [/mm] oder wenigstens nur [mm] $\Leftarrow$ [/mm] ersetzen,
dann wäre das ein gültiger Beweis - aber man sollte sich auch immer
überlegen, ob denn, wenn man einen Folgerungspfeil durch [mm] $\iff$ [/mm] ersetzen will,
auch in der Tat die Folgerung in der anderen Richtung überhaupt gültig ist.
P.S. Zu oben:
Wegen
[mm] $2^{n-1}+(n-1)/2 [/mm] < [mm] 2^n$
[/mm]
[mm] $\iff [/mm] n-1 < [mm] 2^{n+1}-2^n$
[/mm]
[mm] $\iff [/mm] n-1 < [mm] 2^n(2-1)$
[/mm]
[mm] $\iff [/mm] n < [mm] 2^n+1$
[/mm]
ist es, um den Induktionsbeweis zu beenden, hinreichend, $n < [mm] 2^n+1$ [/mm] (für (alle)
$n [mm] \ge [/mm] 0$) zu beweisen!
(Hinweis: Um das einzusehen, reicht es, alle [mm] $\iff$ [/mm] durch [mm] $\Longleftarrow$ [/mm] zu ersetzen und
die Umformungen von unten nach oben zu lesen!)
An dieser (Rest-)Aufgabe kannst Du Dich ja nun nochmal versuchen!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:13 Fr 09.08.2013 | | Autor: | fred97 |
Zu a): Statt "-" steht da also $"*"$.
Es geht also um die Gültigkeit von
$|| [mm] \quad [/mm] ||x||*x [mm] \quad ||^n=||x||^{2n}$
[/mm]
Leider hast Du nicht verraten woher x stammt. Ich vermute x [mm] \in [/mm] X, wobei X ein normierter Raum ist und $||*||$ eine Norm auf X ist (vielleicht [mm] X=\IR^n [/mm] und $||*||$ die Euklidnorm auf X ?).
Wie auch immer. Sei also X ein normierter Raum ist und $||*||$ eine Norm auf X.
Induktion braucht man nicht: sei x [mm] \in [/mm] X und $t:=||x||$. Dann:
$|| [mm] \quad [/mm] ||x||*x [mm] \quad ||^n=||t*x||^n=(|t|*||x||)^n=(||x||*||x||)^n=(||x||^2)^n=||x||^{2n}$
[/mm]
FRED
|
|
|
|
