Beweis einer Analysis Aufgabe
Sonne300459
ich bin eine studentin im ersten semester, lehramt berufschule. wir müssen jede
woche 4 aufgaben bearbeiten und abgeben. leider steht zu einer aufgabe nichts
im script oder in meinem mathebuch. deshalb würde ich mich freuen, wenn mir ein
mathe genie sagen könnte, wie ich an die aufgabe ran gehe. ich möchte keine
komplette lösung, aber der ansatz wäre echt super. denn die studenten, die ich
fragte konnten mir nicht weiter helfen.
also hier die aufgabe:
Es sei [n] := {1,2,...,n} für n element von N (natürliche zahlen) definiert.
Finden sie formeln für
G(n) := # {M Teilmenge von [n] : # M gerade} bzw.
U(n) := # {M Teilmenge von [n] : # M ungerade}
Hinweis: G(n) + U(n) = 2^n
wie gesagt, ich komme überhaupt nicht mehr weiter und würde mich über eine
antwort freuen. ich muß die übung am montag abgeben.
BITTTTEEEEE !!!! :-)
bis bald
manon garcia
Paul Ebermann
>
> Es sei [n] := {1,2,...,n} für n element von N (natürliche zahlen) definiert.
> Finden sie formeln für
> G(n) := # {M Teilmenge von [n] : # M gerade} bzw.
> U(n) := # {M Teilmenge von [n] : # M ungerade}
>
> Hinweis: G(n) + U(n) = 2^n
>
> wie gesagt, ich komme überhaupt nicht mehr weiter und würde mich über eine
> antwort freuen. ich muß die übung am montag abgeben.
Du weißt, was du da finden/beweisen sollst?
Was hast du denn schon herausgefunden?
Wo bist du steckengeblieben?
Nach dem Hinweis genügt es, eine der beiden
Formeln zu finden, die andere ergibt sich dann
mit G(n) = 2^n - U(n) bzw. U(n) = 2^n - G(n).
Paul
Sonne300459
erstmal danke für die schnelle antwort.
ich habe die beiden formeln:
G(n) = 2n
U(n) = 2n -1
damit ergibt sich:
2n + 2n-1 = 2^n
aber ich weiß nicht, wie ich das beweisen soll. denn das wird ja nicht die
lösung sein, das wäre ja zu einfach oder?
manon
Paul Ebermann
>
> ich habe die beiden formeln:
>
> G(n) = 2n
> U(n) = 2n -1
Woher?
Geraten?
> damit ergibt sich:
>
> 2n + 2n-1 = 2^n
Bei mir ergibt das eher 4n - 1 -- und das ist
nicht einmal eine gerade Zahl, geschweige denn
eine Zweierpotenz.
> aber ich weiß nicht, wie ich das beweisen soll. denn das wird ja nicht die
> lösung sein, das wäre ja zu einfach oder?
Schreibe mal die Werte für ein paar kleine Mengen
auf. Beispiel:
n = 2: G(n) = # { {}, {1,2} } = 2
U(n) = # { {1}, {2} } = 2
2 + 2 = 4 = 2^2 = 2^n - stimmt.
n=3:
G(n) = #{ {}, {1,2}, {2,3}, {1,3} } = 4
U(n) = #{ {1}, {2}, {3}, {1,2,3} } = 4
4 + 4 = 8 = 2^3 = 2^n - stimmt.
n=4:
G(n) = #{ {}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3,4} }
= 8
U(n) = #{ {1}, {2}, {3}, {4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4} }
= 8
8 + 8 = 16 = 2^4 = 2^n - stimmt.
Na - hast du jetzt einen Verdacht, wie die
allgemeine Formel lauten könnte?
Und eine Idee, wie man das beweisen könnte?
Paul
--
Im deutschen Usenet ist es üblich, seinen Realnamen (Vor- + Nachname)
anzugeben. Mehr dazu in den regelmäßigen Postings in de.newusers.infos.
Rainer Rosenthal
> ich bin eine studentin im ersten semester... wenn mir ein
> mathe genie sagen könnte,
>
Hallo Manon,
leider habe ich heute erfahren, dass ich keine Chance habe, die
Fields Medaillie zu erringen, aber für die angegebene Frage
sollte ich doch was finden können.
Es ist ein Grundproblem bei Deiner Frage, das immer wieder
vorkommt und deshalb auch immer wieder angesprochen werden
muss: Wenn Du eine Aufgabe im Wortlaut nennst, ist das zwar gut,
weil man dann Missverständnisse ausräumen kann. Wenn Du aber
GARNICHTS weiter hast als diesen Wortlaut und den Termin, zu dem
Du den Krempel abgeben musst, dann ist echtes Helfen unmöglich.
Ich weiss ja nicht einmal, ob Du mit der Schreibweise #{...} vertraut
bist, weil ich keinen Ansatz habe lesen können.
> Es sei [n] := {1,2,...,n} für n element von N (natürliche zahlen)
definiert.
> Finden sie formeln für
> G(n) := # {M Teilmenge von [n] : # M gerade} bzw.
> U(n) := # {M Teilmenge von [n] : # M ungerade}
>
> Hinweis: G(n) + U(n) = 2^n
Wenn ich diesen Formelkram mal kurz zusammenfassen darf, dann sehe
ich, dass zum einen die Kurzschreibweise [n] eingeführt wurde, mit der
die Menge aller natürlichen Zahlen von 1 bis n bezeichnet wird. OK.
Dann polke ich das Folgende von innen auf und sehe " # M gerade ".
Dies heisst: "Menge M hat eine gerade Anzahl von Elementen".
Dies Gebilde { M Teilmenge von [n]: # M gerade } ist eine etwas an-
spruchsvollere Menge. Ihre Elemente sind selbst Mengen.
Beispiel: n = 3 [3] = {1,2,3} hat folgende Teilmengen:
{ }, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}
Das sind 8 Stück, also 8 = 2^3 = 2^n (siehe "Hinweis")
Diejenigen M darunter, die eine gerade Anzahl #M haben,
bilden die "anspruchsvolle Menge":
{ { }, {1,2}, {1,3}, {1,4} }
Weiter mit dem Aufdröseln der Aufgabe:
Mit G(n) wird also die Anzahl der anspruchsvollen Menge bezeichnet.
Im genannten Beispiel also G(3) = 4.
Mit U(n) wird die Anzahl einer ähnlich komplizierten Menge bezeichnet.
Nämlich die der Menge, in der die Teilmengen mit ungerader Anzahl
versammelt sind. Im Beispiel: U(3) = #{ {1}, {2}, {3}, {1,2,3} } = 4.
Die im Hinweis gegebene Beziehung stimmt: 4 + 4 = 8.
>
> wie gesagt, ich komme überhaupt nicht mehr weiter und würde mich über eine
> antwort freuen. ich muß die übung am montag abgeben.
>
> BITTTTEEEEE !!!! :-)
JAISJAGUUUT, aber jetzt solltest Du doch erst mal selber was sagen,
sonst ist ja von "Übung" keine Rede.
Es scheint ja wohl darauf hinauszulaufen, dass Du angeben sollst, wieviele
der insgesamt 2^n Teilmengen von [n] nun gerade Anzahl haben und wie-
viele ungerade Anzahl.
Dazu fällt mir momentan nicht viel ein, ich würde mal auf Halbe-Halbe
tippen. Aber jetzt male Dir am besten selbst ein paar Beispiele.
Übrigens: Wirklich wichtig und gut zu wissen ist, dass es tatsächlich 2^n
Teilmengen in einer n-elementigen Menge gibt. (Die leere Menge { } natürlich
mitgezählt !) Klarmachen kann man sich das, indem man jede Menge einzeln
"antreten" lässt und dann alle Elemente fragt, ob sie dazu gehören. Das gibt
dann jedesmal eine Folge von Ja-Nein-Antworten, die man auch als 0-1-Folgen
interpretieren kann.
Hier auch wieder am obigen Beispiel (n=3) gezeigt:
{ } 000 (alle rufen "Nein")
{1} 001 (Von rechts her zu lesen, ist bei Binärzahlen üblich :-)
{2} 010 ( 1 sagt "Nein", 2 sagt "Ja", 3 sagt "Nein")
{1,2} 011 ( 1 sagt "Ja", 2 sagt "Ja", 3 sagt "Nein")
{3} 100 ( 1 sagt "Nein", 2 sagt "Nein", 3 sagt "Ja")
{1,3} 101 ( 1 sagt "Ja", 2 sagt "Nein", 3 sagt "Ja")
{2,3} 110 (1 ruft "Nein", die beiden anderen: "Ja")
{1,2,3} 111 (Alle rufen "Ja")
Bitte beachte, dass ich die 2^3 = 8 Möglichkeiten so aufgeschrieben
habe, dass sie die Binärzahlen 0 bis 7 in aufsteigender Reihenfolge
darstellen. Es kann nicht schaden, dass ich diesen Zusammenhang
hier gleich mit dargestellt habe, auch wenn Du es jetzt nicht direkt
für die Aufgabe benötigst.
Herzlichen Gruss und toi-toi-toi
Rainer Rosenthal
r.ros...@web.de
Paul Ebermann
> Fields Medaillie zu erringen, aber für die angegebene Frage
> sollte ich doch was finden können.
Hast du die Altersgrenze überschritten?
Dann herzlichen Glückwunsch zum Geburtstag!
Sonst: Warum meinst du, sie nicht erringen zu können?
Paul
Rainer Rosenthal
Paul Ebermann <Paul-E...@gmx.de> wrote
Wieso ICH ? Genau genommen hat auch J.B. nicht ausdrücklich
gesagt, dass ich sie nicht mehr bekommen könnte. Allerdings
nicht für den heutigen Beitrag, in dem ich erstmals seit langem
ein paar Klammern fehlerfrei aufzulösen imstande war :-)
Mit dem Geburtstagsglückwunsch bitte noch bis zum 25. April warten !
Gruss,
Rainer
Hermann Kremer
>hallo ihr,
Hallo Manon,
[ ... ]
>Hinweis: G(n) + U(n) = 2^n
Ein Tip: Denke mal an die Binomialkoeffizienten "n über k", und wie
die kombinatorisch definiert sind: ... Anzahl aller Kombinationen mit ... aus ...
Und dann gab es da noch die hübsche binomische Formel (1 + 1)^n = 2^n ...
Grüße
Hermann
--
Hermann Kremer
>Paul Ebermann <Paul-E...@gmx.de> wrote
Hallo Rainer,
>Mit dem Geburtstagsglückwunsch bitte noch bis zum 25. April warten !
... aber vorher
http://www-history.mcs.st-and.ac.uk/~history/Day_files/Day425.html
lesen - Du befindest Dich in sehr guter Gesellschaft, u.a. auch mit dem
Autor des "Erlanger Programms [einer einheitlichen Geometrie]" ;-))
Grüße
Hermann
--
>
>Gruss,
>Rainer
>
>
Sonne300459
stimmt, beim nächsten mal werde ich genau schreiben, wo ich ein problem habe
oder was ich verstanden habe.
du hast recht, ich hatte mit der schreibweise probleme. deshalb hatte ich auch
keinen ansatz hingeschrieben.
eure überlegungen haben mir sehr geholfen, um zu sehen, wie man an solch eine
aufgabe ran geht. erstmal bis ins detail auseinander nehmen und erklären.
zu deiner ausführung habe ich noch eine frage:
>Beispiel: n = 3 [3] = {1,2,3} hat folgende Teilmengen:
> { }, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}
> Das sind 8 Stück, also 8 = 2^3 = 2^n (siehe "Hinweis")
das sind jetzt also alle teilmengen, die es gibt. die muß ich jetzt aufteilen
auf G(n) und U(n). soweit verstanden.
>Nämlich die der Menge, in der die Teilmengen mit ungerader Anzahl
>versammelt sind. Im Beispiel: U(3) = #{ {1}, {2}, {3}, {1,2,3} } = 4.
warum hast du jetzt die obigen teilmengen der ungeraden anzahl zu geordnet?
ich hatte die aufgabe so verstanden, dass ich die geraden zahlen bzw. ungeraden
zahlen in einer formel darstellen sollte. aber wenn ich euch richtig verstanden
habe, dann wird hier die ungerade anzahl und die gerade anzahl gesucht. heißt
das mit anderen worten, es wird die anzahl aller ungeraden zahlen gesucht oder
bin ich immer noch verkehrt?
ich möchte euch danken, denn ich habe schon sehr viel gelernt bei euch. ich
werde mich auch bemühen, dass die nächsten fragestellungen etwas
anspruchsvoller werden.
darf man fragen, ob ihr studiert und wenn ja wo oder was ihr sonst macht, dass
ihr armen studis aus der klemme helft und dazu bringt mathe richtig zu
verstehen? finde ich super!
manon garcia
Sonne300459
>> ich habe die beiden formeln:
>>
>> G(n) = 2n
>> U(n) = 2n -1
ich habe die aufgabe völlig falsch verstanden, wie ich mittlerweile mitbekommen
habe. ich dachte es sollte nur eine formel gefunden werden für ungerade bzw.
gerade zahlen. aber da war ich völlig auf dem holzweg.
>n = 2: G(n) = # { {}, {1,2} } = 2
> U(n) = # { {1}, {2} } = 2
>
kannst du mir erklären, warum die die teilmengen G und U zugeordnet hast?
welche erklärung steht dahinter? das es die 4 teilmengen gibt, verstehe ich,
aber die aufteilung kann ich noch nicht nach vollziehen. ich hoffe, wenn ich
deine aussagen verstehe, dass ich dann die aufgabe wohl auch richtig verstehe.
>Na - hast du jetzt einen Verdacht, wie die
>allgemeine Formel lauten könnte?
>Und eine Idee, wie man das beweisen könnte?
>
ich hoffe, das ich die allg. formel und den beweis dir sagen kann, wenn du mir
die frage von oben erklären kannst.
ich finde es toll, dass du mir soviel hilfst. denn ich mag mathe sehr und bin
etwas überrascht, dass es kein buch gibt, in dem man die fragestellungen, die
sich ergeben, wenn man sich erst kurz mit der materie beschäftigt. aber du
hilfst mir sehr weiter. denn ich habe schon eine menge von dir gelernt.
kennst du zufällig ein buch, welches man einem studi im ersten semester
empfiehlt? ich habe momentan das königsberger - analysis I, aber dort steht mir
zuwenig erklärung. vielleicht weißt du oder jemand anders ein buch?
manon garcia
Rainer Rosenthal
Sonne300459 <sonne...@aol.com>
> zu deiner ausführung habe ich noch eine frage:
> >Beispiel: n = 3 [3] = {1,2,3} hat folgende Teilmengen:
> > { }, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}
> > Das sind 8 Stück, also 8 = 2^3 = 2^n
> das sind jetzt also alle teilmengen, die es gibt. die muß ich jetzt
> aufteilen auf G(n) und U(n). soweit verstanden.
Hallo Manon,
eventuell hast Du es inzwischen verstanden, weil Du ja jetzt richtig
in die Vollen gehst und Dich mit der Sache auseinandersetzst.
Aber so wie es da steht, bezweifle ich es erst mal - ohne Dir damit
Böses zu wollen :-)
Es ist richtig, dass es darum geht, etwas aufzuteilen.
Aufgeteilt wird: die Menge aller Teilmengen von [n].
Sowas ist durchaus unüblich im Tagesgeschäft. Und es ist durchaus
üblich im mathematischen Geschäft. Das muss erst mal verdaut werden.
Unter den Teilmengen von [n] gibt es solche mit einer geraden Anzahl
von Elementen. Ist M eien solche Teilmenge und hat sie eine gerade
Anzahl, dann wird hier in Deinem Übungsblatt geschrieben: " # M ist gerade".
Das ist was VÖLLIG anderes als "M enthält nur gerade Zahlen".
Weiter zu dem G(n) und U(n): Das sind KEINE Mengen sondern Zahlen.
Denn in der Definition steht G(n) = # { ..... }, G(n) ist also eine ANZAHL.
Ebenso ist U(n) eine Zahl, nämlich die Anzahl der Teilmengen von [n],
die 1 Element oder 3 Elemente oder 5 Elemente ... kurz gesagt eine
ungerade Anzahl von Elementen haben.
Wie Du richtig schreibst, findet also eine Aufteilung aller Mengen statt,
wobei links die mit gerader Anzahl kommen und rechts die mit ungerader,
wenn ich das mal bildlich ausdrücken darf.
Dann zählt man, was sich links gesammelt hat; das ergibt G(n).
Und dann zählt man, wieviele Mengen rechts herumliegen; das ergibt U(n).
>
> >Nämlich die der Menge, in der die Teilmengen mit ungerader Anzahl
> >versammelt sind. Im Beispiel: U(3) = #{ {1}, {2}, {3}, {1,2,3} } = 4.
>
> warum hast du jetzt die obigen teilmengen der ungeraden anzahl zu
geordnet?
Das wird hoffentlich klarer durch meine eben gegebene Erklärung.
>
> ich hatte die aufgabe so verstanden, dass ich die geraden zahlen bzw.
> ungeraden zahlen in einer formel darstellen sollte. aber wenn ich euch
> richtig verstanden habe, dann wird hier die ungerade anzahl und die
> gerade anzahl gesucht. heißt das mit anderen worten, es wird die anzahl
> aller ungeraden zahlen gesucht oder bin ich immer noch verkehrt?
Auch dazu habe ich oben schon was gesagt:
.... Das ist was VÖLLIG anderes als "M enthält nur gerade Zahlen" ....
Du befindest Dich hier in einem Prozess der Gehirnwäsche :-) Es ist sehr
hilfreich, die einzelnen Flecken sorgfältig zu behandeln, aber es muss auch
immer wieder das gesamte Gewebe ins Wasser getaucht, geschwenkt und
ausgewrungen werden.
Will heissen: Du solltest die bisherigen Postings ruhig mehrfach durchgehen,
so dass sich ein zusammenhängendes Bild für Dich ergibt. Wenn dann
wieder eine "unsaubere Stelle" auftaucht, dann besteht schon eine starke
Wahrscheinlichkeit, dass Du sie selbst "bereinigt" bekommst. Allein dadurch,
dass Du keine zittrigen Hände mehr hast und Dir die Seife nicht mehr aus-
glitscht :-)
Wenn doch - Poblem möglichst genau einkreisen und nochmal Frage posten.
> ich möchte euch danken, denn ich habe schon sehr viel gelernt bei euch.
> ich werde mich auch bemühen, dass die nächsten fragestellungen etwas
> anspruchsvoller werden.
Nein, nein - "anspruchsvoller" ist nicht erwünscht. "Ehrlich" ist gefordert.
Ganz ohne moralischen Beigeschmack. Nicht das Ausschmücken von
irgendwelchen Formeln ist ja das Ziel sondern die Zerlegung in einzelne
wohlverstandene Teile, deren Zusammenwirken dann auch wieder
verständlich ist.
>
> darf man fragen, ob ihr studiert und wenn ja wo oder was ihr sonst macht,
> dass ihr armen studis aus der klemme helft und dazu bringt mathe richtig
> zu verstehen? finde ich super!
Das Studium habe ich seit vielen vielen Jahren hinter mir. Es hat mir selbst
viel Freude gemacht.
Dann heisst Du Manon (oder nennst Dich zumindest so :-), was ein schöner
Name ist und hast so eine fröhliche Adresse "Sonne..." und dann
hast Du geschrieben, dass Du selbst Lehrerin werden möchtest. Da ist es ja
sogar schon im Interesse Deiner zukünftigen Schüler, dass Du eine
Einstellung zum Mathematik-Lernen hast, die nicht NUR durch Spass geprägt
ist, sondern auch in aller Ruhe weiterführt, wenn man mal "im Dunkeln"
steht.
Ja so ist das. Und dann freut es immer riesig, wenn der oder die Fragende
echt mitmacht. Dann kannst Du durch Bildschirm und Tastatur hindurch merken,
wie es am anderen Ende "AHA" macht.
Herzlichen Gruss
Rainer Rosenthal
r.ros...@web.de
Sonne300459
ja, jetzt habe ich es endlich verstanden. meine fragen wurden richtig super
toll erklärt. ja, das problem ist momentan für mich wirklich, das zu
verarbeiten, was wir derzeit vorgesetzt bekommen. da muß ich mich erst so
richtig rein denken.
aber wenn man bei euch hier die fragen, die man hat, stellen kann und sie immer
so toll erklärt werden, dann werde ich sicherlich bald hinter das geheimnis der
höheren mathematik kommen! :-)
ich heiße manon. man soll doch bei newsgroups immer seinen richtigen namen
angeben.
ich werde mir jetzt mal gedanken machen, wie ich das beweisen kann. denn das es
so sein muß, habe ich verstanden. jetzt muß mir nur noch die formel her! ich
werde euch berichten, ob ich es bis heute abend geschafft habe oder ob ich noch
eine frage stellen muß.
bis bald
manon
Sonne300459
ich habe mir die aufgabe und eure postings mehrmals durchgelesen und habe die
aufgabenstellung verstanden.
ich habe jetzt durch mein script heraus gefunden, dass (1+1)^n = 2^n ist. habe
das bei mir auch ausprobiert. es kommt hin. ebenso kann ich es mit
binominalkoeffizienten schreiben.
n= 3:
"3 über 0" + "3 über 1" + "3 über 2" + " 3 über 3", das habe ich auch
nachgerechnet und den wert 8 heraus bekommen.
aber das ist ja nicht die formel, die allg. gültig ist. ich habe nicht für G(n)
und für U(n) jeweils eine formel, sondern nur für G(n) + U(n).
>n=3:
>4 + 4 = 8 = 2^3 = 2^n - stimmt.
>
>n=4:
>8 + 8 = 16 = 2^4 = 2^n - stimmt.
>
ich hätte da folgende idee:
für G(n):= 2^(n-1)
für U(n):= 2^(n-1)
nun eine frage zum beweis:
a) welche von den beiden formeln sollte ich verwenden? (1-1)^n oder 2^(n-1)
b) wie beweise ich das? soll ich dann einfach G(n) in die Formel einsetzen?
U(n) + G (n) = 2^n --> umstellen nach U(n)
U(n) = 2^n - G(n) --> G(n) einsetzen
U(n) = 2^n - 2^(n-1)
U(n) = 2^n - 2^n * 2^(-1) --> 2^n ausklammern
U(n) = 2^n * ( 1 - 2^(-1))
U(n) = 2^n * ( 1 - 1 / 2^1)
U(n) = 2^n * 1/2
==> damit hätte ich U(n) berechnet, aber habe ich es damit auch bewiesen?
Frage:
die vollständige Induktion wird die eigentlich nur bei summen hergenommen zum
beweisen? oder kann man die auch bei anderen aussagen verwenden?
bis bald
manon garcia
Rainer Rosenthal
Sonne300459 <sonne...@aol.com>
>
> ich habe mir die aufgabe und eure postings mehrmals
> durchgelesen und habe die aufgabenstellung verstanden.
>
> ich habe jetzt durch mein script heraus gefunden, dass
> (1+1)^n = 2^n ist. habe das bei mir auch ausprobiert.
> es kommt hin. ebenso kann ich es mit binominalkoeffizienten
> schreiben.
Hallo Manon,
das hat doch was!
>
> n= 3:
> "3 über 0" + "3 über 1" + "3 über 2" + " 3 über 3", das habe ich
> auch nachgerechnet und den wert 8 heraus bekommen.
>
> aber das ist ja nicht die formel, die allg. gültig ist. ich habe nicht
> für G(n) und für U(n) jeweils eine formel, sondern nur für G(n) + U(n).
>
Genau. Du weisst nun, dass es z.B. 2^10 = 1024 Teilmengen einer
10-elementigen Menge gibt. Fast nicht zu glauben, oder ? Bloss
10 Elemente und dann derart viele Teilmengen ...
Wie Du richtig festgestellt hast, hast Du damit aber die Anzahl aller
Teilmengen. Gefragt war aber nach der Anzahl der Teilmengen mit
gerader Anzahl. Dass auch nach der mit ungerader Anzahl gefragt
war, ist ja dann leicht zu beantworten: Der Rest sind die Mengen mit
ungerader Elementeanzahl.
> >n=3:
> >4 + 4 = 8 = 2^3 = 2^n - stimmt.
> >
> >n=4:
> >8 + 8 = 16 = 2^4 = 2^n - stimmt.
> >
>
> ich hätte da folgende idee:
> für G(n):= 2^(n-1)
> für U(n):= 2^(n-1)
Dies läuft darauf hinaus, dass Du sagst: Halbe-Halbe.
Denn es ist ja 2^(n-1) = (2^n) / 2.
Das ist aber doch nur eine Vermutung, oder ?
>
> nun eine frage zum beweis:
> a) welche von den beiden formeln sollte ich verwenden? (1-1)^n oder
2^(n-1)
Hier ist entweder ein Schreibfehler oder ein fürchterlicher "Fleck" :-)
Denn (1-1)^n ist ja nix weiter (wegen 1-1 = 0) als 0^n = 0.
Die folgende Rechnung ist zwar ausführlich und aufschlussreich, geht
aber sozusagen "am Thema vorbei". Du arbeitest da kräftig mit durchaus
zulässigen Umformungen, die aber nicht wirklich etwas bringen, wie ich
gleich zeigen werde.
>
> b) wie beweise ich das? soll ich dann einfach G(n) in die Formel
einsetzen?
> U(n) + G (n) = 2^n --> umstellen nach U(n)
> U(n) = 2^n - G(n) --> G(n) einsetzen
> U(n) = 2^n - 2^(n-1)
> U(n) = 2^n - 2^n * 2^(-1) --> 2^n ausklammern
> U(n) = 2^n * ( 1 - 2^(-1))
> U(n) = 2^n * ( 1 - 1 / 2^1)
> U(n) = 2^n * 1/2
>
> ==> damit hätte ich U(n) berechnet, aber habe ich es damit auch bewiesen?
Nein, denn Du bist von der (unbewiesenen) Voraussetzung ausgegangen, dass
G(n) halb so gross ist wie die Anzahl 2^n aller Teilmengen von[n]. Und
gelandet bist Du bei dem Ergebnis, dass dann U(n) die Hälfte von 2^n ist.
Kein grosser Fortschritt, wenn man bedankt, dass Du ja schon vorher
wusstest, dass gilt: G(n) + U(n) = 2^n.
Was fehlt ?
Betrachte die Formel 2^n = (n über 0) + (n über 1) + ... + (n über n)
und erinnere Dich an die Begründung.
(n über m) ist die Anzahl der Teilmengen von [n] mit m Elementen.
Die Summe zählt zusammen die Anzahl der Teilmengen mit 0, 1, 2, 3, ...
Elementen.
G(n) ist aber die Anzahl der Teilmengen mit 0, 2, 4, ... Elementen -
Dämmert was ? Sieht doch usu wie eben, bloss nicht soviele Summanden...
>
> Frage:
> die vollständige Induktion wird die eigentlich nur bei summen hergenommen
> zum beweisen? oder kann man die auch bei anderen aussagen verwenden?
Diese Frage sollten wir vertagen, bis die andere Geschichte wirklich
erledigt ist. OK ?
Gruss,
Rainer
Philipp Zumstein
Rainer Rosenthal <r.ros...@web.de> schrieb:
> Sonne300459 <sonne...@aol.com>
> > n= 3:
> > "3 über 0" + "3 über 1" + "3 über 2" + " 3 über 3", das habe ich
> > auch nachgerechnet und den wert 8 heraus bekommen.
Wenn ich das allgemein ausrechnen will bekomme ich eine Summe die
nicht "so" einfach auszurechnen ist, oder?
Bildlich gesprochen, heisst ja die Vermutung: Man wähle sich eine
Zeile im Pascal'schen Dreieck (nennen wir diese Zeile n) und addiere
mal nur die erste, dritte, fünfte, ... Zahl und dies ergibt 2^(n-1).
Die Summe aller Zahlen in der (n-1)-ten Zeile des Pascal'schen
Dreiecks ergibt 2^(n-1). Diese beiden Summen sind also gleich gross.
Dies ist aber klar, da im Pascal'schen Dreieck eine neue Zahl
berechnet werden kann, indem man in der oberen Reihe die beiden Zahlen
zusammenrechnet. [Man muss vielleicht noch beachten, dass 4 über 5
Null gibt o.ä.] Wenn man diese Idee etwas formal aufschreibt, sollte
man die Aufgabe lösen können. Ich hoffe, ich habe dir nicht die
Aufgabe verdorben; aber ich finde diese Aufgabe recht schwer.
Gruss
Philipp
Rainer Rosenthal
Philipp Zumstein <hzum...@bluewin.ch>
> Rainer Rosenthal <r.ros...@web.de> schrieb:
> > Sonne300459 <sonne...@aol.com>
> > > n= 3:
> > > "3 über 0" + "3 über 1" + "3 über 2" + " 3 über 3", das habe ich
> > > auch nachgerechnet und den wert 8 heraus bekommen.
>
> Wenn ich das allgemein ausrechnen will bekomme ich eine Summe die
> nicht "so" einfach auszurechnen ist, oder?
Hallo Philipp,
meine bisherigen Hilfestellungen für Manon waren eher allgemeiner
Art, wie z.B. "worum geht es ?", "wie weit bist Du schon ?" usw.
Und ich habe ohne eigenes Nachdenken lediglich darauf hingewiesen,
dass das, was sie bisher zum Thema G(n) und U(n) vorgebracht hat,
nicht wirklich eine Lösung sein kann.
Ich glaube das ist die "sokratische Methode" :-) Einfach hartnäckig
dranbleiben, wenn einer (oder eine) meint, etwas zu wissen "es aber
nicht weiss". Dass Halbe-Halbe die richtige Antwort sein könnte,
hatte ich bereits als meine Vermutung zu erkennen gegeben. Wenn wir
jetzt aber in einen Bereich kommen, in dem wir zum eigentlichen Thema
dieser Mathematik-Übung kommen, dann - um so besser. Und dann ist
ja jede Hilfe willkommen ! Ich gebe zu, dass ich mich da noch keinen
Fatz hineingedacht habe sondern sozusagen per Fernsteuerung erst
mal (zusammen mit Paul Ebermann) die Berührungsängste bei Manon
beseitigen geholfen habe. Wie aus ihren Antworten klar hervorgeht,
ist sie sehr gewissenhaft bei den Umformungen und es hapert(e) etwas
mit der Vorstellung von Mengen_von_Mengen, was ja nachvollziehbar ist.
>
> Bildlich gesprochen, heisst ja die Vermutung: Man wähle sich eine
> Zeile im Pascal'schen Dreieck (nennen wir diese Zeile n) und addiere
> mal nur die erste, dritte, fünfte, ... Zahl und dies ergibt 2^(n-1).
> Die Summe aller Zahlen in der (n-1)-ten Zeile des Pascal'schen
> Dreiecks ergibt 2^(n-1). Diese beiden Summen sind also gleich gross.
> Dies ist aber klar, da im Pascal'schen Dreieck eine neue Zahl
> berechnet werden kann, indem man in der oberen Reihe die beiden Zahlen
> zusammenrechnet. [Man muss vielleicht noch beachten, dass 4 über 5
> Null gibt o.ä.] Wenn man diese Idee etwas formal aufschreibt, sollte
> man die Aufgabe lösen können. Ich hoffe, ich habe dir nicht die
> Aufgabe verdorben; aber ich finde diese Aufgabe recht schwer.
>
Nee, nee, nix verdorben ! Es wird Manon nur gut tun, wenn sie erfährt, dass
sie da nicht an einer Popel-Aufgabe sitzt und ihre Zeit für nix
verschwendet.
Ich kann auch gerne leise weiterlesen, wenn es jetzt ins echt Mathematische
geht. ( Versprechen kann ich das natürlich nicht :-)
Mit freundlichem Gruss natürlich auch an Manon, die jetzt noch mehr zum
Lesen bekommen hat (Pascal'sches Dreieck - schööön)
Gruss,
Rainer
Manon garcia
ja, das stimmt ich habe meine eigene vermutung bewiesen. :-)
>(n über m) ist die Anzahl der Teilmengen von [n] mit m Elementen.
>G(n) ist aber die Anzahl der Teilmengen mit 0, 2, 4, ... Elementen
okay, dann werde ich die formel so umstellen, dass sie allgemein für G(n) bzw.
U(n) gilt.
für G(n):
= (n über 0) + (n über 2) + (n über 4) + ... + (n über 2n)
ist das soweit richtig? dann werde ich mir nochmal gedanken machen, wie ich
diese formel allgemeingültig halten kann.
ach, du hast phillip geschrieben, wenn es so richtig ins mathematische geht,
dann klinkst du dich ein, ... steht ich denn nicht kurz vor der lösung??? ;-)
bis gleich
manon
Rainer Rosenthal
Manon garcia <manon...@aol.com>
>
> ach, du hast phillip geschrieben, wenn es so
> richtig ins mathematische geht, dann klinkst du
> dich ein, ... steht ich denn nicht kurz vor der lösung??? ;-)
>
Hallo Manon,
ich glaube, dass Philipp ein wenig übertrieben hat. Zumindest
hoffe ich das für Dich :-)
Das Gemeine an Sackgassen ist, dass man da durchaus
dicht vor dem Ziel stehen kann und doch nicht hinkommt *g*.
Nicht dass Du jetzt in einer Sackgasse wärst - nein ganz gewiss
nicht. Aber bevor Du den Beweis nicht schwarz auf weiss hast,
musst Du jederzeit mit dem Schlimmsten rechnen.
Ich habe es gut, ich gehe jetzt für einige Stunden ausser Haus.
Mal sehen wie es Dir dann gegangen sein wird.
Daumen drückend
Rainer
Christian Stapfer
3be40...@news.bluewin.ch...
>
> Rainer Rosenthal <r.ros...@web.de> schrieb:
> > Sonne300459 <sonne...@aol.com>
> > > n= 3:
> > > "3 über 0" + "3 über 1" + "3 über 2" + " 3 über 3",
> > > das habe ich auch nachgerechnet und den wert 8
> > > heraus bekommen.
>
> Wenn ich das allgemein ausrechnen will bekomme
> ich eine Summe die nicht "so" einfach auszurechnen
> ist, oder?
>
> Bildlich gesprochen, heisst ja die Vermutung:
> Man wähle sich eine Zeile im Pascal'schen Dreieck
> (nennen wir diese Zeile n) und addiere mal nur
> die erste, dritte, fünfte, ... Zahl und dies
> ergibt 2^(n-1).
Man subtrahiere die Entwicklung von (1-1)^n von der
Entwicklung von (1+1)^n gemäss Binomialsatz: das
ergibt 2 * die Summe der Koeffizienten "n über (2*k + 1)"
= 2^n.
"Generatingfunctionology" - Du erinnerst Dich? Um
die erzeugende Funktion der formalen Potenzreihe zu
erhalten, die nur aus den *ungeraden* Termen besteht,
nimmst Du einfach den *ungeraden*Teil* der erzeugenden
Funktion dieser Potenzreihe: das wäre hier also
((1+x)^n-(1+(-x))^n)/2
und wenn Du nun x=1 einsetzt erhältst Du die gesuchte
Summe der Koeffizienten der ungeraden Terme:
\sum_{k=0}^n\binom{n}{2k+1}1^{2k+1} = 2^n/2 = 2^{n-1}
Gruss,
Christian
Manon garcia
ich habe die binomialentwicklung versucht allgemein zu schreiben. denn das ist
es ja, was ich herausfinden sollte oder?
also z.b. für n=4:
G(4) = (4 über 0) + (4 über 2) + ( 4 über 4)
allg: (n über n-n) + (n über n-n/2) + (n über n)
oder:
4! / (0! (4-0)! + 4! / (2! (4-2)! + 4! / (4! (4-4)!
allg: n! / (n-n)!(n-(n-n))! + n! / (n-n/2)! (n-(n-n/2)!) + n! / (n! (n-n)!)
jetzt müßte ich doch nur noch eine allgmein gültige formel schreiben für n = n
elemente oder? aber da komme ich momentan nicht mehr weiter. vielleicht kannst
du mir sagen, ob ich auf dem richtigen wege bin?
manon
Manon garcia
es gibt ja für die geraden zahlen folgende formel:
gerade: 2*n + 1
ungerade: 2 * n
>Binomialsatz: das
>ergibt 2 * die Summe der Koeffizienten "n über (2*k + 1)"
>= 2^n.
kann ich da auch allgemein schreiben:
G(n) = Summe (n über 2 * n) und
U(n) = Summe (n über 2 * n + 1)
habe ich dich richtig verstanden?
weiter schreibst du:
> ((1+x)^n-(1+(-x))^n)/2
>
>\sum_{k=0}^n\binom{n}{2k+1}1^{2k+1} = 2^n/2 = 2^{n-1} (für ungerade terme)
>
diesen schritt habe ich nicht verstanden. woher hast du diese formel
hergeleitet?
oder komme ich auch darauf, wenn ich meine obige formel ausmultipliziere?
bis bald
manon
Paul Ebermann
> > > Fields Medaillie zu erringen, aber für die angegebene Frage
> > > sollte ich doch was finden können.
> >
> > Hast du die Altersgrenze überschritten?
> > Dann herzlichen Glückwunsch zum Geburtstag!
> >
> > Sonst: Warum meinst du, sie nicht erringen zu können?
> >
> > Paul
>
> Wieso ICH ? Genau genommen hat auch J.B. nicht ausdrücklich
> gesagt, dass ich sie nicht mehr bekommen könnte. Allerdings
> nicht für den heutigen Beitrag, in dem ich erstmals seit langem
> ein paar Klammern fehlerfrei aufzulösen imstande war :-)
Den Beitrag von Janos habe ich erst ein paar Minuten
später gelesen. Dann habe ich mein Posting sofort
gecancelt, allerdings war das trotzdem zu spät - du hast
schon genatwortet.
Paul
Rainer Rosenthal
Manon garcia <manon...@aol.com> schrieb
>
> ich habe die binomialentwicklung versucht allgemein zu
> schreiben. denn das ist es ja, was ich herausfinden sollte oder?
>
Ja
> also z.b. für n=4:
>
> G(4) = (4 über 0) + (4 über 2) + ( 4 über 4)
>
> allg: (n über n-n) + (n über n-n/2) + (n über n)
Hallo Manon,
bin wieder da und habe gesehen, dass inzwischen schwere
Geschütze aufgefahren wurden. Nun ist wohl die Zeit der
freundlichen Sprüche vorbei und ich werde selber mitdenken
müssen - o je, dabei kann man leicht Fehler machen :-)
Was Du zu G(4) geschrieben hast, ist ein interessanter Ansatz (*),
der allerdings SO schon bei n=5 nicht mehr funktionieren wird :-(
für n=5 ist ja nicht bis zu (5 über 5) zu summieren, wenn man die
Mengen mit GERADER Anzahl zusammenzählt:
G(5) = (5 über 0) + (5 über 2) + (5 über 4) = 1 + 10 + 5 = 16
U(5) = (5 über 1) + (5 über 3) + (5 über 5) = 5 + 10 + 1 = 16
Hier bestätigt sich die Halb-Halbe-Vermutung und das von Christian
Stapfer angegebene Resultat. Aber ehrlich gesagt, blicke ich bei der
Begründung auch noch nicht durch. Werde mich aber anstrengen.
>
> oder:
> 4! / (0! (4-0)! + 4! / (2! (4-2)! + 4! / (4! (4-4)!
>
> allg: n! / (n-n)!(n-(n-n))! + n! / (n-n/2)! (n-(n-n/2)!) + n! / (n!
(n-n)!)
>
> jetzt müßte ich doch nur noch eine allgmein gültige formel schreiben für n
= n
> elemente oder? aber da komme ich momentan nicht mehr weiter. vielleicht
kannst
> du mir sagen, ob ich auf dem richtigen wege bin?
Öhhh, ähhh, nee eher nicht :-) Wo kommen denn da plötzlich diese
scheusslichen Fakultäten her ? Vielleicht ist auch bei Dir mal
"Kopf-Auslüften" und Spazierengehen angesagt ? Frische Luft
wirkt Wunder. Ich habe das vorhin selbst bemerkt und mein Posting
von heute morgen zu einem interessanten Thema gelöscht, weil
mir bei meiner Pause klar geworden war, dass da Mist drin stand.
Abstand MUSS auch sein, echt !
>
> manon
Gruss,
Rainer
(*) Du brauchst noch einige Übung mit der Formulierung von Summen
und Erkennen des richtigen Index. Nicht verzagen, weitermachen !
Die Folge 0, 2, 4 hast Du im Fall n=4 korrekt als n-n, n-n/2, n
aufschreiben können. Das Wörtchen "allgemein" dabei war aber
etwas geprahlt. Denn das ist eben nicht allgemein.
Manon garcia
ich glaube ich habe es geschafft!!!!!
ich habe jetzt folgende allgemein gültigen formeln:
G(n) = Summe k=0 bis n von (n über 2k)
U(n) = Summe k=0 bis n von (n über 2k +1)
das habe ich bis n=4 überprüft und es kam das richtige ergebnis heraus.
nun zum beweis:
hier kann ich doch schreiben
G(n) + U(n) = 2^n
Summe k=0 bis n von (n über 2k) + Summe k=0 bis n von (n über 2k+1) = 2^n
damit kann ich dann doch die vollständige induktion anwenden oder?
induktionsansatz: n=1
induktionsschluß: n -> n+1
das werde ich jetzt ausprobieren und dann hoffe ich, dass das selbe heraus
kommt!
ich sage schon mal danke an alle!!!!!!!!
bis bald
manon
Manon garcia
ich glaube ich habe es geschafft!!!!!
habe ich dein posting richtig verstanden?
ich habe jetzt folgende allgemein gültigen formeln:
G(n) = Summe k=0 bis n von (n über 2k)
U(n) = Summe k=0 bis n von (n über 2k +1)
das habe ich bis n=4 überprüft und es kam das richtige ergebnis heraus.
nun zum beweis:
hier kann ich doch schreiben
G(n) + U(n) = 2^n
Summe k=0 bis n von (n über 2k) + Summe k=0 bis n von (n über 2k+1) = 2^n
damit kann ich dann doch die vollständige induktion anwenden oder?
induktionsansatz: n=1
induktionsschluß: n -> n+1
das werde ich jetzt ausprobieren und dann hoffe ich, dass das selbe heraus
kommt!
bis bald
manon
Hermann Kremer
Ja, bist Du ... aber ich würde nicht mit n-n/2 usw. arbeiten - was passiert
denn, wenn n ungerade ist ?
Ich gebe Dir mal einen Tip (der wurde zwar schon mal geposted, den hast Du
aber wahrscheinlich übersehen ;-)
(1 + 1)^n = "n über 0" + "n über 1" + "n über 2" + ....
(1 - 1)^n = "n über 0" - "n über 1" + "n über 2" - ....
Siehst Du was ?
Addieren der beiden Gleichungen ergibt ...
Subtrahieren der beiden Gleichungen ergibt ...
Grüße
Hermann
--
>
>manon
Hermann Kremer
>hallo ihr,
Hallo Manon,
>ich glaube ich habe es geschafft!!!!!
Fein, prima ...
>ich habe jetzt folgende allgemein gültigen formeln:
>
> G(n) = Summe k=0 bis n von (n über 2k)
> U(n) = Summe k=0 bis n von (n über 2k +1)
Ja, OK
>das habe ich bis n=4 überprüft und es kam das richtige ergebnis heraus.
>
>nun zum beweis:
>hier kann ich doch schreiben
>
>G(n) + U(n) = 2^n
>Summe k=0 bis n von (n über 2k) + Summe k=0 bis n von (n über 2k+1) = 2^n
Ja
>damit kann ich dann doch die vollständige induktion anwenden oder?
>induktionsansatz: n = 1
>induktionsschluß: n -> n+1
>
>das werde ich jetzt ausprobieren und dann hoffe ich, dass das selbe heraus
>kommt!
OK, das müßte im Prinzip funktionieren, und Du solltest es ruhig mal
ausprobieren ... toi, toi, toi - aber es geht auch einfacher !!!
Hast Du mein Posting von 20:52 gelesen ?
Grüße
Hermann
--
Paul Ebermann
> es ja, was ich herausfinden sollte oder?
>
> also z.b. für n=4:
>
> G(4) = (4 über 0) + (4 über 2) + ( 4 über 4)
Die Anzahl der 0-Elementigen Teilmengen
+ die Anzahl der 2-elementigen Teilmengen
+ die Anzahl der 4-elementigen Teilmengen.
> allg: (n über n-n) + (n über n-n/2) + (n über n)
Nein - du musst bei n=6 ja etwa (6,0), (6,2),
(6,4), (6,6) addieren ( (x,y) soll hier für den
Binomialkoeffizienten x über y stehen).
> jetzt müßte ich doch nur noch eine allgmein gültige formel schreiben für n = n
> elemente oder? aber da komme ich momentan nicht mehr weiter. vielleicht kannst
> du mir sagen, ob ich auf dem richtigen wege bin?
Das könnte so lauten:
G(2n) = summe[k=0 .. n] (2n, 2k)
G(2n+1) = summe[k=0 .. n] (2n+1, 2k)
U(2n) = summe[k=0 .. n] (2n, 2k+1)
U(2n+1) = summe[k=0 .. n] (2n+1, 2k+1)
Dass das jetzt immer 2^(2n - 1) bzw. 2^(2n) ergibt,
müsstest du noch nachweisen.
HTH
Paul
Paul Ebermann
> aufgabenstellung verstanden.
Das ist schon einmal positiv.
> aber das ist ja nicht die formel, die allg. gültig ist. ich habe nicht für G(n)
> und für U(n) jeweils eine formel, sondern nur für G(n) + U(n).
Und die brauchst du nicht, weil sie ja eigentlich
schon vorgegeben ist.
> >n=3:
> >4 + 4 = 8 = 2^3 = 2^n - stimmt.
> >
> >n=4:
> >8 + 8 = 16 = 2^4 = 2^n - stimmt.
> >
>
> ich hätte da folgende idee:
> für G(n):= 2^(n-1)
> für U(n):= 2^(n-1)
Die Vermutung hatte ich auch - du hast das
also erkannt.
> nun eine frage zum beweis:
> a) welche von den beiden formeln sollte ich verwenden? (1-1)^n oder 2^(n-1)
>
> b) wie beweise ich das? soll ich dann einfach G(n) in die Formel einsetzen?
> U(n) + G (n) = 2^n --> umstellen nach U(n)
> U(n) = 2^n - G(n) --> G(n) einsetzen
> U(n) = 2^n - 2^(n-1)
> U(n) = 2^n - 2^n * 2^(-1) --> 2^n ausklammern
> U(n) = 2^n * ( 1 - 2^(-1))
> U(n) = 2^n * ( 1 - 1 / 2^1)
> U(n) = 2^n * 1/2
>
> ==> damit hätte ich U(n) berechnet, aber habe ich es damit auch bewiesen?
Wie Rainer schon sagte, hast du damit nur gezeigt,
dass U(n) die eine Häfte von 2^n ist, wenn G(n) die
andere ist.
Du müsstest jetzt zeigen, dass U(n) (oder G(n)) wirklich
die Hälfte ist.
Dazu kannst du auch zeigen, dass U(n) = G(n) ist.
> Frage:
> die vollständige Induktion wird die eigentlich nur bei summen hergenommen zum
> beweisen? oder kann man die auch bei anderen aussagen verwenden?
Die vollständige Induktion kannst du prinzipiell
bei jeder Aussage über natürliche Zahlen anwenden.
Bei Summenformeln bietet sich das wirklich an, aber
man könnte wohl auch diese Aufgabe damit lösen.
Paul
Manon garcia
> U(2n) = summe[k=0 .. n] (2n, 2k+1)
> U(2n+1) = summe[k=0 .. n] (2n+1, 2k+1)
>
kann man denn nicht auch:
U(n) = summe [k=0 .. n] (n über 2k + 1) ansetzen? denn der obere wert muß noch
nicht gerade sein oder?
>Dass das jetzt immer 2^(2n - 1) bzw. 2^(2n) ergibt,
>müsstest du noch nachweisen.
ich dachte, ich muß 2^n nachweisen. warum meinst du muß ich 2^(2n-1) bzw.
2^(2n) nachweisen? das verstehe ich leider nicht.
manon
Manon garcia
ich habe in der auflistung nachgesehen, aber kein posting von dir von 20:52
gesehen. oder habe ich es übersehen? kannst du sie nochmal posten?
denn an einer einfacheren lösung ich sehr interessiert! :-))
manon
Christian Stapfer
20011103133255...@mb-fs.aol.com...
> hallo christian,
>
> es gibt ja für die geraden zahlen folgende formel:
>
> gerade: 2*n + 1
> ungerade: 2 * n
>
> > Binomialsatz: das
> > ergibt 2 * die Summe der Koeffizienten "n über (2*k + 1)"
> > = 2^n.
>
> kann ich da auch allgemein schreiben:
>
> G(n) = Summe (n über 2 * n) und
> U(n) = Summe (n über 2 * n + 1)
>
> habe ich dich richtig verstanden?
\binom{n}{k} := "n über k" ist gleich der
Zahl der k-elementigen Teilmengen (k=0..n) einer
n-elementigen Grundmenge. Falls Du dies nicht
als bekannt annehmen darfst, dann ist es wohl
am besten, zuerst diesen grundlegenden Zusammenhang
zu beweisen.
Zur Summation: um die Zahl G(n) der Teilmengen mit
gerader Anzahl (=2k) Elemente einer n-elementigen
Grundmenge zu erhalten, müssen also alle Binomial-
koeffizienten der Form \binom{n}{2k} über k summiert
werden; dito: um die Zahl U(n) der Teilmengen
mit ungerader Anzahl (=2k+1) Elemente einer n-elementigen
Grundmenge zu erhalten, müssen alle Binomialkoeffizienten
der Form \binom{n}{2k+1} über k summiert werden.
Aufgrund des Binomialsatzes ist ja
(1+1)^n = 2^n = \sum_{k=0}^n{\binom{n}{k}}
(Eine n-elementige Grundmenge besitzt 2^n verschiedene
Teilmengen, d.h. eine 2^n-elementige Potenzmenge.)
Ausserdem haben wir
(1+(-1))^n = 0^n = 0
= \sum_{k=0}^n{\binom{n}{k}(-1)^k}
Zusammengezählt also
(1+1)^n - (1+(-1))^n = 2^n - 0^n = 2^n
= \sum_{k=0}^n{(1+(-1)^k)\binom{n}{k}}
^^^^^^^^^^
1+(-1)^k ist = 0 für gerades k und = 2 für ungerades
k. Also ist (1+1)^n - (1+(-1))^n = 2^n = 2 * die
gesuchte Summe über k der Binomialkoeffizienten
\binom{n}{2k+1}
> weiter schreibst du:
Der Rest meines Beitrages war eigentlich nicht
wirklich an Dich sondern an Philipp Zumstein
adressiert, weil ich weiss, dass er sich vor
kurzem mit "erzeugenden Funktionen" beschäftigt
hat.
> > ((1+x)^n-(1+(-x))^n)/2
Diese Funktion von x nennt man "erzeugende Funktion"
der Zahlenfolge
a_k := 0 falls k gerade,
:= \binom{n}{k} falls k ungerade
weil die a_k bei ihrer "Entwicklung in eine Potenzreihe"
als Koeffizienten von x^k auftreten.
Ich glaube es ist nicht sinnvoll, dass ich nun
versuche, Dir diese Theorie per NG-postings zu
erklären...
Gruss,
Christian
Christian Stapfer
<snip/>
> Zusammengezählt also
Falsch formuliert: natürlich *subtrahiere* ich
die beiden Entwicklungen von (1+1)^n bzw.
(1+(-1))^n gemäss Binomialsatz.
Die nächste Zeile ist also noch richtig
> (1+1)^n - (1+(-1))^n = 2^n - 0^n = 2^n
^^^^
aber dann habe ich Unsinn geschrieben
> = \sum_{k=0}^n{(1+(-1)^k)\binom{n}{k}}
^^^^^^^^^^
Sollte richtig sein:
> = \sum_{k=0}^n{(1-(-1)^k)\binom{n}{k}}
^^^^^^^^^^
Daher ist auch die nächste Zeile falsch:
> 1+(-1)^k ist = 0 für gerades k und = 2 für ungerades
und sollte statt dessen richtig sein:
> 1 - (-1)^k ist = 0 für gerades k und = 2 für ungerades
^^^
> k. Also ist (1+1)^n - (1+(-1))^n = 2^n = 2 * die
> gesuchte Summe über k der Binomialkoeffizienten
> \binom{n}{2k+1}
Ich hoffe Dich nun mit diesem ganz dummen Fehler nicht
zu sehr verwirrt zu haben.
Gruss,
Christian
Manon garcia
mensch, du bist ja auch die ganze nacht wach um armen studis zu helfen ...
:-)))
also das G(n) + U(n) = 2^n ist dürfen wir als gegeben annehmen.
aber trotzdem möchte ich deinen ansatz verstehen und habe da noch einige
fragen:
>(1+1)^n = 2^n = \sum_{k=0}^n{\binom{n}{k}}
habe ich dich verstanden, dass heisst:
summe von k=0 bis n -> soweit gut, aber
..{\binom{n}{k}} bedeutet das binom (n über k)?
was bedeutet das? denn das finde ich bei mir nicht im script.
wir haben nur:
2^n = (1+1)^n = (n über 0) + (n über 1) + (n über 2) + ... + (n über n-1) + (n
über n)
oder ist das das selbe?
wenn ich jetzt die beiden formeln besitze für G(n) und U(n) ---> kommt jetzt
die vollständige induktion oder haben wir das mit deiner ausführung bereits
bewiesen?
manon
Manon garcia
danke für das posting, denn ich hatte den schritt nicht verstanden, warum
(1-1)^2 bei gerade 0 und bei ungeraden 2 ist.
aber jetzt verstehe ich es!
manon
Manon garcia
du hast geschrieben, dass die formeln für G(n) so lauten könnten:
> G(2n) = summe[k=0 .. n] (2n, 2k)
aber ich verstehe nicht, warum du G(2n) nimmst und nicht G(n). hat das einen
bestimmten grund?
> G(2n+1) = summe[k=0 .. n] (2n+1, 2k)
diese formel ist für den induktionsschluß oder? denn hier setzten wir n -> n+1
den nachweis werde ich jetzt mit der vollständigen induktion beweisen.
manon :-)
Manon garcia
so ich bin es nochmal und habe gezieltere fragen, denn ich habe versucht die
vollständige induktion anzuwenden ... (betonung liegt auf versucht) :-)
> G(2n) = summe[k=0 .. n] (2n, 2k)
bei dem induktionsansatz setze ich ja n=0 oder? denn es geht ja mit k=0 los.
dann bekomme ich heraus:
1:=0!
(0 über 2*0) = 0! / (0! (0-0)! = 1 -> das entspricht der leeren Menge OKAY
> U(2n) = summe[k=0 .. n] (2n, 2k+1)
induktionsansatz: n = 0
(2*0 über 2*0+1) = (0 über 1) GEHT DAS??? kann der untere teil größer sein als
der obere? nein oder? dann gibt es für U(2n) keine Teilmenge.
jetzt zu der kompletten formel:
G(n) + U(n) = 2^n --> wenn ich jetzt G(2n) + U(2n) einsetze wird dann 2^n zu
2^(2n) ???? oder bleibt es bei 2^n??? wenn die formel lauten würde:
G(2n) + U(2n) = 2^n --> kommt bei n=0
1 + 0 = 1 heraus OKAY aber bei 2^(2n) kommt ja dann 2 heraus --> stimmt nicht.
==> wenn ich dann deine formel 2^(2n-1) einsetze kommt auch 1 heraus, aber
woher hast du die formel? okay, ich verwende erstmal deine formeln und warte
dann auf deine antwort, warum ich die formeln verwenden soll. okay? :-)
also verwende ich jetzt G(2n) + U(2n) = 2^(2n-1). dann stimmt der
induktionsansatz.
damit ergibt sich:
G(2n) + U(2n) = 2^(2n-1)
induktionsschluß: als ich es probieren wollte mit G(n) habe ich gemerkt, dass
der untere teil größer wird als der obere. deshalb ging das bei mir ja nicht.
also verwende ich deine formeln:
>G(2n+1) = summe[k=0 .. n] (2n+1, 2k)
> U(2n+1) = summe[k=0 .. n] (2n+1, 2k+1)
damit kann ich beim induktionsschluß: n --> n+1 den beweis führen und hoffe,
dass dann 2^(2n) heraus kommt. mal sehen :-)
ich würde mich freuen, wenn du mir schreiben würdest:
1) warum wir die formeln so schreiben oder ob sich das ergibt?
2) war das mathematisch korrekt, wenn heraus kommen würde (0 über 1) das es da
kein ergebnis gibt?
3) in der aufgabe war nach G(n) gefragt, aber wir setzten jetzt G(2n) ein.
dürfen wir das? muß man das mathematisch begründen? oder reicht es, wenn das
richtige ergebnis heraus kommt?
4) du schreibst für den induktionsschluß: U(2n+1) müßte das nicht heißen
U(2(n+1)) oder habe ich die formel falsch verstanden? denn wir setzten doch für
n --> n+1 oder?
ich hoffe, du oder ihr habt noch lust mir auf diese fragen zu antworten. denn
dann habe ich die aufgabe wirklich verstanden und kann sie mit gutem gewissen
abgeben. denn die gefahr besteht natürlich, wenn ich eine von wenigen bin, die
die aufgabe gelöst hat, dass ich vorrechnen muß und dann sollte ich alles
begründen können.
also bis bald
manon
Rainer Rosenthal
Manon Garcia <sonne...@aol.com> schrieb
>
> Es sei [n] := {1,2,...,n} für n element von N definiert.
> Finden sie formeln für
> G(n) := # {M Teilmenge von [n] : # M gerade} bzw.
> U(n) := # {M Teilmenge von [n] : # M ungerade}
>
> Hinweis: G(n) + U(n) = 2^n
>
Hallo Manon,
nachdem der wichtigste Zweck der Übung (nämlich Üben)
erreicht worden ist, und nachdem sehr viele Fäden und
Querverbindungen entstanden sind, möchte ich noch einen
eigenen Entwurf zur Lösung präsentieren. Dabei verwende
ich meine eigene Überlegung zur Berechnung von G und U
statt der zugegebenermassen pfiffigen Binom-Rechnung.
Der in der Aufgabe gegebene Hinweis auf G(n) + U(n) = 2^n
ist sehr gut. Denn dann genügt es G(n) = U(n) zu beweisen !
Weil die Summe 2^n ist, bleibt für beide gerade die Hälfte,
d.h. G(n) = U(n) = 2^n/2 = 2^(n-1).
*****************************************
Satz: G(n) = U(n) für alle n = 1,2, ...
Beweis durch vollständige Induktion:
Induktionsanfang:
G(1) = # { M Teilmenge von [1] : # M gerade } = # { {} } = 1
U(1) = # { M Teilmenge von [1] : # M ungerade } = # { {1} } = 1
Also G(1) = U(1).
Induktionsannahme: G(n) = U(n).
Induktionsschritt:
Teile die Teilmengen von [n+1] auf in solche mit dem
Element (n+1) und solche ohne das Element (n+1):
P = { M Teilmenge von [n+1] : n+1 ist Element von M }
Q = { M Teilmenge von [n+1] : n+1 ist nicht Element von M }
Setze
PG = { M Element von P : # M gerade }
PU = { M Element von P : # M ungerade }
QG = { M Element von Q : # M gerade }
QU = { M Element von Q : # M ungerade }
Es ist dann
G(n+1) = #PG + #QG (1)
U(n+1) = #PU + #QU (2)
Offenbar ist #QG = G(n) und #QU = U(n).
(Die Elemente von Q sind ja die Teilmengen von [n]).
Nach Induktionsannahme also #QG = #QU.
Jetzt zeige ich noch #PG = #PU.
Ein M aus PG hat gerade Anzahl. M ohne (n+1) hat
also ungerade Anzahl. Die M aus PG entsprechen
also eineindeutig den ungeraden Teilmengen von [n].
Also ist #PG = U(n).
Ebenso ist #PU = G(n).
Aus der Induktionsannahme folgt also #PG = #PU.
Aus (1) und (2) folgt also
G(n+1) = #PG + #QG = #PU + #QU = U(n+1)
Aus der Induktionsannahme G(n) = U(n) konnte also
G(n+1) = U(n+1) hergeleitet werden.
Ende des Beweises
*****************************************
Das ist alles in allem recht länglich geworden, aber nach dem vielen
Hin und Her wollte ich doch ein Beispiel für einen formal sauberen
Beweis geben. Ich hoffe, das ist mir gelungen.
Gruss,
Rainer Rosenthal
r.ros...@web.de
-
P.S. In einem früheren Posting hatte ich Dich schon darauf
aufmerksam gemacht, wie man die Mengen-Elemente immer
Ja und Nein rufen lässt und dadurch die Teilmengen von [n]
klassifiziert und aufgezählt bekommt.
Ich habe das hier in etwas seriöserer Form aufgeschrieben, weil
ich zuerst auf diesem Wege die Aufgabe lösen wollte, bis mir der
obige elegantere G(n) = U(n) Gedanke gekommen war.
Zum Wefwerfen waren mir meine Zeilen dann aber zu schade,
daher habe ich sie hier als P.S. dran gehängt :-)
Ich schreibe A(n) = # { M Teilmenge von [n] } und erinnere
an den Beweis, mit dem man zeigt, dass A(n) = 2^n ist.
*****************************************
Satz: A(n) = 2^n für alle n = 1, 2, ...
Beweis durch vollständige Induktion:
Induktionsanfang: A(1) = 2^1 = 2 ist richtig, weil [1] = { 1 }
die Teilmengen { } und {1} hat.
Induktionsannahme: A(n) = 2^n.
Induktionsschritt: Die Teilmengen von [n+1] sind solche mit
solche ohne (n+1) als Element. Die ohne (n+1) sind
genau die von [n]. Also gibt es davon A(n) viele.
Die mit (n+1) als Element sind von der Form T u { n+1 }
mit einem T aus [n]. Sie entsprechen eineindeutig den
Elementen von [n], es gibt also ebenfalls A(n) viele davon.
Also ist die Anzahl A(n+1) = A(n) + A(n) = 2*2^n = 2^(n+1).
Es konnte also gezeigt werden, dass wenn A(n) = 2^n ist,
dann auch A(n+1) = 2^(n+1).
Ende des Beweises
*****************************************
Nach genau diesem Muster kann man dann auch die Formeln
für G und U herleiten. Der Kern des obigen Beweises ist ja, dass
ein hinzukommendes Element die Anzahl der Teilmengen dadurch
verdoppelt, dass es zu jeder der vorhandenen dazukommt oder
nicht. Wenn man sich das genauer anschaut, dann sieht man, dass
sich bezüglich gerade/ungerade nur dann etwas ändert, wenn das
neue Element dazukommt. Und zwar wird dann aus einer geraden
Teilmenge eine ungerade und umgekehrt. Das Verhältnis bleibt also
Halbe-Halbe.
Manon garcia
ich werde dein posting ausdrucken und in ruhe nachvollziehen. ich glaube aber,
dass ich den einzelnen schritten folgen kann.
bei der binominalentwicklung kam ich nicht so richtig weiter, weil ich da ein
paar fragen hatte, die mir noch nicht beantwortet wurden. ich möchte aber nur
eine hausaufgabe abgeben, wenn ich sie verstanden und dann auch erklären kann.
kannst du mir vielleicht sagen,
a) warum der unter teil von binomialkoeffizienten nicht größer als der obere
sein darf?
denn bei der binomialentwicklung kamen wir zum schluß ja zu folgendem:
G(n) = Summe_k=0 bis n (n über 2k) --> denn hier würde der untere
binomialkoeffizient ja größer werden als n -> da 2 * n > n. darf man dann
einfach aufhören bei der summe, wenn der untere teil größer werden würde als
der obere?
z.b. n=2
(2 über 0) + (2 über 2*1) + und hier paßt es dann nicht mehr (2 über 2*2) -->
dürfte man den letzten term weglassen, weil der untere teil nicht größer sein
darf oder muß man an seiner formel etwas ändern, so dass der fall gar nicht
erst eintritt?
müßte ich dann schreiben G(2n) = Summe_k=0 bis n (2n über 2k)????
damit hätte ich das problem zwar nicht mehr, dass der untere
binomialkoeffizient > oberer binom., aber damit bekomme ich aber falsche werte
heraus:
z.b.
n=2
G(2n) = (2*2 über 0) + (2*2 über 2*1) + (2*2 über 2*2) = 8 das stimmt nicht
mit 2^n/2 = 2^2/2 = 2 überein.
generelle frage:
dürfte man die formel dann so umstellen, wie man es beim ausprobieren
ermittelt? wenn der beweis dann stimmt müßte doch die aufgabe wieder stimmen
oder? oder muß man sich an die aufgabenstellung halten in diesem fall an G(n)?
so, nun werde ich aber erstmal dein posting durcharbeiten.
bis bald
manon
Rainer Rosenthal
Manon garcia <manon...@aol.com>
>
> ich werde dein posting ausdrucken und in ruhe nachvollziehen. ich glaube
> aber, > dass ich den einzelnen schritten folgen kann.
Hallo Manon,
das nehme ich auch an. Und ich wünsche Dir Erfolg. Wie ich schon geschrieben
habe, war mir das Wichtigste, dass nach all den einzelnen Erörterungen ein
Beispiel dasteht, das zeigt, wie ein Rahmen auszusehen hat.
Es gibt da im einzelnen gewisse Geschmacksunterschiede, aber generell kann
man sagen, dass man es bei mathematischen Erörterungen mit folgendem zu
tun hat.
Erstens mit einer Diskussion des Themas,
wobei gewisse Begriffe geklärt werden und eine bestimmte Notation
gewählt wird. Dabei kriegt man das Thema erst einmal in den Griff.
In unserem Beispiel ist es die Notierung [n] für {1,2,...,n}, die sehr
praktisch ist, obwohl sie natürlich in anderen Zusammenhängen für was
anderes verwendet wird; typisch ist da z.B. [3.14159] = 3.
Weiterhin wurde bei Euch #M verwendet für "Anzahl der Elemente von M".
Auch das sieht man oft anders, meistens als |M| oder auch als card(M).
Und so weiter. Alle diese Bausteine haben wir ja dann auch gemeinsam in
diesem Thread auseinander genommen und ihre Bedeutung geklärt. Ohne
diese Arbeit, ohne dieses Grundverständnis ALLER Teile kannst Du nix
erreichen.
Zweitens mit Aussagen, Vermutungen, Behauptungen, Sätzen.
Es wird oft genug in der Gegend herumgeschwätzt - ich nehme mich da
nicht aus - ohne dass eigentlich klar ist, worum es überhaupt geht. In
der Mathematik ist dem ein gewisser Riegel vorgeschoben, weil es dann
irgendwann heisst: genug gelabert
( vornehmer: diskutiert, definiert, motiviert ...) - jetzt sage, worum
es geht, formuliere Deine Behauptung.
Drittens mit Beweisen
Wenn erst einmal die Grundlagen (erstens s.o.) geklärt sind, wozu dann
auch noch Axiome kommen können, über die man sich erst noch verständigen
zu müssen meint, und wenn die Behauptung klar formuliert ist, dann kann
man sich auf diese konzentrieren und das Mathespiel heisst dann: Beweis'
oder stirb.
Dass man dabei feststellen kann, dass man die Behauptung gar nicht oder
falsch verstanden hat, dass die Grundlagen nur scheinbar klar waren
usw., das macht die Beweiserei dann zusätzlich interessant.
Und genau diesen zweiten+dritten Teil wollte ich gern einmal demonstrieren.
Ich war selbst erstaunt, wieviel Zeit mich das gekostet hat, diese
gerade/ungerade Thematik sauber zu fassen. Ein bisschen unbehaglich ist es
mir, wenn Du meine Lösung quasi 1:1 übernehmen würdest. Aber im Endeffekt
ist wohl wenig dagegen zu sagen, weil Du die Details ja alle mitgeübt hast
und Dir selbst vorgenommen hast, die Sache so aufzunehmen, dass Du über
alle Schritte Rechenschaft geben kannst.
Wenn Du mit den Binomen glücklich wirst, dann ist das genauso gut oder auch
besser. Aber auch dann sollte halt der Rahmen stimmen. Also die Regeln des
Mathe-Spiels eingehalten werden.
>
> bei der binominalentwicklung kam ich nicht so richtig weiter, weil ich da
> ein paar fragen hatte, die mir noch nicht beantwortet wurden. ich möchte
> aber nur eine hausaufgabe abgeben, wenn ich sie verstanden und dann
> auch erklären kann.
>
> kannst du mir vielleicht sagen,
> a) warum der unter teil von binomialkoeffizienten nicht größer als der
> obere sein darf?
Ich schlage zu dieser Frage meinen Rechen-Duden auf. Ich empfehle Dir die
Anschaffung dieses Buches sehr, weil viele wichtige Begriffe ohne Schnörkel
erklärt werden.
Binomialkoeffizient:
Ist N eine Menge mit genau n Elementen, so bezeichnet man mit
(n über k) ( gelesen "n über k") die Anzahl der verschiedenen
k-elementigen Teilmengen von N.
Die Zahlen 0 <= k <= n heissen Binomialkoeffizienten, weil sie als
Koeffizienten im binomischen Lehrsatz auftreten.
Im weiteren wird dann auf die Formel eingegangen
n über k) = (n/k) * ((n-1)/(k-1)) * ... * ((n-k+1)/1),
das Pascalsche Dreieck erklärt, die Verbindung zum Zahlenlotto "6 aus 49"
dargestellt und einige Formeln zur Verwandtschaft der Koeffizienten
vorgestellt.
Und zum Schluss kommt dann sogar das, wonach Du gefragt hast:
Wir haben (n über k) bisher nur für ganze Zahlen n, k mit 0 <= k <= n
definiert. Für nichtnegative ganze Zahlen k und beliebige reelle
Zahlen a definiert man:
(a über k) = a*(a-1)*(a-2)*...*(a-k+1) / k!
Dies sind die Koeffizienten in der binomischen Reihe. Insbesondere ist
(n über k) = 0 für ganze Zahlen n, k mit 0 <= n < k
Soweit also der Rechen-Duden.
Und die Festlegung ( 3 über 7 ) = 0 macht durchaus Sinn, denn die Anzahl
der Möglichkeiten, eine 7-elementige Teilmenge aus einer 3-elementigen Menge
zu wählen, kann man getrost mit Null bezeichnen :-)
>
> denn bei der binomialentwicklung kamen wir zum schluß ja zu folgendem:
> G(n) = Summe_k=0 bis n (n über 2k) --> denn hier würde der untere
> binomialkoeffizient ja größer werden als n -> da 2 * n > n. darf man dann
> einfach aufhören bei der summe, wenn der untere teil größer werden würde
> als der obere?
Bei dieser Diskussion bin ich nicht mehr durchgestiegen; ich denke, dass da
noch ein wenig Konfusion bei den Indizes bzw. den Grenzen besteht. Wenn da
die Binomialkoeffizienten (n über 2k) verwendet werden, dann ist für mich
klar, dass man sich mit der Anzahl der Möglichkeiten befasst, Mengen mit
gerader Anzahl (2k) aus der n-elementigen Menge [n] = { 1, 2, 3, ... n }
auszuwählen.
Wieso man da bis k=n summiert, will mir nicht in den Schädel. Und ich sehe
da auch durchaus Schwierigkeiten beim Formulieren - keine unüberwindbaren,
aber doch eben Schwierigkeiten. Denn plötzlich spielt es eine Rolle, ob n
selbst gerade ist oder nicht. Wenn ja, dann muss bis zu 2k = n summieren,
wenn nein, dann nur bis zu 2k = n-1.
> z.b. n=2
> (2 über 0) + (2 über 2*1) + und hier paßt es dann nicht mehr
> (2 über 2*2) -->
> dürfte man den letzten term weglassen, weil der untere teil nicht größer
> sein darf oder muß man an seiner formel etwas ändern, so dass der fall gar
> nicht erst eintritt?
Es scheint nichts Schlimmes zu passieren, wenn man etwas weiter summiert als
unbedingt nötig, weil man dann bloss Null addiert. Aber schön ist anders :-)
>
> müßte ich dann schreiben G(2n) = Summe_k=0 bis n (2n über 2k)????
> damit hätte ich das problem zwar nicht mehr, dass der untere
> binomialkoeffizient > oberer binom., aber damit bekomme ich aber falsche
> werte heraus:
> z.b.
> n=2
> G(2n) = (2*2 über 0) + (2*2 über 2*1) + (2*2 über 2*2) = 8 das stimmt
> nicht mit 2^n/2 = 2^2/2 = 2 überein.
>
> generelle frage:
> dürfte man die formel dann so umstellen, wie man es beim ausprobieren
> ermittelt? wenn der beweis dann stimmt müßte doch die aufgabe wieder
> stimmen, oder? oder muß man sich an die aufgabenstellung halten in diesem
> fall an G(n)?
Diese Passage wirst Du selbst beim erneuten Lesen nicht verstehen. Oder ?
"Dürfte man die Formel dann so umstellen, wie man es beim
Ausprobieren ermittelt ?"
Selbst wenn ich die mir geläufigeren Grossbuchstaben verwende, sehe ich
nicht, wonach Du hier fragst.
"Wenn der Beweis dann stimmt, müsste doch auch die Aufgabe
wieder stimmen, oder ?"
Sorry, das ist irgendwie daneben :-)
Natürlich bist Du ganz schön im Stress, aber ich hoffe, dass Du das in den
Griff kriegst. So wie Du Dich jetzt in die Sache reinkniest, stehen die
Chancen ja sehr gut.
>
> so, nun werde ich aber erstmal dein posting durcharbeiten.
>
Das freut mich, dass die Mühe nicht umsonst war.
Gruss,
Rainer
Christian Stapfer
> hallo christian,
>
> mensch, du bist ja auch die ganze nacht wach um
> armen studis zu helfen ... :-)))
Nicht gerade nur *deswegen*... (dafür bin ich
normalerweise erst am Abend wieder kurz auf
dem Netz).
> also das G(n) + U(n) = 2^n ist dürfen wir als
> gegeben annehmen. aber trotzdem möchte ich deinen
> ansatz verstehen und habe da noch einige
> fragen:
>
> >(1+1)^n = 2^n = \sum_{k=0}^n{\binom{n}{k}}
>
> habe ich dich verstanden, dass heisst:
> summe von k=0 bis n -> soweit gut, aber
>
> ..{\binom{n}{k}} bedeutet das binom (n über k)?
Ja
> was bedeutet das? denn das finde ich bei mir nicht
> im script.
Sorry, das war nur eine von der LaTeX Package
amsmath inspirierte *Schreibweise* für den
Binomialkoeffizienten (n über k). Also keine
Substanz: nur eine Frage der Notation in einem
NG Posting.
> wir haben nur:
> 2^n = (1+1)^n = (n über 0) + (n über 1) + (n über 2) +
> ... + (n über n-1) + (n über n)
> oder ist das das selbe?
Was Du idealerweise wissen solltest ist, dass für
beliebiges a,b und natürliche Zahlen n
[*] (a+b)^n = (n über 0)a^n b^0 + (n über 1)a^{n-1}b^1
+ ... + (n über n)a^{n-n} b^n
gilt. Dies könnte man, wenn nötig, durch Induktion
nach n beweisen. Im weiteren ist (n über k)
auch die Anzahl verschiedener k-elementiger
Teilmengen einer n-elementigen Grundmenge.
[*] mit a=b=1 zeigt also, dass die Gesamtzahl
der Teilmengen von {1, .., n}, bzw. die Kardinalität
der Potenzmenge von {1, .., n}, das heisst Deine
Summe G(n) + U(n), gleich 2^n ist.
Wegen [*] mit a=1, b=-1 ist aber auch:
0^n = (1+(-1))^n = (n über 0) - (n über 1) + (n über 2) -
... + (n über k)*(-1)^k + ... + (n über n)*(-1)^n
daher fallen bei der folgenden Subtraktion die Glieder
mit geradem k heraus und es bleibt nur das Doppelte
der Glieder mit ungeradem k:
2^n - 0^n = 2*(n über 1) + 2*(n über 3) + ...
...
= 2 * [(n über 1) + (n über 3) + ...]
Also ist die gesuchte Summe U(n) der Binomialkoeffizienten
(n über k) für ungerades k gleich 2^n/2 (beide Seiten durch
2 dividiert).
G(n) ist dann = 2^n - U(n) = 2^n - 2^{n-1} = 2^{n-1}.
> wenn ich jetzt die beiden formeln besitze für G(n) und U(n)
> ---> kommt jetzt die vollständige induktion oder haben wir
> das mit deiner ausführung bereits bewiesen?
Diese Summen sind ja schon für beliebiges n angesetzt,
daher ist keine Induktion für den Übergang zum
"allgemeinen Fall" mehr nötig - den haben wir schon.
Ich kann Dir aber keine Garantie geben, dass diese
Argumentation von Deinem Lehrer problemlos geschluckt
wird - Lehrer sind da manchmal recht komisch - mit
anderen Worten: ich habe nicht versucht, mich in die
Detailsituation in Deinem Lehrplan einzuarbeiten, sondern
einfach eine (möglicherweise gänzlich deplazierte)
Bemerkung zum Beitrag von Philipp Zumstein senden wollen.
Gruss,
Christian
Manon garcia
ich habe dein posting verstanden.
dein tipp sich ein duden zu kaufen werde ich befolgen. kennst du ein gutes oder
sind die alle gleich?
der hinweis, dass bei 0>n>k alle binomialkoeffizienten gleich Null sind, hilft
mir in sofern, dass ich dann eine zweite möglichkeit hätte die aufgabe zu
lösen. nicht so schön zwar, aber es funktioniert dann.
also erstmal vielen dank, denn mir hat das wochenende sehr viel gebracht. in
bin in die materie ein ganzen stück hinein gekommen und verstehe die
zusammenhänge schon viel besser!
bis bald
manon
Manon garcia
vielen dank für deine hilfe. ich werde das dann nochmal durchgehen und
versuchen endgültig zu verstehen.
bis bald
manon
Rainer Rosenthal
Manon garcia <manon...@aol.com> wrote
> hallo rainer,
>
> ich habe dein posting verstanden.
>
> dein tipp sich ein duden zu kaufen werde ich befolgen. kennst du ein
> gutes oder sind die alle gleich?
> [ ... ]
> also erstmal vielen dank, denn mir hat das wochenende sehr viel gebracht.
> Ich bin in die materie ein ganzen stück hinein gekommen und verstehe die
> zusammenhänge schon viel besser!
>
Hallo Manon,
freut mich sehr! Dein Dankschreiben kommt in meinen Danke-Ordner,
denn ich bin ein eitler Mensch. Ausserdem habe ich den ehrlichen Eindruck,
dass sich der Aufwand gelohnt hat. Du bist ja auch wirklich knallhart dran
geblieben.
DUDEN, Rechnen und Mathematik, Das Lexikon
für Schule und Praxis. ISBN 3-411-02423-2.
Gruss und toi-toi-toi
Rainer Rosenthal
r.ros...@web.de
-
Teile nie durch Nüll, sonst erhältst du Müll.
Paul Ebermann
>
> > U(2n) = summe[k=0 .. n] (2n, 2k+1)
> > U(2n+1) = summe[k=0 .. n] (2n+1, 2k+1)
Ich habe hier die Formeln für gerade n (also Vielfache von 2)
und ungerade n einzeln aufgeschrieben. Deswegen habe ich statt
n einmal 2n, das andere mal 2n+1 geschrieben.
> kann man denn nicht auch:
> U(n) = summe [k=0 .. n] (n über 2k + 1) ansetzen? denn der obere wert muß noch
> nicht gerade sein oder?
Dann hast du wieder alle Teilmengen aufsummiert, nicht nur die
mit gerader/ungerader Elementeanzahl.
> >Dass das jetzt immer 2^(2n - 1) bzw. 2^(2n) ergibt,
> >müsstest du noch nachweisen.
> ich dachte, ich muß 2^n nachweisen. warum meinst du muß ich 2^(2n-1) bzw.
> 2^(2n) nachweisen? das verstehe ich leider nicht.
Statt n habe ich 2n bzw. 2n+1 verwendet.
Paul
Paul Ebermann
> vollständige induktion anzuwenden ... (betonung liegt auf versucht) :-)
>
> > G(2n) = summe[k=0 .. n] (2n, 2k)
>
> bei dem induktionsansatz setze ich ja n=0 oder? denn es geht ja mit k=0 los.
> dann bekomme ich heraus:
> 1:=0!
> (0 über 2*0) = 0! / (0! (0-0)! = 1 -> das entspricht der leeren Menge OKAY
>
> > U(2n) = summe[k=0 .. n] (2n, 2k+1)
> induktionsansatz: n = 0
> (2*0 über 2*0+1) = (0 über 1) GEHT DAS??? kann der untere teil größer sein als
> der obere? nein oder? dann gibt es für U(2n) keine Teilmenge.
Genau. Wenn in einem Binomialkoeffizient oben eine 0 steht, und unten eine
positive (ganze) Zahl, ist das Ergebnis 0.
> jetzt zu der kompletten formel:
> G(n) + U(n) = 2^n --> wenn ich jetzt G(2n) + U(2n) einsetze wird dann 2^n zu
> 2^(2n) ???? oder bleibt es bei 2^n??? wenn die formel lauten würde:
> G(2n) + U(2n) = 2^n --> kommt bei n=0
> 1 + 0 = 1 heraus OKAY aber bei 2^(2n) kommt ja dann 2 heraus --> stimmt nicht.
> ==> wenn ich dann deine formel 2^(2n-1) einsetze kommt auch 1 heraus, aber
> woher hast du die formel? okay, ich verwende erstmal deine formeln und warte
> dann auf deine antwort, warum ich die formeln verwenden soll. okay? :-)
Es ist natürlich
G(2n) + U(2n) = 2^(2n).
> also verwende ich jetzt G(2n) + U(2n) = 2^(2n-1). dann stimmt der
> induktionsansatz.
> damit ergibt sich:
> G(2n) + U(2n) = 2^(2n-1)
>
> induktionsschluß: als ich es probieren wollte mit G(n) habe ich gemerkt, dass
> der untere teil größer wird als der obere. deshalb ging das bei mir ja nicht.
> also verwende ich deine formeln:
>
> >G(2n+1) = summe[k=0 .. n] (2n+1, 2k)
> > U(2n+1) = summe[k=0 .. n] (2n+1, 2k+1)
> damit kann ich beim induktionsschluß: n --> n+1 den beweis führen und hoffe,
> dass dann 2^(2n) heraus kommt. mal sehen :-)
>
> ich würde mich freuen, wenn du mir schreiben würdest:
> 1) warum wir die formeln so schreiben oder ob sich das ergibt?
Ich wollte eben die Formeln für gerade und ungerade Zahlen trennen.
Wie du schon herausgefunden hast, sind die Binomialkoeffizienten
(n,k) ja 0, wenn n < k, also ist es nicht so schlimm, wenn du
deine Summierungsvariante verwendest.
> 2) war das mathematisch korrekt, wenn heraus kommen würde (0 über 1) das es da
> kein ergebnis gibt?
(0 über 1) ist 0.
> 3) in der aufgabe war nach G(n) gefragt, aber wir setzten jetzt G(2n) ein.
> dürfen wir das? muß man das mathematisch begründen? oder reicht es, wenn das
> richtige ergebnis heraus kommt?
Du kannst es vielleicht so schreiben:
G(n) = summe [k=0 .. n/2] (n, 2k) wenn n eine gerade Zahl
G(n) = summe [k=0 .. (n-1)/2] (n, 2k) wenn n eine ungerade Zahl
Und analog für U(n).
> 4) du schreibst für den induktionsschluß: U(2n+1) müßte das nicht heißen
> U(2(n+1)) oder habe ich die formel falsch verstanden? denn wir setzten doch für
> n --> n+1 oder?
Das war kein Induktionsschluss, das war nur ein
anderer Fall - der mit ungeradem Argument.
Paul
Andreas Zerbst
U(n) die Summe aller Binomialkoeffizienten (n ueber k) ist
mit k ungerade (weil gerade der Binomialkoeffizient angibt,
wieviel Teilmengen mit k-Elementen es aus einer n-elementigen
Menge gibt)
2) Analog fuer G(n) mit k gerade.
3) Wir wissen oder zeigen, dass Binomialkoeff.(n ueber k) gleich
Binomialkoeff. (n-1 ueber k) + Binomialkoeff. (n-1 ueber k-1)
Aus 1) bis 3) folgt, dass U(n)=G(n) etc.
(Die richtigen Wertebereiche fuer das jeweilige k muss natuerlich
korrekt angegeben werden und alles muss schoen ausfuehrlich und exakt
notiert werden - anschaulichster Schluessel sind jedenfalls die
Summenformeln ueber die Binomialkoeffizienten, die Zerlegung eines
Binomialkoeffizienten in zwei andere und der Zusammenhang zwischen
der Anzahl von Teilmengen und Binomialkoeffizient)
Gruss,
Andreas Zerbst.
Hermann Kremer
Hallo Manon,
sorry, daß es erst jetzt kommt, aber ich war gestern unterwegs ...
Du mußt nur wissen, daß
G(n) = "n über 0" + "n über 2" + ...
U(n) = "n über 1" + "n über 3" + ...
ist - aber das dürfte ja mittlerweile klar sein.
Außerdem brauchst Du die binomischen Formeln für
(a + b)^n und (a - b)^n .
----------------------------------------------
Von: Hermann Kremer <hermann...@online.de>
Betreff: Re: Beweis einer Analysis Aufgabe
Datum: Samstag, 3. November 2001 20:52
[ ... ]
Ich gebe Dir mal einen Tip (der wurde zwar schon mal gepostet, den hast Du