Discussion:
sum(binomial(n,k)*2^k) =3^n
(zu alt für eine Antwort)
carlo berlingen
2020-12-29 17:06:11 UTC
Permalink
Wer kan mir einen Tip zur Durchführung des Induktionsschritts geben.
Danke schön
Carlo
Alfred Flaßhaar
2020-12-29 17:43:06 UTC
Permalink
Post by carlo berlingen
Wer kan mir einen Tip zur Durchführung des Induktionsschritts geben.
Danke schön
Carlo
(1+2)^n ?
Rainer Rosenthal
2020-12-29 17:45:47 UTC
Permalink
Post by carlo berlingen
Wer kan mir einen Tip zur Durchführung des Induktionsschritts geben.
Danke schön
Carlo
Schreib doch mal hin, wie es losgehen soll.
Zum Dran-Gewöhnen ist vielleicht das eine oder andere Beispiel auch
hilfreich. Dann weißt Du eher, was Du beweisen sollst.

Kannst Du den Ausdruck "sum(binomial(n,k)*2^k) = 3^n" für n = 2 so
schreiben, dass er ähnlich aussieht wie "x+y+z"?
Worüber wird da summiert? Über n oder über k? Und von welchem
Anfangswert bis zu welchem Endwert?

Gruß,
RR
Stephan Gerlach
2020-12-29 18:15:46 UTC
Permalink
Post by carlo berlingen
Wer kan mir einen Tip zur Durchführung des Induktionsschritts geben.
Da die Frage / Aufgabe / zu beweisende Aussage nicht richtig formuliert
ist, gibt's *diesen* Tip nicht.

Eine gute Formulierung wäre z.B. gewesen:

"... Man soll beweisen, daß für alle n Element |N

sum(binomial(n,k)*2^k) =3^n

gilt. Ich hatte mir gedacht, daß man das mit vollständiger Induktion
zeigen kann. Der Induktionsanfang ist klar, aber beim Induktionsschritt
komme ich nicht ganz weiter. Wer kan mir einen Tip zur Durchführung des
Induktionsschritts geben?"


Einen (anderen) Tip gibt's aber dennoch:
Die Aussage ist ein einfacher Spezialfall des binomischen Lehrsatzes.
Damit braucht man deine Aussage gar nicht zwingend mit Induktion
beweisen, sofern der binomische Lehrsatz vorausgesetzt werden darf.
--
Post by carlo berlingen
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Ulrich Diez
2021-01-04 11:19:07 UTC
Permalink
Post by Stephan Gerlach
"... Man soll beweisen, daß für alle n Element |N
sum(binomial(n,k)*2^k) =3^n
gilt.
Erbsenzählerei:

Die Angaben für Startwert und Endwert für die
"Laufvariable" k fehlen da immer noch.

Ulrich
Stephan Gerlach
2021-01-04 15:18:19 UTC
Permalink
Post by Ulrich Diez
Post by Stephan Gerlach
"... Man soll beweisen, daß für alle n Element |N
sum(binomial(n,k)*2^k) =3^n
gilt.
Die Angaben für Startwert und Endwert für die
"Laufvariable" k fehlen da immer noch.
Ach so, ja, stimmt.
Ich hatte einfach seine Formel per Copy&Paste aus dem Subjekt kopiert.
--
Post by Ulrich Diez
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Jens Kallup
2020-12-29 20:43:37 UTC
Permalink
Hallo,
Post by carlo berlingen
Wer kan mir einen Tip zur Durchführung des Induktionsschritts geben.
Danke schön
Carlo
also allgemein gilt ja für binomische Formel:

lhs = rhs
(a + b)^2 = a^2 + 2ab + b^2

n 2
- wobei das rechte 3 für das b steht,
- der Einfachheit ist n = 2:

1. Schritt: es ist zu zeigen, was:
n 2
3 = b ist:

2 2
3 = b | wurzel ziehen auf beiden Seiten
3 = b | somit haben wir b mit Wert 3

2 2
(a + b) = (2 + 3)
= 5 * 5
= 25

lhs = 25 Fertig mit Schritt 1,

2. Schritt:
2 2 2
= (a + b) = a + 2ab + b
= 4 + (2 * 2 * 3) + 3
= 4 + 18 + 3
= 25

3. Schritt: lhs und rhs gegenüber stellen:
lhs rhs
25 = 25

ok, stimmt.

Mit freundlichen Grüßen

Jens
Ulrich Diez
2021-01-01 02:16:11 UTC
Permalink
carlo berlingen schrieb zum Thema
sum(binomial(n,k)*2^k) =3^n
Post by carlo berlingen
Wer 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
Ulrich Diez
2021-01-04 20:52:48 UTC
Permalink
Ich schrob in der Silvesternacht:

[...]
Post by Ulrich Diez
Ab jetzt wird frohgemut der Term auf der rechten Seite der Gleichung
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:]
Das war zwar nicht falsch aber taktisch gesehen doof von mir, denn das
muss nach Zusammenfassen der beiden Summenausdrücke zu einem einzigen
Summenausdruck ja wieder rückgängig gemacht werden.

Es dürfte praktischer sein, beim vorderen Summenterm gemäß Vorbemerkung 3
Start- und Endwert der Laufvariablen k um 1 zu vergrössern und die Argumente
der Folgenglieder um 1 zu verkleinern - es kommt erwartungsgemäß das
gleiche heraus, aber man kann sich eine Umformung sparen:

