Induktionsbeweis und n!..

25.10.2006, 18:12

Susi1987

Induktionsbeweis und n!..

hi ich muss so einiges machen, aber ich komm gar nicht dahinter wie genau ich das anstellen soll.

Ich komm leider mit beiden nicht ganz klar - bin noch ziemlich neu an der Uni und es ist mein 1. jahr.

1. n € N0
$\begin{eqnarray*} \sum_{k=0}^n~(-1)^k2^k\begin{pmatrix} n \\ k \end{pmatrix}=(-1)^n \end{eqnarray*}$
2. n € N0
$\begin{eqnarray*} \sum_{k=0}^n~\frac{(-1)^{k}}{k+1}\begin{pmatrix} n \\ k \end{pmatrix}=\frac{1}{n+1} \end{eqnarray*}$
3.
a) Show: If M is a set consisting of n elements then the number of subsets of M containing k elements $\begin{eqnarray*} (0\leq k\leq n) is \begin{pmatrix} n \\ k \end{pmatrix}. \end{eqnarray*}$

b) Determine the number of subsets of a set consisting of n elements.

-------------------------------------------------------------------------------------------------------

Mit der 1. Übung hatte ich keinerlei Probleme - auch nicht mit Induktionsbeweisen an sich, jedoch fehlt mit der ansatz.

n=0 müsste man ja beginnen- dafür gehts.
n -> n+1 da stellt sich die Frage: Setze ich auch für k n+1 ein oder wenn k da steht mache ich nur k + 1 ?
Auf beiden Seiten? Wäre dankbar für schnelle Hilfe ..

EDIT: $\begin{eqnarray*} \text{LaTeX} \end{eqnarray*}$ (therisen)

25.10.2006, 18:25

tigerbine

Auf diesen Beitrag antworten »

RE: Induktionsbeweis und n!..
1. Aufgabe

IA: n = 0

$\begin{eqnarray*} (-1)^{0} \cdot 2^{0} \cdot \begin{pmatrix} 0 \\0 \end{pmatrix} = 1\cdot1\cdot1 = (-1)^{0} \end{eqnarray*}$

Also stimmt die Behauptung für n=0

IV: Sei die Behauptung richtig für n-1. Dann gilt:

$\begin{eqnarray*} \sum_{k=0}^{n-1}~(-1)^{k}2^{k} \begin{pmatrix} n-1 \\k \end{pmatrix} = (-1)^{n-1} \end{eqnarray*}$

IS: Zeige nun mit Hilfe von IV (z.B. durch Aufspalten der Summe), dass die Formel auch für n gilt.

25.10.2006, 18:33

Susi1987

Auf diesen Beitrag antworten »

n-1 ? sonst immer n+1 hä?

außerdem wäre eine lösung von einer aufgabe nicht schlecht, damit ich mir es dadurch aneignen kann.

dankööö

25.10.2006, 18:37

therisen

Auf diesen Beitrag antworten »

RE: Induktionsbeweis und n!..
Ich weiß ja nicht, ob du die erste Aufgabe unbedingt mit Induktion beweisen sollst, aber es geht auch viel einfacher und direkt, wenn man den binomischen Lehrsatz kennt: $\begin{eqnarray*} (x+y)^n = \sum_{k=0}^n {n \choose k} x^ky^{n-k} \end{eqnarray*}$ .
Wegen $\begin{eqnarray*} (-1)^k2^k = (-2)^k \end{eqnarray*}$ genügt es also, $\begin{eqnarray*} x=-2 \end{eqnarray*}$ und $\begin{eqnarray*} y=1 \end{eqnarray*}$ zu setzen.

Allgemein empfehle ich dir mal [Workshop] Vollständige Induktion durchzulesen Augenzwinkern

Gruß, therisen

25.10.2006, 18:43

tigerbine

Auf diesen Beitrag antworten »

RE: Induktionsbeweis und n!..
@ Susi

Ob man von n auf n+1 oder n-1 auf n schließt ist egal. Das Prinzip der Vollständigen Induktion ist wie ähnlich einer "Dominosteinkette".

Mit dem IA zeigt Du dass es Dominostein(e) gibt

Mit em Induktionsschluss zeigst Du, dass wenn man einen Umschmeist auch der nächste fällt. Ob man nun n-1, oder n umschubst, ist egal.

25.10.2006, 19:32

Susi1987

Auf diesen Beitrag antworten »

RE: Induktionsbeweis und n!..
Danke für die Antworten. Und NEIN es muss nicht unbedingt Ind. Beweis sein. Man soll "geschickt2 beweisen, also ist denke mal dein Vorschlag gemeint.

Zitat:

Original von therisen
$\begin{eqnarray*} (x+y)^n = \sum_{k=0}^n {n \choose k} x^ky^{n-k} \end{eqnarray*}$ .
Wegen $\begin{eqnarray*} (-1)^k2^k = (-2)^k \end{eqnarray*}$ genügt es also, $\begin{eqnarray*} x=-2 \end{eqnarray*}$ und $\begin{eqnarray*} y=1 \end{eqnarray*}$ zu setzen.

Gruß, therisen

Leuchtet ein,
geht das auch beim 2.? N bissl umformen? Oder ist das nicht möglich?

Und was wollen die bei Aufgabe 3 Überhaupt?

25.10.2006, 19:41

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktionsbeweis und n!..
Also bei Aufgabe 2 sehe ich auf Anhieb keine geschickte Umformung.

Und bei Aufgabe 3 sollst du eben zeigen, daß die Anzahl k-elementiger Teilmengen aus einer Menge mit n Elementen $\begin{eqnarray*} n\choose k \end{eqnarray*}$ ist.

25.10.2006, 20:04

therisen

Auf diesen Beitrag antworten »

Bei 3b) überlege dir, wie du $\begin{eqnarray*} \sum_{k=0}^n {n \choose k} \end{eqnarray*}$ berechnen kannst - "vielleicht" gibt's da ja wieder einen direkten Weg Augenzwinkern

26.10.2006, 16:13

Susi1987

Auf diesen Beitrag antworten »

thx für die antworten - thema hat sich erledigt.

zu 3b) muss man den binomischen satz benutzen, 1 einsetzen und dann kommt 2^n raus, falls es wen interessiert.

2 is ziemlich schwer - 3a hab ich per induktionsbeweis gemacht - mal sehen obs stimmt - danköö

03.11.2006, 22:07

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktionsbeweis und n!..

Zitat:

Original von Susi1987
2. n € N0
$\begin{eqnarray*} \sum_{k=0}^n~\frac{(-1)^{k}}{k+1}\begin{pmatrix} n \\ k \end{pmatrix}=\frac{1}{n+1} \end{eqnarray*}$

Hat etwas gedauert, aber jetzt habe ich die Lösung.
Also mit vollständiger Induktion kommt man da nicht weit. (Jedenfalls habe ich da keine Lösung gefunden). Aber hier hilft die Funktion $\begin{eqnarray*} f(x) = (1-x)^n \end{eqnarray*}$ . Integriere diese von 0 bis 1. Dann wendest du auf die Funktion den binomischen Lehrsatz an. Das Ergebnis davon kannst du auch von 0 bis 1 integrieren. Augenzwinkern

Neue Frage »

Antworten »

Induktionsbeweis und n!..

Verwandte Themen