Beweise mittels Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:46 Mo 31.01.2011 | | Autor: | Sup |
| Aufgabe | a) 3^(2n+1)+5 ist durch 8 teilbar (n [mm] \in \IN)
[/mm]
b) [mm] \summe_{j=0}^{n}(-1)^j\vektor{n \\ j} [/mm] = 0 (n [mm] \in \IN \cup [/mm] {0})
Tipp: Verwende die Identität [mm] \vektor{n+1 \\ j}=\vektor{n \\ j}+\vektor{n \\ j+1}
[/mm]
c) [mm] 3^n \ge n^3 [/mm] für jede natürliche Zahl [mm] n\ge3 [/mm] |
Hallo zusammen,
es geht in allen 3 Aufgaben, um den Beweis der Aussagen mittels volständiger Induktion.
a) Ich lasse mal die 1. beiden Schritte weg um fange gleich mal mit dem Induktionschritt an:
n [mm] \Rightarrow [/mm] n+1 :
3^(2(n+1)+1) +5 = 3^(2n+3) +5 = [mm] 3^{2n+1}*3^2+5
[/mm]
Ich persönlich wüsste jetzt weder wie ich das noch großartig weiter umformen soll, noch wie ich daran zeige, dass es durch 8 teilbar ist.
b) hier habe ich ein Problem mit dem Induktionsanfang.
Wenn ich n=0 setzte ist alles ok (Ergebnis: [mm] \vektor{0 \\ 0}).
[/mm]
Für n=1 bekomme ich aber [mm] \vektor{0 \\ -1} [/mm] heraus.....
c) hier macht mir wieder die Begründung Probleme:
n [mm] \Rightarrow [/mm] n+1 :
3^(n+1) [mm] \ge (n+1)^3
[/mm]
= 3^(n+1) [mm] \ge n^3+3n^2+3n+1
[/mm]
Hoffe ihr könnt mir da helfen
Gruß
~sup
|
|
| |
|
Zu a)
Betrachte $ [mm] 3^{2n+1}\cdot{}3^2+5 [/mm] $
Du weißt, dass [mm] 3^{2n+1}+5 [/mm] teilbar durch 8 ist.
Wie kannst du daher [mm] 3^{2n+1}+5 [/mm] anders schreiben?
Wie dann [mm] 3^{2n+1}?
[/mm]
Wie dann [mm] 3^{2n+1}\cdot{}3^2?
[/mm]
Wie dann $ [mm] 3^{2n+1}\cdot{}3^2+5 [/mm] $?
-----------------------------
Zu b)
B ist für n=0 falsch. Ansonsten ist sie richtig, ich sehe aber den Zusammenhang mit der Vollst. Ind. nicht.
Beispiel aus dem Pascalschen Dreieck:
Reihe 4 1 4 6 4 1
Reihe 5 1 5 10 10 5 1
Reihe 6 1 6 15 20 15 6 1
Jede Folgereihe kommt so zu Stande, dass die darüberstehende Zahl einmal als Summand nach links und einmal nach rechts geht, also (von Reihe 5 auf 6)
1 zu 1 und 6, 5 zu 6 und 15, 10 zu 15 und 20, 10 zu 20 und 15, 5 zu 15 und 6, 1 zu 6 und 1. (Daher ist übrigens die Summe aller Zahlen in einer Reihe immer doppelt so groß wie die vorhergehende und damit gleich [mm] 2^n.)
[/mm]
Nun sieht man, wie sich das auswirkt, wenn man auf die zu bildende Summe blickt:
Obige Reihen werden zu
Reihe 4 1 -4 6 -4 1
Reihe 5 1 -5 10 -10 5 -1
Reihe 6 1 -6 15 -20 15 -6 1
Jede Zahl geht also (absolut) einmal nach links und eimal nach rechts in den jeweiligen positiven oder negativen Summanden , wird dabei also einmal positiv und einmal negativ gezählt. Daher muss die Summe 0 sein, egal ob das vorher auch schon so war. Der Beweis geht also ohne V.I., ob mit V.I, weiß ich auch nicht.
Beispiel:
Vorreihe: 2 7 8 3 3
Folgereihe: 2 9 15 11 6 3
Nun ist
Vorreihe: 2 -7 8 -3 3 gibt als Summe 3, aber
Folgereihe: 2 -9 15 -11 6 -3 gibt als Summe 0, folgt also nicht aus "Vorreihe=0".
-------------------
c) Verwandle auch [mm] 3^{n+1} [/mm] in [mm] 3*3^n [/mm] > [mm] 3*n^3 [/mm] und zeige, dass das größer ist als [mm] (n+1)^3.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:00 Mo 31.01.2011 | | Autor: | Sup |
> Zu a)
>
> Betrachte [mm]3^{2n+1}\cdot{}3^2+5[/mm]
>
> Du weißt, dass [mm]3^{2n+1}+5[/mm] teilbar durch 8 ist.
> Wie kannst du daher [mm]3^{2n+1}+5[/mm] anders schreiben?
[mm] 3^{2n}*3^1+5 [/mm]
> Wie dann [mm]3^{2n+1}?[/mm]
[mm] 3^{2n}*3^1
[/mm]
> Wie dann [mm]3^{2n+1}\cdot{}3^2?[/mm]
> Wie dann [mm]3^{2n+1}\cdot{}3^2+5 [/mm]?
[mm] 3^{2n+3}+5 [/mm] oder [mm] 3^{2(n+1)}*3^1+5
[/mm]
Srry aber ich weiß nicht genau worauf du hinaus willst. Was kann ich sonst machen, außer die Potenzen zusammenfassen bzw. "trennen"
> -----------------------------
>
> Zu b)
>
> B ist für n=0 falsch. Ansonsten ist sie richtig, ich sehe
> aber den Zusammenhang mit der Vollst. Ind. nicht.
Es geht darum, dass ich den Induktionsanfang für n=1 nicht hinbekomme :(
Ich stehe wahrscheinlich derbe aufm Schlach aber hier ist was ich zu n=1 rechne:
[mm] \summe_{i=0}^{1}=(-1)^j\vektor{1 \\ j} [/mm] = [mm] (-1)^0\vektor{1 \\ 0} [/mm] + [mm] (-1)^1\vektor{1 \\ 1} [/mm] = [mm] \vektor{1 \\ 0} [/mm] - [mm] \vektor{1 \\ 1} [/mm] = [mm] \vektor{0 \\ -1}
[/mm]
Dein Beweis mag zwar stimmen, nur muss ich das leider per Induktion beweisen
> -------------------
> c) Verwandle auch [mm]3^{n+1}[/mm] in [mm]3*3^n[/mm] > [mm]3*n^3[/mm] und zeige,
> dass das größer ist als [mm](n+1)^3.[/mm]
wie kommst du auf [mm] 3*n^3 [/mm] ?
>
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:05 Mo 31.01.2011 | | Autor: | Loddar |
Hallo Sup!
> > c) Verwandle auch [mm]3^{n+1}[/mm] in [mm]3*3^n[/mm] > [mm]3*n^3[/mm] und zeige,
> > dass das größer ist als [mm](n+1)^3.[/mm]
> wie kommst du auf [mm]3*n^3[/mm] ?
Hier wurde auf [mm] $3*3^n$ [/mm] die Induktionsvoraussetzung angewandt.
Denn gemäß dieser gilt ja: [mm] $3^n [/mm] \ > \ [mm] n^3$ [/mm] .
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:27 Mo 31.01.2011 | | Autor: | Sup |
> Hallo Sup!
>
>
> > > c) Verwandle auch [mm]3^{n+1}[/mm] in [mm]3*3^n[/mm] > [mm]3*n^3[/mm] und zeige,
> > > dass das größer ist als [mm](n+1)^3.[/mm]
> > wie kommst du auf [mm]3*n^3[/mm] ?
>
> Hier wurde auf [mm]3*3^n[/mm] die Induktionsvoraussetzung
> angewandt.
> Denn gemäß dieser gilt ja: [mm]3^n \ > \ n^3[/mm] .
Also habe ich jetzt folgendes da stehen:
[mm] 3n^3 \ge (n+1)^3
[/mm]
Mag blöd erscheinen aber ich komm im moment nicht drauf -.-
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:20 Mo 31.01.2011 | | Autor: | Marcel |
Hallo,
> > Hallo Sup!
> >
> >
> > > > c) Verwandle auch [mm]3^{n+1}[/mm] in [mm]3*3^n[/mm] > [mm]3*n^3[/mm] und zeige,
> > > > dass das größer ist als [mm](n+1)^3.[/mm]
> > > wie kommst du auf [mm]3*n^3[/mm] ?
> >
> > Hier wurde auf [mm]3*3^n[/mm] die Induktionsvoraussetzung
> > angewandt.
> > Denn gemäß dieser gilt ja: [mm]3^n \ > \ n^3[/mm] .
>
> Also habe ich jetzt folgendes da stehen:
> [mm]3n^3 \ge (n+1)^3[/mm]
> Mag blöd erscheinen aber ich komm im
> moment nicht drauf -.-
bei (Induktions-)Beweisen ist es wichtig, eine vernünftige und übersichtliche Beweisstruktur zu haben.
Behauptung: [mm] $3^n \ge n^3$ [/mm] gilt für alle natürlichen $n [mm] \ge 3\,.$
[/mm]
Beweis per Induktion: Induktionsstart [mm] $n=3\,:$
[/mm]
[mm] $$3^n=3^3=27 \ge 3^3=n^3\,,$$
[/mm]
passt also.
$$n [mm] \mapsto n+1\,:$$
[/mm]
Nach Voraussetzung gilt für natürliches $n [mm] \ge [/mm] 3$ die Ungleichung
[mm] $$(\star) \;\;3^n \ge n^3\,.$$
[/mm]
Induktionsschritt $n [mm] \mapsto n+1\,:$
[/mm]
Wir haben nun ZU ZEIGEN, dass [mm] $(\star)$ [/mm] gilt, wenn man dort [mm] $n\;$ [/mm] durch [mm] $n+1\,$ [/mm] ersetzt. Es ist also
[mm] $$3^{n+1} \ge (n+1)^3$$
[/mm]
zu begründen, unter der VORAUSSETZUNG, dass das natürliche $n [mm] \ge [/mm] 3$ mit [mm] $3^n \ge n^3$ [/mm] gegeben sei (letztere Ungleichung darf also verwendet werden).
Nun gilt (wichtig sind vor allem die Folgerungen [mm] "$\Leftarrow$")
[/mm]
[mm] $$3^{n+1} \ge (n+1)^3$$
[/mm]
[mm] $$\gdw\; (\star_2)\;\;3*3^{n} \ge (n+1)^3\,.$$
[/mm]
Wegen der binomischen Formel (oder durch direktes nachrechnen) gilt [mm] $(n+1)^3=n^3+3n^2+3n+1\,,$ [/mm] so dass
[mm] $$(\star_2)\;\gdw 3*3^n \ge n^3+3n^2+3n+1\,.$$
[/mm]
Durch Verfolgen der Folgerungen [mm] "$\Leftarrow$" [/mm] und Lesen der Ungleichungen von unten nach oben erkennen wir, dass wir die Ungleichung
[mm] $$3^{n+1} \ge (n+1)^3$$
[/mm]
(für unser natürliches $n [mm] \ge [/mm] 3$ mit [mm] $3^n \ge n^3$) [/mm] bewiesen haben, wenn wir die Ungleichung
[mm] $$(\star_2)\;\gdw 3*3^n \ge n^3+3n^2+3n+1$$
[/mm]
(für unser natürliches $n [mm] \ge [/mm] 3$ mit [mm] $3^n \ge n^3$) [/mm] begründen können.
Wir wissen schon, dass [mm] $n^3 \le 3^n$ [/mm] wegen [mm] $(\star)$ [/mm] (Induktionsvoraussetzung) gilt. Daraus ergibt sich, dass
[mm] $$3*3^n \ge 3*n^3$$
[/mm]
(für unser natürliches $n [mm] \ge [/mm] 3$ mit [mm] $3^n \ge n^3$) [/mm] gilt.
----
Nun eine Zwischenüberlegung:
Wenn wir nun begründen können, dass
[mm] $$3*n^3 \ge n^3+3n^2+3n+1$$
[/mm]
(für unser natürliches $n [mm] \ge [/mm] 3$ mit [mm] $3^n \ge n^3$), [/mm] so ergibt sich doch aus
[mm] $$3^{n+1}=3*3^n \ge 3*n^3 \ge n^3+3n^2+3n+1=(n+1)^3$$
[/mm]
dann
[mm] $$3^{n+1} \ge (n+1)^3\,.$$
[/mm]
----
Nun zeige halt:
Für unser natürliches $n [mm] \ge [/mm] 3$ mit [mm] $3^n \ge n^3$ [/mm] gilt insbesondere
[mm] $$3*n^3 \ge (n+1)^3\,,$$
[/mm]
bzw. Deine Aufgabe besteht nun darin, zu beweisen, dass
[mm] $$3*n^3 \ge n^3+3n^2+3n+1$$
[/mm]
bzw.
[mm] $$2n^3 -3n^2-3n-1 \ge 0\,.$$
[/mm]
Wegen $n [mm] \ge [/mm] 3$ kann man aber $n=m+3$ mit einem $m [mm] \in \IN_0$ [/mm] schreiben, so dass man die letzte Ungleichung auch in der Form
[mm] $$2*(m+3)^3 -3(m+3)^2-3(m+3) [/mm] -1 [mm] \ge [/mm] 0$$
bringen kann. Warum gilt nun die letzte Ungleichung? (Man kann sie leicht in eine Form bringen, so dass man ein Polynom dritten Grades [mm] $\sum_{k=0}^3 a_k x^k$ [/mm] mit [mm] $a_k \ge [/mm] 0$ [mm] ($k=0,1,2,3\,$) [/mm] sieht, und wenn man da $m [mm] \in \IN_0$ [/mm] einsetzt, wird der Wert dieses Polynoms an der Stelle [mm] $m\,$ [/mm] natürlich auch [mm] $\ge [/mm] 0$ sein).
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:00 Di 01.02.2011 | | Autor: | Sup |
Danke, damit wäre das auch geklärt.
Die ersten beiden Schritte (Induktionsanfang und -vorraussetzung) habe ich hier aus Zeitgründen (und ein wenig aus Faulheit^^) nicht hingeschrieben.
Danke, dass du dir trotzdem die Mühe gemacht hats.
Danke auch an alle anderen beteiligten.
Da ich die Aufgaben morgen vormittag abgeben muss werde ich zu b) schreiben, dass unter Berücksichtigung der Vorgaben in der Aufgabe, ein (korrekter) Induktionsanfang nicht gegeben ist
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:07 Mo 31.01.2011 | | Autor: | Loddar |
Hallo Sup!
Betrachte [mm] $3^{2n+1}*3^2+5 [/mm] \ = \ [mm] 9*3^{2n+1}+5$ [/mm] .
Zerlege dabei den Faktor $9_$ in $(8+1)_$ .
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:15 Mo 31.01.2011 | | Autor: | Sup |
ok a) hab ich vertsanden, danke
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:35 Mo 31.01.2011 | | Autor: | ullim |
Hi,,
> Zu b)
> Es geht darum, dass ich den Induktionsanfang für n=1 nicht hinbekomme :(
> Ich stehe wahrscheinlich derbe aufm Schlach aber hier ist was ich zu n=1 rechne:
> [mm] \summe_{i=0}^{1}=(-1)^j\vektor{1\\j}=(-1)^0\vektor{1\\0}+(-1)^1\vektor{1\\1}=\vektor{1\\0}-\vektor{1\\1}=\vektor{0\\-1}
[/mm]
[mm] \vektor{1\\0}=1
[/mm]
[mm] \vektor{1\\1}=1
[/mm]
also [mm] \vektor{1\\0}-\vektor{1\\1}=0
[/mm]
Und es gilt i.a. nicht [mm] \vektor{n\\m}-\vektor{k\\l}=\vektor{n-k\\m-l}
[/mm]
den
[mm] \vektor{4\\2}-\vektor{2\\1}=4
[/mm]
[mm] \vektor{2\\1}=2
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:21 Mo 31.01.2011 | | Autor: | Sup |
Also ich kapier nicht was dieses [mm] \vektor{n \\ j} [/mm] eigentlich ist.
Es ist kein Vektor (iwe ich zuerst angenommen hab), da dann die Gleichung für n=1 nicht aufgeht.
Anhand deines Posts dachte ich es handle sich um Binomialkoeffizienten. Damit geht die Gleichung für n=1 auch auf.
Für n=0 aber wieder nicht.
[mm] \summe_{i=0}^{0}=(-1)^j\vektor{0\\j}=(-1)^0\vektor{0\\0} [/mm] =1*1=1
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:31 Mo 31.01.2011 | | Autor: | ullim |
Hi,
> Also ich kapier nicht was dieses [mm]\vektor{n \\ j}[/mm] eigentlich
> ist.
> Es ist kein Vektor (iwe ich zuerst angenommen hab), da
> dann die Gleichung für n=1 nicht aufgeht.
>
> Anhand deines Posts dachte ich es handle sich um
> Binomialkoeffizienten. Damit geht die Gleichung für n=1
> auch auf.
> Für n=0 aber wieder nicht.
>
> [mm]\summe_{i=0}^{0}=(-1)^j\vektor{0\\j}=(-1)^0\vektor{0\\0}[/mm]
> =1*1=1
>
[mm] \vektor{n \\ j} [/mm] ist der Binomialkoeffizient. Im allgemeinen gilt
[mm] (a+b)^n=\summe_{j=0}^{n}\binom{n}{j}a^{n-j}*b^j
[/mm]
setze a=1 und b=-1 dann folgt die Behauptung.
|
|
|
| |
|
| Status: |
(Korrektur) kleiner Fehler  | | Datum: | 23:46 Mo 31.01.2011 | | Autor: | Marcel |
Hallo ullim,
> Hi,
>
> > Also ich kapier nicht was dieses [mm]\vektor{n \\ j}[/mm] eigentlich
> > ist.
> > Es ist kein Vektor (iwe ich zuerst angenommen hab), da
> > dann die Gleichung für n=1 nicht aufgeht.
> >
> > Anhand deines Posts dachte ich es handle sich um
> > Binomialkoeffizienten. Damit geht die Gleichung für n=1
> > auch auf.
> > Für n=0 aber wieder nicht.
> >
> > [mm]\summe_{i=0}^{0}=(-1)^j\vektor{0\\j}=(-1)^0\vektor{0\\0}[/mm]
> > =1*1=1
> >
>
> [mm]\vektor{n \\ j}[/mm] ist der Binomialkoeffizient. Im allgemeinen
> gilt
>
> [mm](a+b)^n=\summe_{j=0}^{n}\binom{n}{j}a^{n-j}*b^j[/mm]
>
> setze a=1 und b=-1 dann folgt die Behauptung.
wegen [mm] $0^0=1\,$ [/mm] folgt die Behauptung nicht so, wie sie in der Aufgabenstellung steht. Denn die Behauptung in der Aufgabenstellung
[mm] $$\sum_{j=0}^n (-1)^j{n \choose j}=0$$
[/mm]
ist für [mm] $n=0\,$ [/mm] falsch, da schon richtig erkannt wurde
[mm] $$(-1)^0 [/mm] {0 [mm] \choose [/mm] 0}=1*1=1 [mm] \not=0\,.$$
[/mm]
Da hat der Aufgabensteller geschlampt. Denn in der Form
[mm] $$\sum_{j=0}^n (-1)^j [/mm] {n [mm] \choose j}=0^n=\begin{cases} 1, & \mbox{falls } n=0,\\0, & \mbox{falls } n \ge 1 \end{cases}$$
[/mm]
kann man die Aufgabe durchaus für $n [mm] \in \IN_0:=\IN \cup \{0\}$ [/mm] stellen. Hier ist aber der Sonderfall [mm] $n=0\,$ [/mm] und [mm] $0^0=1$ [/mm] zu beachten.
Natürlich stimmt Dein Hinweis, wie man die Aufgabe mit dem binomischen Lehrsatz lösen kann, dennoch.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:39 Mo 31.01.2011 | | Autor: | Marcel |
Hallo,
> Also ich kapier nicht was dieses [mm]\vektor{n \\ j}[/mm] eigentlich
> ist.
> Es ist kein Vektor (iwe ich zuerst angenommen hab), da
> dann die Gleichung für n=1 nicht aufgeht.
>
> Anhand deines Posts dachte ich es handle sich um
> Binomialkoeffizienten. Damit geht die Gleichung für n=1
> auch auf.
> Für n=0 aber wieder nicht.
>
> [mm]\summe_{i=0}^{0}=(-1)^j\vektor{0\\j}=(-1)^0\vektor{0\\0}[/mm]
> =1*1=1
Dein Einwand hier ist vollkommen korrekt. Die Aufgabenstellung ist falsch:
Entweder sollte da stehen
[mm] $$\sum_{k=0}^n (-1)^k [/mm] {n [mm] \choose [/mm] k}=0$$
für alle $n [mm] \in \IN=\blue{\IN_0 \setminus \{0\}}\,,$ [/mm] oder aber man sollte schreiben
[mm] $$\sum_{k=0}^n (-1)^k [/mm] {n [mm] \choose [/mm] k}=0$$
für alle natürlichen $n [mm] \ge [/mm] 1$ und
[mm] $$\sum_{k=0}^n (-1)^k [/mm] {n [mm] \choose k}=\sum_{k=0}^0 (-1)^k [/mm] {0 [mm] \choose [/mm] k}=1$$
für [mm] $n=0\,.$
[/mm]
Allgemeiner:
[mm] $$\sum_{k=0}^n (-1)^k [/mm] {n [mm] \choose k}=0^n$$
[/mm]
für alle $n [mm] \in \IN_0\,,$ [/mm] wobei man [mm] $0^0:=1$ [/mm] vereinbare.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:50 Mo 31.01.2011 | | Autor: | ullim |
Hi,
da hast Du recht, für n=0 ist die Aufgabenstellung nicht richtig.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:04 Di 01.02.2011 | | Autor: | Sup |
Danke auch an alle anderen beteiligten.
Da ich die Aufgaben morgen vormittag abgeben muss werde ich zu b) schreiben, dass unter Berücksichtigung der Vorgaben in der Aufgabe, ein (korrekter) Induktionsanfang nicht gegeben ist
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:53 Mo 31.01.2011 | | Autor: | Marcel |
Hallo,
da es Dich zu verwirren schien:
> b)
> [mm]\summe_{j=0}^{n}(-1)^j\vektor{n \\ j}[/mm] = 0 (n [mm]\in \IN \cup \{0\}[/mm])
Die Aufgabe ist falsch gestellt und sollte in der Form
$$ [mm] \sum_{j=0}^n (-1)^j [/mm] {n [mm] \choose j}=0^n\;\;\left(\;=\begin{cases} 1, & \mbox{falls } n=0,\\0, & \mbox{falls } n \ge 1 \end{cases}\;\;\right)$$
[/mm]
bearbeitet werden.
Gruß,
Marcel
|
|
|
|
