Induktionsbeweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:36 Di 21.10.2008 | | Autor: | Hachiko8 |
| Aufgabe 1 | 1. (a) Beweise, dass für alle n [mm] \in \IN [/mm] gilt:
[mm] \summe_{k=1}^{n} [/mm] = 1/6*n (n+1)(2n+1) |
| Aufgabe 2 | (b) Ermittle für welche [mm] n\in \IN [/mm] die Ungleichung [mm] 2^n [/mm] < n! gilt.
Hinweis zu (b): Finde zunächst das kleinste [mm] n\in \IN, [/mm] für das [mm] 2^n [/mm] < n! gilt, und benutze dann vollständige Induktion. |
Könnt ihr es bitte auf Fehler kontrollieren und diese berichtigen wenn möglich? das wär echt lieb, danke
Induktionsanfang: n=1 linke seite: 1²=1 rechte seite: 6/6=1
->wahre aussage
Induktionsvoraussetzung: [mm] \summe_{k=1}^{n} [/mm] = 1/6*n (n+1)(2n+1) gilt für alle [mm] n\in \IN
[/mm]
Induktionsschritt: n->n+1
[mm] \summe_{k=1}^{n+1} [/mm] = [mm] \summe_{k=1}^{n} [/mm] k²+(n+1)²= ((n(n+1)(2n+1))/6)+(n+1)² = (n(n+1)(2n+1)+6(n+1)²)/6= ((n+1)(n(2n+1)+6(n+1))/6 = (n+1)(2n²+n+6n+6)/6= (n+1)(2n²+7n+6)/6 = (n+1)(n+2)(2n+3)/6 //
(b) Induktionsanfang: n=4 [mm] 2^4<4! [/mm] 16<24
dann kommt etwas verwirrendes, dass ich auch nicht so ganz verstehe, weil mir das jemand vorgesagt hat...
Induktionsschritt:
[mm] (n+1)!=(n+1)*n!>(n+1)2^n >2*2^n=2^{n+1} [/mm] //
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:15 Di 21.10.2008 | | Autor: | Marcel |
Hallo,
> 1. (a) Beweise, dass für alle n [mm]\in \IN[/mm] gilt:
> [mm]\summe_{k=1}^{n} \red{k^2}[/mm] = 1/6*n (n+1)(2n+1)
> (b) Ermittle für welche [mm]n\in \IN[/mm] die Ungleichung [mm]2^n[/mm] < n!
> gilt.
>
> Hinweis zu (b): Finde zunächst das kleinste [mm]n\in \IN,[/mm] für
> das [mm]2^n[/mm] < n! gilt, und benutze dann vollständige
> Induktion.
> Könnt ihr es bitte auf Fehler kontrollieren und diese
> berichtigen wenn möglich? das wär echt lieb, danke
>
> Induktionsanfang: n=1 linke seite: 1²=1 rechte seite: 6/6=1
> ->wahre aussage
>
> Induktionsvoraussetzung: [mm]\summe_{k=1}^{n}[/mm] = 1/6*n
> (n+1)(2n+1) gilt für alle [mm]n\in \IN[/mm]
>
> Induktionsschritt: n->n+1
> [mm]\summe_{k=1}^{n+1}\red{k^2}[/mm] = [mm]\summe_{k=1}^{n}[/mm] k²+(n+1)²=
> ((n(n+1)(2n+1))/6)+(n+1)² = (n(n+1)(2n+1)+6(n+1)²)/6=
> ((n+1)(n(2n+1)+6(n+1))/6 = (n+1)(2n²+n+6n+6)/6=
> (n+1)(2n²+7n+6)/6 = (n+1)(n+2)(2n+3)/6
benutze doch bitte den Formeleditor, dann ist das ganze auch übersichtlicher. Brüche $a/b$ schreibst Du mit [mm] [nomm]$\frac{a}{b}$[/nomm] [/mm] oder [mm] [nomm]$\bruch{a}{b}$[/nomm], [/mm] generell hilft Dir auch dieser Link [mm] ($\leftarrow$ einfach anklicken). Und anstelle der Doppel-m's, die die Formel umschließen, kannst Du auch einfach ein Dollarzeichen vor die Formel und eins dahinter schreiben.
Ansonsten sieht Deine Rechnung ja ganz gut aus. Und am Ende kommt ja auch das raus, was man haben will, von daher denke ich auch nicht, etwas zu übersehen (was natürlich dennoch passiert sein könnte).
> (b) Induktionsanfang: n=4 [/mm] [mm]2^4<4![/mm] 16<24
>
> dann kommt etwas verwirrendes, dass ich auch nicht so ganz
> verstehe, weil mir das jemand vorgesagt hat...
>
> Induktionsschritt:
>
> [mm](n+1)!=(n+1)*n!>(n+1)2^n >2*2^n=2^{n+1}[/mm] //
Welchen Schritt verstehst Du denn nicht? Hier kann man folgendes machen:
Behauptung:
Es gilt $n! > [mm] 2^n$ [/mm] für alle $n [mm] \ge [/mm] 4$.
I.-Start: Für n=4 gilt $n!=4!=24 > [mm] 16=2^4=n^4$, [/mm] also der Induktionsstart klappt.
Induktionsschritt:
Zu zeigen ist: Wenn $n! > [mm] 2^n$ [/mm] für ein $n [mm] \ge [/mm] 4$ gilt, dann gilt auch schon $(n+1)! > [mm] 2^{n+1}$.
[/mm]
(Wenn man das gezeigt hat: Weil $n! > [mm] 2^n$ [/mm] für n=4 gilt, liefert der Induktionsschritt dann ja, dass auch $(n+1)! > [mm] 2^{n+1}$, [/mm] also dass $n! > [mm] 2^n$ [/mm] auch für $n=5$ gilt. Weil dann aber $n! > [mm] 2^n$ [/mm] ja auch für $n=5$ gilt, liefert der Induktionsschritt dann auch, dass $n! > [mm] 2^n$ [/mm] für $n=6$ gilt etc.)
Also:
Induktionsschritt $n [mm] \mapsto [/mm] n+1$:
Es gelte (I.V.) $n! > [mm] 2^n$ [/mm] für (irgendein) $n [mm] \ge [/mm] 4$. Wegen
[mm] $(n+1)!=(n+1)*\underbrace{n*(n-1)*...*2*1}_{=n!}=(n+1)*n!$ [/mm]
liefert die Induktionsvoraussetzung (man beachte dabei $n+1 > 0$):
[mm] $(\star)$ $(n+1)!=(n+1)*\underbrace{n!}_{> 2^n} [/mm] > [mm] (n+1)*2^n\,.$
[/mm]
Jetzt ist es hinreichend, zu zeigen, dass $(n+1) [mm] *2^n \ge 2^{n+1}$ [/mm] gilt. Dazu gibt es zwei Möglichkeiten:
1.) Wie vorgeschlagen:
Wegen $n [mm] \ge [/mm] 4$ gilt insbesondere $n [mm] \ge [/mm] 1$ und damit $n+1 [mm] \ge [/mm] 2$, also gilt [mm] $(n+1)*2^n \ge 2*2^n=2^{n+1}$.
[/mm]
Man beendet nun den Induktionsbeweis, indem man diese Abschätzung bei [mm] $(\star)$ [/mm] benutzt:
[mm] $(n+1)!=(n+1)*\underbrace{n!}_{> 2^n} [/mm] > [mm] (n+1)*2^n \underset{\text{da }n+1 \ge 2}{\ge} 2*2^{n}=2^{n+1}$.
[/mm]
Insbesondere beinhaltet die letzte Ungleichungskette ja
$(n+1)! > [mm] 2^{n+1}\,,$
[/mm]
was man zu zeigen hat. [mm] $\blacksquare$
[/mm]
Eine andere Möglichkeit, um den Induktionsbeweis zu beenden, wäre
2.) Man überlegt sich, für genau welche $n$ denn [mm] $(n+1)*2^n \ge 2^{n+1}$ [/mm] gilt. Hier gilt wegen [mm] $2^{n+1}=2*2^n$:
[/mm]
[mm] $(n+1)*2^n \ge 2^{n+1}$
[/mm]
[mm] $\gdw$ $(n+1)*2^n \ge 2*2^{n}$
[/mm]
[mm] $\underset{\text{bea.: }2^n > 0}{\gdw}$ [/mm] $n+1 [mm] \ge [/mm] 2$
[mm] $\gdw$ [/mm] $n [mm] \ge [/mm] 1$.
Wegen $n [mm] \ge [/mm] 4$ gilt aber insbesondere $n [mm] \ge [/mm] 1$ (Transitivität von [mm] $\ge$), [/mm] und daher gilt hier [mm] $(n+1)*2^n \ge 2^{n+1}$.
[/mm]
Das Ende des Beweises folgt nun also genau wie bei der ersten Möglichkeit des Beweisendes.
P.S.:
Wenn Du magst, kannst Du auch den Induktionsbeweis hier anders führen:
Und zwar:
Dass $n! > [mm] 2^n$ [/mm] für alle $n [mm] \in \IN_{\ge 4}$ [/mm] gilt, ist äquivalent dazu, dass $(k+3)! > [mm] 2^{k+3}$ [/mm] für alle $k [mm] \in \IN$ [/mm] gilt (mit $0 [mm] \notin \IN$). [/mm]
Der Induktionsbeweis würde dann so aussehen:
I.-Start: $k=1$ Okay
I.V.: Sei $k [mm] \in \IN$ [/mm] mit $(k+3)! > [mm] 2^{k+3}$.
[/mm]
$k [mm] \mapsto [/mm] k+1$:
$(k+4)!=(k+4)*(k+3)! [mm] \underset{\text{I.V.}}{\ge} (k+4)*2^{k+3}$ [/mm]
Und hier erkennst Du nun wegen $k [mm] \ge [/mm] 1$ (da $k [mm] \in \IN$) [/mm] auch $k+4 [mm] \ge [/mm] 5 [mm] \ge [/mm] 2$. An dieser Stelle kann es vielleicht etwas helfen, aber i.a. sieht's (für meinen Geschmack) ansonsten wohl doch eher unübersichtlich(er) aus...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:27 Di 21.10.2008 | | Autor: | Hachiko8 |
erstmal danke für die antwort^^
ich hab mir meine Lösung zu (a) nochmal genaur angesehen und da hab ich doch das aufgeschrieben:
= [mm]\frac{n(n+1)(2n+1)+6(n+1)^2}{6}[/mm] = [mm]\frac{(n+1)(n(2n+1)+6(n+1)}{6}[/mm]
Jetzt ist mir aber aufgefallen dass beim 2.Term die potenz fehlt oder nicht?? wie lautet es dann richtig?
zu (b) versteh ich ni wieso du darauf gekommen bist: $ [mm] (n+1)!=(n+1)\cdot{}\underbrace{n\cdot{}(n-1)\cdot{}...\cdot{}2\cdot{}1}_{=n!}=(n+1)\cdot{}n! [/mm] $ wieso darf man das so aufspalten?ist das irgendein Gesetz?
Das gleiche bei:
und [mm] 2^n=(n+1) 2^n [/mm] und $ [mm] 2^{n+1}=2\cdot{}2^n [/mm] $
|
|
|
| |
|
Hallo Hachiko8,
> erstmal danke für die antwort^^
>
> ich hab mir meine Lösung zu (a) nochmal genaur angesehen
> und da hab ich doch das aufgeschrieben:
>
> = [mm] $\frac{n(n+1)(2n+1)+6(n+1)^2}{6}$ [/mm] =
> [mm] $\frac{(n+1)(n(2n+1)+6(n+1)\red{)}}{6}$ [/mm]
Oben hattest du noch richtigerweise die letzte rote Klammer gesetzt, also im Schritt vom ersten Bruch zum zweiten im Zähler $(n+1)$ ausgeklammert
>
> Jetzt ist mir aber aufgefallen dass beim 2.Term die potenz
> fehlt oder nicht?? wie lautet es dann richtig?
Ganz oben ist es noch richtig, hier hattest du die letzte Klammer vergessen!
>
> zu (b) versteh ich ni wieso du darauf gekommen bist:
> [mm](n+1)!=(n+1)\cdot{}\underbrace{n\cdot{}(n-1)\cdot{}...\cdot{}2\cdot{}1}_{=n!}=(n+1)\cdot{}n![/mm]
> wieso darf man das so aufspalten?ist das irgendein Gesetz?
Das ist doch nur stumpf die Definition der Fakultät
>
> Das gleiche bei:
>
> und [mm]2^n=(n+1) 2^n[/mm] ![[notok]](/images/smileys/notok.gif "[notok]")
wer hat das wo behauptet? oben sehe ich nur [mm] $2^{n+1}=2\cdot{}2^n<(n+1)\cdot{}2^n\underbrace{<}_{\text{nach IV}}(n+1)\cdot{}n!=(n+1)!$
[/mm]
Und genau das war zu zeigen im Induktionsschritt
> und [mm]2^{n+1}=2\cdot{}2^n[/mm]
na, das ist doch wohl ein dir hoffentlich bekanntes Potenzgesetz ...
LG
schachuzipus
|
|
|
|
