carlo berlingen schrieb zum Thema
sum(binomial(n,k)*2^k) =3^n
Post by carlo berlingenWer kan mir einen Tip zur Durchführung des Induktionsschritts geben.
Dieses Posting bitte mit Festbreitenschrift anzeigen lassen.
Ich hoffe, das Google-Groups-Interface zerstört nicht meine
Einrückungen an Zeilenanfängen.
Im folgenden verwende ich geschweifte Klammern {...} um Argumente
von Funktionen zu gruppieren und runde Klammern (...) um
mathematische Terme und Argumente von Folgengliedern zu gruppieren.
Mich deucht, die Aufgabe ist:
-----------------------------
Beweise durch Induktion, dass für n in N gilt:
3^n = SUMME{k=0..n}{(n ÜBER k) * (2^k)}
Man könnte es sich einfach machen und aus einem Mathebuch den
Induktionsbeweis für den Binomiallehrsatz, der da lautet:
(a+b)^n=SUMME{k=0..n}{(n ÜBER k)(a^(n-k))(b^k)}
, abschreiben und beim Abschreiben a mit 1 und b mit 2 ersetzen
und bedenken, dass Potenzen von 1 auch 1 ergeben.
Man kann aber auch, ohne an den Binomiallehrsatz zu denken,
im Rahmen eines Induktionsbeweises zeigen, dass:
3*( SUMME{k=0..m}{(m ÜBER k) * (2^k)} )
= SUMME{k=0..(m+1)}{((m+1) ÜBER k) * (2^k)}
Man muss dann allerdings ein paar Kniffe beim Rechnen mit
Binomialkoeffizienten und Summen kennen.
Deshalb:
Vorbemerkungen zum Rechnen mit Binomialkoeffizienten und Summen:
----------------------------------------------------------------
Für m,k in Z; 0 <= k <= m gilt:
Vorbemerkung 0: 0! = 1
Vorbemerkung 1: (m ÜBER k) = m!/((m-k)! * k!)
Vorbemerkung 1a: (m ÜBER k) = m!/((m-k)! * k!) = m!/((m-(m-k))! * (m-k)!) = (m ÜBER (m-k))
Vorbemerkung 1b: Für k = 0 folgt: (m ÜBER 0) = (m ÜBER m) = 1
Vorbemerkung 2: Für m,k in Z; 0 <= k < m gilt:
(m ÜBER (k+1)) + (m ÜBER k) = ((m+1) ÜBER (k+1))
Beweis:
(m ÜBER (k+1)) = (m ÜBER k) * (m-k)/(k+1)
(m ÜBER (k+1)) + (m ÜBER k) = (m ÜBER k) * (m-k)/(k+1) + (m ÜBER k)
= (m ÜBER k) * ( (m-k)/(k+1) + 1 )
= (m ÜBER k) * ( (m-k)/(k+1) + (k+1)/(k+1) )
= (m ÜBER k) * (m-k+k+1)/(k+1)
= (m ÜBER k) * (m+1)/(k+1)
= m!/((m-k)! * k!) * (m+1)/(k+1)
= (m+1)!/((m-k)! * k!) * 1/(k+1)
= (m+1)!/(((m+1)-(k+1))! * k!) * 1/(k+1)
= (m+1)!/(((m+1)-(k+1))! * (k+1)!)
= ((m+1) ÜBER (k+1))
Vorbemerkung 3:
SUMME{k=K..L}{a(k)} = SUMME{k=(K+D)..(L+D)}{a(k-D)}
In Worten:
Wenn man bei Summen über Folgenglieder den Start- und den Endwert
der Laufvariablen vergrößert, müssen die Argumente der Folgenglieder
entsprechend verkleinert werden.
Wenn man bei Summen über Folgenglieder den Start- und den Endwert
der Laufvariablen verkleinert, müssen die Argumente der Folgenglieder
entsprechend vergrössert werden.
Induktionsanfang:
-----------------
Die Aussage
3^n = SUMME{k=0..n}{(n ÜBER k) * (2^k)}
ist wahr für n = 1 -- für n=1 ergibt sich:
3^1 = SUMME{k=0..1}{(1 ÜBER k) * (2^k)}
= (1 ÜBER 0) * (2^0) + (1 ÜBER 1) * (2^1)
[ Vorbemerkung 1b: ]
= 1 * (2^0) + 1 * (2^1)
= 3^1
Induktionsannahme:
------------------
Die Aussage 3^n = SUMME{k=0..n}{(n ÜBER k) * (2^k)} sei wahr für den Fall n = m.
Induktionsschluss:
------------------
Aus 3^n = SUMME{k=0..n}{(n ÜBER k) * (2^k)} mit n=m
folgt 3^n = SUMME{k=0..n}{(n ÜBER k) * (2^k)} mit n=(m+1).
Dies lässt sich durch diverse Äquivalenzumformungen zeigen:
3^n = SUMME{k=0..n}{(n ÜBER k) * (2^k)} mit n=m
ist äquivalent zu:
3^m = SUMME{k=0..m}{(m ÜBER k) * (2^k)}
Multiplikation mit 3 ergibt:
3^(m+1) = 3* SUMME{k=0..m}{(m ÜBER k)*(2^k)}
Ab jetzt wird frohgemut der Term auf der rechten Seite der Gleichung
umgeformt bis er erbaulich aussieht:
3^(m+1) = 3* SUMME{k=0..m}{(m ÜBER k)*(2^k)}
[3*(Gedöns) = 2*(Gedöns)+1*(Gedöns) :]
= 2*( SUMME{k=0..m}{(m ÜBER k)*(2^k)} ) + SUMME{k=0..m}{(m ÜBER k)*(2^k)}
[Im vorderen Summenterm ausmultiplizieren:]
= SUMME{k=0..m}{(m ÜBER k)*(2^k)*2} + SUMME{k=0..m}{(m ÜBER k)*(2^k)}
[Bedenken, dass (2^k)*2 = 2^(k+1) :]
= SUMME{k=0..m}{(m ÜBER k)*(2^(k+1))} + SUMME{k=0..m}{(m ÜBER k)*(2^k)}
[Aus dem vorderen Summenterm den letzten Summanden herausholen:]
= SUMME{k=0..(m-1)}{(m ÜBER k)*(2^(k+1))} + ((m ÜBER m)*(2^(m+1))) + SUMME{k=0..m}{(m ÜBER k)*(2^k)}
[Bedenken, dass gemäß Vorbemerkung 1b (m ÜBER m) = 1 :]
= SUMME{k=0..(m-1)}{(m ÜBER k)*(2^(k+1))} + (2^(m+1)) + SUMME{k=0..m}{(m ÜBER k)*(2^k)}
[Aus dem hinteren Summenterm den ersten Summanden herausholen:]
= SUMME_{k=0..(m-1)}{(m ÜBER k)*(2^(k+1))} + (2^(m+1)) + SUMME{k=1..m}{(m ÜBER k)*(2^k)} + ((m ÜBER 0)*(2^0))
[Bedenken, dass (m ÜBER 0) = 1 :]
= SUMME{k=0..(m-1)}{(m ÜBER k)*(2^(k+1))} + (2^(m+1)) + SUMME{k=1..m}{(m ÜBER k)*(2^k)} + (2^0)
[Beim hinteren Summenterm gemäß Vorbemerkung 3 Start- und Endwert der Laufvariablen k
um 1 verkleinern und die Argumente der Folgenglieder um 1 vergrössern:]
= SUMME{k=0..(m-1)}{(m ÜBER k)*(2^(k+1))} + (2^(m+1)) + SUMME{k=0..(m-1)}{(m ÜBER (k+1))*(2^(k+1))} + (2^0)
[Die beiden Summenterme können nun als ein Summenterm geschrieben werden:]
= SUMME{k=0..(m-1)}{(m ÜBER k)*(2^(k+1)) + (m ÜBER (k+1))*(2^(k+1)) } + (2^(m+1)) + (2^0)
[(2^(k+1)) ausklammern:]
= SUMME{k=0..(m-1)}{((m ÜBER k)+(m ÜBER (k+1)))*(2^(k+1))} + (2^(m+1)) + (2^0)
[Gemäß Vorbemerkung 2 ist (m ÜBER k) + (m ÜBER (k+1)) = ((m+1) ÜBER (k+1)) :]
= SUMME{k=0..(m-1)}{((m+1) ÜBER (k+1))*(2^(k+1))} + (2^(m+1)) + (2^0)
[Beim Summenterm gemäß Vorbemerkung 3 Start- und Endwert der Laufvariablen k um 1 vergrössern
und die Argumente der Folgenglieder um 1 verkleinern:]
= SUMME{k=1..m}{((m+1) ÜBER k))*(2^k)} + (2^(m+1)) + (2^0)
[Gemäß Vorbemerkung 1b ist ((m+1) ÜBER (m+1)) = 1 :]
= SUMME{k=1..m}{((m+1) ÜBER k))*(2^k)} + ((m+1) ÜBER (m+1)(2^(m+1)) + (2^0)
[Der mittlere Summand kann in den Summenterm übernommen werden indem der Endwert der
Laufvariablen um 1 erhöht wird:]
= SUMME{k=1..(m+1)}{((m+1) ÜBER k))*(2^k)} + (2^0)
[Gemäß Vorbemerkung 1b ist ((m+1) ÜBER 0) = 1 :]
= SUMME{k=1..(m+1)}{((m+1) ÜBER k))*(2^k)} + ((m+1) ÜBER 0) *(2^0)
[Der hintere Summand kann in den Summenterm übernommen werden indem der Startwert
der Laufvariablen um 1 verkleinert wird:]
= SUMME{k=0..(m+1)}{((m+1) ÜBER k))*(2^k)}
Nun lassen wir die Umformungszwischenschritte der rechten Seite der Gleichung weg:
3^(m+1) = ... = SUMME{k=0..(m+1)}{((m+1) ÜBER k))*(2^k)}
3^(m+1) = SUMME{k=0..(m+1)}{((m+1) ÜBER k))*(2^k)}
Dies ist äquivalent zu:
3^n = SUMME{k=0..n}{(n ÜBER k) * (2^k)} mit n=(m+1)
QED
Ein gutes neuse Jahr wünschend
verbleibe ich mit
freundlichem Gruß
Ulrich