Vollständige Induktion. Beweise: Summe (n über k)= 2^n

Question

\( \sum \limits_{k=0}^{n}\left(\begin{array}{l}{n} \\ {k}\end{array}\right)=2^{n} \)

melde mich noch einmal. Ich bekomme die Vollständige Induktion für n über k gleich 2 hoch n nicht hin. Als Anhang habe ich meinen Rechenweg hinzugefügt.

Ich weiss nicht wie man ((n-k)(n) / (k-1)!) umformen kann :(

Für n über k kann man ja zu n! / ((n-k)! * k!) umformen, aber wie ich  ((n-k)(n) / (k-1)!) umformen kann weiß ich überhaupt nicht.

Die Aufgabe soll mit vollständiger Induktion ausgeführt werden. Ich übe gerade für
das Studium (Bin noch nicht im ersten Semester). Mit dem Summenzeichen kenne
ich mich bisher auch kaum aus, daher wäre die ausführliche Variante leichter
zu verstehen.

Comments

Du wuefelst hier alles bunt durcheinander, was zeigt, dass Du das Prinzip der vollstaendigen Induktion ueberhaupt noch nicht begriffen hast. Bevor Du das nicht geaendert hast, kannst Du unmoeglich Beispiele rechnen.

Fangen wir mit dem Induktionsprinzip an. Es sei \(M\subset\mathbb{N}=\{1,2,3,\ldots\}\) und für \(M\) gelte:

(i)   \(1\in M\),

(ii)  Aus \(n\in M\) folgt \(n+1\in M\).

Was kann man dann ueber \(M\) sagen?

---

Ich habe schon ein paar Aufgaben lösen können.

Hier fällt es mir aufgrund des Binomialkoeffizienten und der Summenzeichen nicht leicht.

---

Abwarten. Willst Du zu dem \(M\) was sagen?

---

M ist Teilmenge von N, also den natürlichen Zahlen.

1 -> Das die Zahl eins Element der Menge M ist. Generell ist die
eins die kleinste natürliche Zahl.

2 -> Das jede Zahl n einen weiteren Nachfolger n + 1 hat.
Bedeutet, wenn für etwas für den Nachfolger n + 1 gilt, so gilt dies für alle n.

---

Und was ist mit \(M\) selber? Kann man nicht ganz konkret sagen, in welcher Beziehung \(M\) zu \(\mathbb{N}\) steht. (Ueber die Voraussetzung \(M\subset\mathbb{N}\) hinaus?)

---

Keine Ahnung. Erkläre mir bitte was man genau über M sagen kann :/

---

(i) sagt \(1\in M\). Mit (ii) folgt \(2\in M\). Wieder (ii) ergibt \(3\in M\), usw. Also was wird \(M\) wohl sein?

---

Stehe auf dem Schlauch :/

Nach wie vor würde ich sagen das M zur Menge der natürlichen Zahlen gehört.
M ist also n? :(

---

Oben hab ich \(\mathbb{N}=\{1,2,3,\dots\}\) geschrieben, mit dem Induktionsprinzip ergibt sich für \(M\): \(1\in M\), \(2\in M\), \(3\in M\), ... Was ist das für ein Schlauch, auf dem Du stehst?

---

Also: Jedes M hat genau einen Nachfolger.

---

Ich glaube, das wird heute nix mehr. \(M\) ist eine Menge von natuerlichen Zahlen, selbst aber keine natuerliche Zahl.  \(M\) hat keine Nachfolger. Die richtige Antwort waere \(M=\mathbb{N}\) gewesen.

Tja, also: Diese simple Aussage nennst sich Induktionsprinzip. Die natuerlichen Zahlen sind eindeutig durch die Eigenschaft definiert, dass sie einen Anfang (1) haben, und dass es zu jeder Zahl (n) eine naechste (n+1) gibt. Jede Menge natuerlicher Zahlen, die auch diese Eigenschaft hat, ist schon identisch zur Menge aller natuerlichen Zahlen. Um zu zeigen, dass ein Teilmenge \(M\) von \(\mathbb{N}\) schon ganz \(\mathbb{N}\) ist, muss man also bloss zeigen, dass \(M\) den Bedingungen (i) und (ii) des Induktionsprinzips genuegt.

Eigentlich wollte ich jetzt aus dem Induktionsprinzip das Beweisverfahren der vollstaendigen Induktion ableiten, aber nachdem es bisher so zaeh ging, wird es wohl am besten sein, hier für heute aufzhoeren.

---

Ich verstehe :)

Tut mir Leid, der Stoff ist noch ganz neu für mich

---

Mit dem binomischen Lehrsatz und ohne Induktion kommt man bei auch zu dieser Formel.

Diskussion z.B. hier: https://www.mathelounge.de/61002/zeigen-sie-dass-die-folgende-gleichung-gilt-∑-n-tief-k-2-n

Musst du denn unbedingt einen Induktionsbeweis machen?

---

VIelen Dank für die Verlinkung Lu!

Ja steht auf dem Aufgabenblatt so. Kennst du eventuelle eine Seite,
bei der man Binomialkoeffizienten umformen und sich mit
Summenzeichen vertraut machen kann?

Grüße :)

---

Ich muss gerade weg. Aber eine Anfängereinführung zum Summenzeichen findest du, wenn du

bei https://www.matheretter.de/mathe-videos?aff=gmf&subid=gmf-menu-top

Summenzeichen in die Suche eingibst.

Ansonsten auch mal Diskussion zu c) ansehen. Hier:

http://matheplanet.com/default3.html?call=viewtopic.php?topic=99782&ref=http%3A%2F%2Fwww.google.ch%2Fsearch%3Fclient%3Dsafari%26rls%3Den%26q%3Dbeweis%2Bsumme%2Bbinomialkoeffizient%26ie%3DUTF-8%26oe%3DUTF-8%26gfe_rd%3Dcr%26ei%3D1ZqwVdamN4yRigarrJaYCQ

---

Bitte. Gern geschehen.

Answer 1

Du hattest doch am Anfang für die linke Seite 2 Summen, und musst

nur zeigen, dass diese den gleichen Wert haben wie 2 ⁿ⁺¹  

Allerdings gehen beide von 0 bis n+1

Bei der ersten kommt dann der Summand 0 dazu ( nämlich für k=n+1)

und bei der 2. machst du eine Indexverschiebung  ist es auch so ( da kommt

als 1. Summand eine 0 dazu).  Also hast du 2 Summen mit je 2^n  und deren

Summe ist 2 ⁿ⁺¹   .