= SUMME{k=1..m}{(m ÜBER (k-1))*(2^k)} + (2^(m+1)) + SUMME{k=1..m}{(m ÜBER k)*(2^k)} + (2^0)
[Die beiden Summenterme können nun als ein Summenterm geschrieben werden:]
= SUMME{k=1..m}{(m ÜBER (k-1))*(2^k) + (m ÜBER k)*(2^k)} + (2^(m+1)) + (2^0)
[(2^k) ausklammern:]
= SUMME{k=1..m}{((m ÜBER (k-1)) + (m ÜBER k))*(2^k)} + (2^(m+1)) + (2^0)
[Gemäß Vorbemerkung 2 ist (m ÜBER (k-1)) + (m ÜBER k) = ((m+1) ÜBER k) :]
= 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:

[...]

Ulrich
Roland Franzius
2021-01-05 12:33:08 UTC
Permalink
Post by carlo berlingen
Wer kan mir einen Tip zur Durchführung des Induktionsschritts geben.
Danke schön
for all n \in IN

Sum_(k \in IN ) (binomial(n,k) 2^k) =
Sum_(k \in IN) (binomial(n,k) 2^k 1^(n-k) ) = (1+3)^n = 3^n

mit /def: binomial(n,k) = coeff ( (1+x)^n , x^k )

und daher binomial(n,k) = 0 für k<0, k>n
--
Roland Franzius
Alfred Flaßhaar
2021-01-05 13:13:30 UTC
Permalink
Post by Roland Franzius
Post by carlo berlingen
Wer kan mir einen Tip zur Durchführung des Induktionsschritts geben.
Danke schön
for all n \in IN
Sum_(k  \in IN )  (binomial(n,k) 2^k) =
Sum_(k \in IN)  (binomial(n,k) 2^k 1^(n-k) ) = (1+_3_)^n  = 3^n
? 2 ? anstelle 3 ?
Post by Roland Franzius
mit /def:  binomial(n,k) = coeff ( (1+x)^n , x^k )
und daher binomial(n,k) = 0 für k<0, k>n
Roland Franzius
2021-01-05 20:03:40 UTC
Permalink
Post by Roland Franzius
Post by carlo berlingen
Wer kan mir einen Tip zur Durchführung des Induktionsschritts
geben. Danke schön
for all n \in IN
Sum_(k \in IN ) (binomial(n,k) 2^k) = Sum_(k \in IN)
(binomial(n,k) 2^k 1^(n-k) ) = (1+_3_)^n = 3^n
? 2 ? anstelle 3?
Sowas erregt unfehlbar die notwendigen Aufmerksamkeiten.
Post by Roland Franzius
mit /def: binomial(n,k) = coeff ( (1+x)^n , x^k )
und daher binomial(n,k) = 0 für k<0, k>n
--
Roland Franzius
Alfred Flaßhaar
2021-01-06 09:54:33 UTC
Permalink
Post by Roland Franzius
Wer kann mir einen Tip zur Durchführung des Induktionsschritts
geben. Danke schön
for all n \in IN
Sum_(k  \in IN )  (binomial(n,k) 2^k) = Sum_(k \in IN)
(binomial(n,k) 2^k 1^(n-k) ) = (1+_3_)^n  = 3^n
                                    ? 2 ? anstelle 3?
Sowas erregt unfehlbar die notwendigen Aufmerksamkeiten.
(...)
это доставляет мне удовольствие ;-)

Lesen Sie weiter auf narkive:
Suchergebnisse für 'sum(binomial(n,k)*2^k) =3^n' (Newsgroups und Mailinglisten)
5
Antworten
Fehler in MuPAD Funktion "sum"
gestartet 2008-08-10 08:09:32 UTC
de.sci.mathematik
10
Antworten
"n über k" und Fakultät
gestartet 2004-09-05 08:10:02 UTC
de.sci.mathematik
6
Antworten
Laufzeit von einem Algoritmus mit O(bin(n,k))
gestartet 2005-03-25 10:40:40 UTC
de.sci.informatik.misc
6
Antworten
schnell binomial verteilte Zufallszahlen erzeugen
gestartet 2007-05-09 20:53:13 UTC
de.sci.mathematik
Suchergebnisse für 'sum(binomial(n,k)*2^k) =3^n' (Fragen und Antworten)
4
Antworten
Wofür steht K-2SO?
gestartet 2016-12-16 10:51:47 UTC
filme
2
Antworten
K-Thermoelement, Instrumenten-Operationsverstärker und Arduino
gestartet 2019-08-14 23:17:40 UTC
elektronik
4
Antworten
Warum ändert sich der Dissoziationsgrad, wenn wir eine schwache Säure verdünnen, obwohl die Gleichgewichtskonstante konstant ist?
gestartet 2019-03-17 15:18:05 UTC
chemie
Nicht verwandte, aber interessante Themen
6
Antworten
Warum sind Raketen so groß?
gestartet 2013-11-28 02:00:59 UTC
6
Antworten
Gibt es eine Möglichkeit für einen Astronauten, sich zu drehen?
gestartet 2013-11-29 09:28:46 UTC
15
Antworten
Was ist der Sinn der Hamiltonschen Mechanik?
gestartet 2013-12-05 02:12:58 UTC
7
Antworten
Wie ist die Beziehung zwischen elektromagnetischer Welle und Photon?
gestartet 2013-12-18 15:59:54 UTC
7
Antworten
Ist es möglich, Nudeln bei Raumtemperatur mit ausreichend niedrigem Druck zu "kochen"?
gestartet 2013-12-29 12:26:25 UTC
Loading...