Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:19 Do 18.04.2013 | | Autor: | wiwawutz |
| Aufgabe | Für eine natürliche Zahl n betrachte man die Aussage
1. A(n) : [mm] n^{2}-5n+4\ge0
[/mm]
2.A(n) [mm] :n+1\ge [/mm] 2n
3.A(n) [mm] :2^{n}>n^{2}
[/mm]
4. A(n) [mm] :3^{2n}<2^{3n}
[/mm]
a) Für welche n [mm] \in \IN [/mm] ist der Induktionsschluss [mm] A(n)\Rightarrow [/mm] A(n+1) gültig?
b)Für welche n [mm] \in \IN [/mm] ist die Aussage A(n) wahr? |
Guten Tag ihr Lieben.
Ich stehe gerade wieder am Anfang meines Semesters, da ich durchgefallen bin. Jetzt habe ich hier ein paar Übungsaufgaben zur Induktion, bei denen ich auf der Strecke stehe.
Zu a) Ich muss ja jetzt den Induktionsanfang prüfen, sprich für n=1 (oder die 0) einsetzen. Zu 1. wäre das ja bewiesen das es auf jeden Fall größer gleich 0 ist.
Nur wie mache ich weiter, und wie zeige ich dann das der Induktionsschluss gültig ist??? Oder meinen die alle Aussagen zusammen? Ich weiß zwar, dass ich jetzt irgendwas mit n+1 zeigen muss, nur ich bin mir nicht sicher wie das funktioniert, Ich komme wirklich gar nicht weiter. Und auch das ganze googlen bringt mich nicht ans Ziel. Das ist einfach gar nicht mein Thema, ich wäre euch also durchaus dankbar, wenn jemand mir das evtl. an einer Aufgabe a) und b) vorrechnen könnte, damit ich bei den anderen das Verfahren anwenden kann.
Vielen Dank schonmal, Gruß wiwawutz
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:33 Do 18.04.2013 | | Autor: | Marcel |
Hallo,
> Für eine natürliche Zahl n betrachte man die Aussage
> 1. A(n) : [mm]n^{2}-5n+4\ge0[/mm]
> 2.A(n) [mm]:n+1\ge[/mm] 2n
> 3.A(n) [mm]:2^{n}>n^{2}[/mm]
> 4. A(n) [mm]:3^{2n}<2^{3n}[/mm]
>
> a) Für welche n [mm]\in \IN[/mm] ist der Induktionsschluss
> [mm]A(n)\Rightarrow[/mm] A(n+1) gültig?
> b)Für welche n [mm]\in \IN[/mm] ist die Aussage A(n) wahr?
> Guten Tag ihr Lieben.
> Ich stehe gerade wieder am Anfang meines Semesters, da ich
> durchgefallen bin.
woran lag's?
Ich schreibe jetzt keine Antwort, aber vielleicht kannst Du Dir ja
mal irgendwo das Buch hier ausleihen, um mal reinzugucken:
![[]](/images/popup.gif) (klick!)
( Nein, ich mach' keine Schleichwerbung und bin auch keiner der Autoren
des Buches und kenne die auch nicht.  )
Ich hab' da gerade mal, soweit Googel mir das erlaubt, reingeguckt,
und ich denke, dass da eben halt die Grundlagen gut und ausführlich
beschrieben sind, um die vollständige Induktion zu verstehen. Natürlich
können wir das auch hier zusammen aufbauen, aber Du siehst ja, dass
Du da nicht die/der einzige bist, der Probleme damit hat, sonst hätten
die das in dem Buch nicht so ausführlich alles nochmal zusammengeschrieben!
P.S. Die Aufgaben sind einzeln zu verstehen, Du hast oben also quasi 4
Aussagen/Aufgaben, die Du getrennt zu behandeln hast!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:52 Do 18.04.2013 | | Autor: | abakus |
> Für eine natürliche Zahl n betrachte man die Aussage
> 1. A(n) : [mm]n^{2}-5n+4\ge0[/mm]
> 2.A(n) [mm]:n+1\ge[/mm] 2n
> 3.A(n) [mm]:2^{n}>n^{2}[/mm]
> 4. A(n) [mm]:3^{2n}<2^{3n}[/mm]
>
> a) Für welche n [mm]\in \IN[/mm] ist der Induktionsschluss
> [mm]A(n)\Rightarrow[/mm] A(n+1) gültig?
> b)Für welche n [mm]\in \IN[/mm] ist die Aussage A(n) wahr?
> Guten Tag ihr Lieben.
> Ich stehe gerade wieder am Anfang meines Semesters, da ich
> durchgefallen bin. Jetzt habe ich hier ein paar
> Übungsaufgaben zur Induktion, bei denen ich auf der
> Strecke stehe.
>
> Zu a) Ich muss ja jetzt den Induktionsanfang prüfen,
Wieso?
Gerade das wird hier NICHT verlangt, es soll kein vollständiger Induktionsbeweis geführt werden.
Lies die Aufgabe gründlicher.
Gruß Abakus
> sprich für n=1 (oder die 0) einsetzen. Zu 1. wäre das ja
> bewiesen das es auf jeden Fall größer gleich 0 ist.
> Nur wie mache ich weiter, und wie zeige ich dann das der
> Induktionsschluss gültig ist??? Oder meinen die alle
> Aussagen zusammen? Ich weiß zwar, dass ich jetzt irgendwas
> mit n+1 zeigen muss, nur ich bin mir nicht sicher wie das
> funktioniert, Ich komme wirklich gar nicht weiter. Und auch
> das ganze googlen bringt mich nicht ans Ziel. Das ist
> einfach gar nicht mein Thema, ich wäre euch also durchaus
> dankbar, wenn jemand mir das evtl. an einer Aufgabe a) und
> b) vorrechnen könnte, damit ich bei den anderen das
> Verfahren anwenden kann.
>
> Vielen Dank schonmal, Gruß wiwawutz
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:19 Do 18.04.2013 | | Autor: | Marcel |
Hallo,
> > Für eine natürliche Zahl n betrachte man die Aussage
> > 1. A(n) : [mm]n^{2}-5n+4\ge0[/mm]
> > 2.A(n) [mm]:n+1\ge[/mm] 2n
> > 3.A(n) [mm]:2^{n}>n^{2}[/mm]
> > 4. A(n) [mm]:3^{2n}<2^{3n}[/mm]
> >
> > a) Für welche n [mm]\in \IN[/mm] ist der Induktionsschluss
> > [mm]A(n)\Rightarrow[/mm] A(n+1) gültig?
> > b)Für welche n [mm]\in \IN[/mm] ist die Aussage A(n) wahr?
> > Guten Tag ihr Lieben.
> > Ich stehe gerade wieder am Anfang meines Semesters, da
> ich
> > durchgefallen bin. Jetzt habe ich hier ein paar
> > Übungsaufgaben zur Induktion, bei denen ich auf der
> > Strecke stehe.
> >
> > Zu a) Ich muss ja jetzt den Induktionsanfang prüfen,
> Wieso?
> Gerade das wird hier NICHT verlangt, es soll kein
> vollständiger Induktionsbeweis geführt werden.
> Lies die Aufgabe gründlicher.
ich sehe das aber schon so, dass hier ein Induktionsbeweis geführt werden
soll. Denn etwa bei der Aufgabe, die ich vorgerechnet habe (die hier nicht steht):
$A(n)$: [mm] $n^2 \le 2^n\,.$
[/mm]
Da gilt jeder der Induktionsschlüsse $A(0) [mm] \Longrightarrow A(1)\,,$ [/mm] $A(1) [mm] \Longrightarrow A(2)\,,$ [/mm] aber nicht der $A(2) [mm] \Longrightarrow A(3)\,.$
[/mm]
Das folgt alleine, weil $A(0), A(1), [mm] A(2)\,$ [/mm] alle wahr, aber [mm] $A(3)\,$ [/mm] falsch ist.
Dass $A(4)$ gilt und dass dann $A(n) [mm] \Longrightarrow [/mm] A(n+1)$ für alle $n [mm] \ge [/mm] 4$ gilt,
bedarf eines Beweises, auch, wenn es in der Aufgabenstellung nicht explizit verlangt wird!
(Es gibt in der Mathematik halt auch ein gewisses "automatisches Verlangen" in Beweisen - wobei
das auch wiederum etwas unterschiedlich ist: Wenn ich einen Hinweis zu einer Aufgabe geben würde,
würde ich automatisch wollen, dass dieser auch bewiesen wird, es sei denn, ich schreibe explizit dazu,
dass das nicht nötig ist. Andere sehen das wiederum genau andersherum: Der Hinweis ist nur dann
eines Beweises bedürftig, wenn das explizit dazu gesagt wird...
Bei mir ist der Grund einfach der: Wenn ich etwas benutze, von dem ich nicht weiß, ob es richtig ist,
kann ich ziemlichen Unfug getrieben haben, wenn es doch falsch gewesen ist. (So habe ich übrigens
auch mal meinem damaligen Prof. mitteilen dürfen, dass sein Hinweis für eine Übungsaufgabe eine falsche
Aussage war - und ich hatte die Aufgabe damals daher gar nicht bearbeitet, weil mich das verwirrte. Fast
alle anderen haben sie gelöst, aber die Lösung war falsch, weil sie es mit dem Hinweis gelöst
hatten - dennoch hatte ich 0 Punkte, alle anderen die 4 Punkte für die Aufgabe. Da war es auch kein
großer Trost, dass der Prof. die Aufgabe dann nachträglich wegen seines falschen Hinweises als
Zusatzaufgabe deklariert hatte, denn die anderen hatten dann ja doch 4 Punkte mehr als ich, die sie
eigentlich nicht hätten haben dürfen...)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:05 Do 18.04.2013 | | Autor: | Marcel |
Hallo,
> Für eine natürliche Zahl n betrachte man die Aussage
> 1. A(n) : [mm]n^{2}-5n+4\ge0[/mm]
> 2.A(n) [mm]:n+1\ge[/mm] 2n
> 3.A(n) [mm]:2^{n}>n^{2}[/mm]
> 4. A(n) [mm]:3^{2n}<2^{3n}[/mm]
ich rechne Dir keine der Aufgaben hier vor, aber eine, die der
4. sehr ähnelt.
Frage: Für genau welche $n [mm] \in \IN_0=\IN \cup \{0\}$ [/mm] gilt [mm] $n^2 \le 2^n$?
[/mm]
Antwort: Für genau alle $n [mm] \in \IN_0 \setminus \{3\}$!
[/mm]
Beweis: 1.) Wir führen zunächst einen Induktionsbeweis, dass die Aussage für
alle natürlichen $n [mm] \ge [/mm] 4$ gilt. (Wir könnten auch einen Induktionsbeweis für $n [mm] \ge n_0$
[/mm]
mit einem natürlichen [mm] $n_0 [/mm] > 4$ führen - warum? Und was wäre danach dann noch zu tun, wenn
wir das so machen würden?)
Induktionsanfang: Für $n=4$ gilt [mm] $n^2=4^2=16 \le 16=2^4=2^n\,.$
[/mm]
Induktionsschritt: Sei $n [mm] \ge [/mm] 4$ und es gelte [mm] $n^2 \le 2^n\,.$ [/mm] Wir haben zu zeigen, dass daraus
schon folgt, dass [mm] $(n+1)^2 \le 2^{n+1}$ [/mm] gilt.
Es gilt
[mm] $$(n+1)^2=n^2+2n+1 \le 2^n+2n+1\,,$$
[/mm]
da aufgrund der Induktionsvoraussetzung [mm] $n^2 \le 2^n$ [/mm] benutzt werden darf. Wenn wir nun noch
[mm] $2^n+2n+1 \le 2^{n+1}$ [/mm] beweisen können, sind wir fertig:
Es gilt
[mm] $$\blue{2^n+2n+1 \le 2^{n+1}}$$
[/mm]
[mm] $$\iff 2^n+2n+1 \le 2*2^{n}$$
[/mm]
[mm] $$\iff 2^n+2n+1 \le 2^n+2^n$$
[/mm]
[mm] $$\iff \red{2n+1 \le 2^n}\,.$$
[/mm]
Wenn wir also die rote Ungleichung begründen, so folgt aus dieser durch Lesen der Umformungen
von unten nach oben unter Benutzung der [mm] $\Longleftarrow$'s [/mm] die blaue - man beachte, dass wir hier
stets $n [mm] \in \IN_0$ [/mm] mit [mm] $\text{\blue{n}} \;\mathbf{\blue{\ge}}\; \text{\blue{4}}$ [/mm] auch haben.
Dazu ist es wegen der I.V. [mm] $n^2 \le 2^n$ [/mm] hinreichend, zu beweisen, dass $2n+1 [mm] \le n^2$ [/mm] für alle natürlichen
$n [mm] \ge [/mm] 4$ gilt.
Dies machen wir jetzt nicht per Induktion (was auch ginge - aber wir wollen Induktionsbeweise hier nicht
zu sehr "ineinander verschachteln"), sondern so: Wir können ein natürliches $n [mm] \ge [/mm] 4$ als [mm] $n=4*k\,$ [/mm] mit einem
$k [mm] \in \IN=\IN \setminus \{0\}$ [/mm] schreiben. Dann gilt für diese $n [mm] \ge [/mm] 4$
$$2n+1 [mm] \le n^2$$
[/mm]
[mm] $$\iff [/mm] 8k+1 [mm] \le 16k^2$$
[/mm]
[mm] $$\iff 16k^2-8k-1 \ge [/mm] 0$$
[mm] $$\iff \green{8k^2+(8k^2-k)-1 \ge 0}\,.$$
[/mm]
Da für $k [mm] \ge [/mm] 1$ offenbar [mm] $8k^2-k=k*(8k-1) \ge [/mm] 1*7=7$ ist, ist auch [mm] $(8k^2-k)-1 \ge [/mm] 0$ und damit die
grüne Ungleichung bewiesen (da [mm] $8k^2 \ge [/mm] 0$ offensichtlich gilt)!
Zusammenfassend:
Bewiesen wurde, dass für jedes natürliche $n [mm] \ge [/mm] 4$ gilt, dass
$$2n+1 [mm] \le n^2\,.$$
[/mm]
Nach Induktionsvoraussetzung gilt für jedes natürliche $n [mm] \ge [/mm] 4$
[mm] $$n^2 \le 2^n\,.$$
[/mm]
Damit haben wir im Induktionsschritt die zusätzliche Ungleichung
[mm] $$\red{2n+1} \le n^2 \red{\le 2^n}\;\;\;(n \ge [/mm] 4)$$
gefolgert. Daraus folgt
[mm] $$2^n+2n+1 \le 2^n+2^n\,,$$
[/mm]
also
[mm] $$(\*)\;\;\;2^n+2n+1 \le 2^{n+1}\,.$$
[/mm]
Mit der Induktionsvoraussetzung haben wir
[mm] $$(n+1)^2=n^2+2n+1 \le 2^n+2n+1$$
[/mm]
für $n [mm] \ge [/mm] 4$ begründet. Mit [mm] $(\*)$ [/mm] folgt dann
[mm] $$(n+1)^2=n^2+2n+1 \stackrel{\text{I.V.}}{\le} 2^n+2n+1 \stackrel{(\*)}{\le} 2^{n+1}\,,$$
[/mm]
und damit war der Beweis des Induktionsschrittes beendet, also 1.) beendet!
Bisher bewiesen:
[mm] $n^2 \le 2^n$ [/mm] gilt für alle natürlichen $n [mm] \ge 4\,.$
[/mm]
Nun 2.)
(Und das kannst Du nun alleine tun):
Einfaches nachrechnen zeigt, dass die Ungleichung [mm] $n^2 \le 2^n$ [/mm] wahr ist für [mm] $n=0,\,1,\,2\,,$ [/mm] und offenbar ist wegen
[mm] $3^2=... [/mm] > [mm] ...=2^3$ [/mm] die Ungleichung für [mm] $n=3\,$ [/mm] falsch!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:01 Do 18.04.2013 | | Autor: | kaju35 |
Hallo wiwawutz,
Zu Aufgabe 1.
Setze doch mal $n+1$ in die Ungleichung
ein, klammer aus und subtrahiere die
Ungleichung für $n$. Beim Beweis mittels
vollständiger Induktion gehst Du dann den
umgekehrten Weg : Du fängst an mit
[mm] $n^2-5\cdot n+4\ge [/mm] 0$, addierst die Differenz
von zuvor (von der noch zu zeigen ist, dass sie größer
gleich $0$ ist) und fasst wieder zusammen! Du erhältst
die Ungleichung für $n+1$ und damit den gültigen
Induktionsschritt [mm] ($(n+1)^2-5\cdot(n+1)+4\ge [/mm] 0$).
Zu Aufgabe 2. Teil b)
Zieh doch einfach auf beiden Seiten
$n$ ab und schon steht da, für welche
[mm] $n\in\mathbb{N}$ [/mm] die Ungleichung gilt!
Gruß
Kai
|
|
|
|
