vollständige Induktion Binomia < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie für alle $ n [mm] \in \IN [/mm] $ das folgendes gilt:
$ [mm] \vektor{n \\ 0} [/mm] + [mm] \vektor{n \\ 2} [/mm] + ... = [mm] \vektor{n \\ 1} [/mm] + [mm] \vektor{n \\ 3} [/mm] + ... $ |
Hallo,
ich brauche ein Idee für den Induktionsschritt.
Ich habe immer das Gefühl, dass sich bei allem was ich ausprobiere, ich die Induktionsverraussetzung nicht benutze.
Induktionsschritt
1 Fall n gerade $ [mm] \Rightarrow [/mm] $ n + 1 ungerade
$ [mm] \vektor{n +1 \\ 0} [/mm] + [mm] \vektor{n +1 \\ 2} [/mm] + ... + [mm] \vektor{n +1\\ n} [/mm] = [mm] \vektor{n +1 \\ n+1 -n} [/mm] + [mm] \vektor{n +1 \\ n+1 - (n - 2)} [/mm] + ... + [mm] \vektor{n +1 \\ n+1 - 0} [/mm] = [mm] \vektor{n +1 \\ 1} [/mm] + [mm] \vektor{n +1 \\ 3} [/mm] + ... + [mm] \vektor{n+1 \\ n+1 } [/mm] $ .
In diesen Fall habe ich einfach nur $ [mm] \vektor{ n \\ k } [/mm] = [mm] \vektor{ n \\ n-k } [/mm] $ verwendet, aber bei n ungrade verzweifel ich.
Danke freshstyle
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:26 Mi 13.08.2008 | | Autor: | statler |
Hi!
> Zeigen Sie für alle [mm]n \in \IN[/mm] das folgendes gilt:
> [mm]\vektor{n \\ 0} + \vektor{n \\ 2} + ... = \vektor{n \\ 1} + \vektor{n \\ 3} + ...[/mm]
>
> ich brauche ein Idee für den Induktionsschritt.
> Ich habe immer das Gefühl, dass sich bei allem was ich
> ausprobiere, ich die Induktionsverraussetzung nicht
> benutze.
Muß das Induktion sein? Kennst du die Formel für [mm] (a+b)^{n} [/mm] und darfst du sie benutzen? Wenn ja, berechne mal [mm] (1+(-1))^{n}.
[/mm]
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:19 Do 14.08.2008 | | Autor: | freshstyle |
Aber bei $ (1 + [mm] (-1))^n [/mm] $ wende ich den Binomianalsatz an , $ ... = 0 $ , dann schmeiße ich die koeffizienten mit einen minus vorbehaftet für und habe die Gleichheit stehen. Weil $ (1 + [mm] (-1))^n \forall [/mm] n [mm] \in \IN [/mm] $ gilt.
Aber ich habe noch nicht verstanden wo ich die I.V einsetze.
Danke freshstyle
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:37 Do 14.08.2008 | | Autor: | Somebody |
> Aber bei [mm](1 + (-1))^n[/mm] wende ich den Binomianalsatz an , [mm]... = 0[/mm]
> , dann schmeiße ich die koeffizienten mit einen minus
> vorbehaftet für und habe die Gleichheit stehen. Weil [mm](1 + (-1))^n \forall n \in \IN[/mm]
> gilt.
> Aber ich habe noch nicht verstanden wo ich die I.V
> einsetze.
Die brauchst Du gar nicht, denn wie Dieter angedeutet hatte, geht es auf diesem Weg ganz bequem auch ohne Induktion:
[mm]\big(1+(-1)\big)^n=\sum\limits_{k=0}^n\binom{n}{k}(-1)^k=0\Rightarrow \sum\limits_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}=\sum\limits_{k=0}^{\lfloor (n-1)/2\rfloor}\binom{n}{2k+1}[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:50 Do 14.08.2008 | | Autor: | freshstyle |
Aber wir sollen das per Induktion machen , deshalb.
MFG freshstyle
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:07 Do 14.08.2008 | | Autor: | Somebody |
> Aber wir sollen das per Induktion machen , deshalb.
Ok, dann würde ich die Sache so ansetzen: die Summe [mm] $G_n=\binom{n}{0}+\binom{n}{2}+\cdots$ [/mm] ist die Anzahl Teilmengen einer $n$-elementigen Menge die eine gerade Anzahl Elemente besitzen und die Summe [mm] $U_n=\binom{n}{1}+\binom{n}{3}+\cdots$ [/mm] ist die Anzahl ihrer Teilmengen die eine ungerade Anzahl Elemente besitzen.
Die zu beweisende Behauptung lautet in dieser Formulierung also: für [mm] $n\geq [/mm] 1$ hat eine (endliche) Menge gleich viele Teilmengen mit gerader Anzahl von Elementen wie Teilmengen mit ungerader Anzahl von Elementen. Kurz: [mm] $G_n=U_n$
[/mm]
Beweis (induktiv):
Induktionsanfang: ist $n=1$, dann ist [mm] $G_n=\binom{1}{0}=1$ [/mm] und [mm] $U_n=\binom{1}{1}=1$, [/mm] die Behauptung gilt in diesem Fall.
Induktionsschritt: Es ist [mm] $G_{n+1}=\blue{G_n}+\red{U_n}$ [/mm] und [mm] $U_{n+1}=\blue{U_n}+\red{G_n}$ [/mm] (weshalb? - überleg mal, was geschieht, wenn man ein $n+1$-tes Element dazunimmt: blau markiert die geraden/ungeraden Teilmengen, die schon bei der $n$-elementigen Menge vorhanden waren, rot markiert, diejenigen die neu dazukommen, die also insbesondere das hinzugekommene $n+1$-te Element enthalten - und somit vorher nicht schon gezählt worden sind). Da nach Voraussetzung [mm] $G_n=U_n$ [/mm] ist, folgt [mm] $G_{n+1}=U_{n+1}$.
[/mm]
Bem: Du kannst dies, unter Verwendung der Beziehung [mm] $\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}$ [/mm] auch etwas formaler zeigen:
[mm]G_{n+1}=\green{\binom{n+1}{0}}+\blue{\binom{n+1}{2}}+\red{\binom{n+1}{4}}+\cdots=\green{\binom{n}{0}}+\blue{\binom{n}{1}+\binom{n}{2}}+\red{\binom{n}{3}+\binom{n}{4}}+\cdots=G_n+U_n[/mm]
und
[mm]U_{n+1}=\green{\binom{n+1}{1}}+\blue{\binom{n+1}{3}}+\red{\binom{n+1}{5}}+\cdots=\green{\binom{n}{0}+\binom{n}{1}}+\blue{\binom{n}{2}+\binom{n}{3}}+\red{\binom{n}{4}+\binom{n}{5}}+\cdots=G_n+U_n[/mm]
Induktionsschluss: für alle [mm] $n\geq [/mm] 1$ gilt [mm] $G_n=U_n$ [/mm] (Anzahl der Teilmengen mit gerader Anzahl Elemente ist gleich Anzahl der Teilmengen mit ungerader Anzahl Elemente).
|
|
|
|
