0 Daumen
1,7k Aufrufe

∑ [k=0 bis n] (n über k)*2k = 3n

Ich soll dies durch Induktion beweisen, wobei ich auf große Probleme stoße.

Ich vermute allerdings, dass dies an einem falschen Beginn meines Induktionsschrittes liegen könnte, da die richtige Umformung mir unmöglich erscheint:

(IS):

n ---> n+1

∑ [k=0 bis n+1] (n über k)*2k   =  3n + (n+1 über n+1)*2n+1

n+1 über n+1 wäre dann ja 1 und dann weiß ich wirklich nicht, wie man noch auf 3n+1 kommen soll..


Wo liegt mein Fehler oder wie ist die Umformung möglich?


Vielen lieben Dank schon mal!

Avatar von

EDIT: Du hast in der Überschrift eine leicht andere Behauptung als im Fragetext.

Soll das n^k oben ein 2^k sein?

oh.. tut mir leid.. es sollte ein 2k sein

EDIT: Ok ich passe die Überschrift an und hoffe du hast mit mathefs Antwort die Aufgabe bereits geschafft.

Lass dir von mathef nichts einreden.

1 Antwort

+1 Daumen
 
Beste Antwort

Der Ansatz stimmt nicht ganz, ( siehe rot )

Das 2. n muss auch in n+1 geändert werden

∑ [k=0 bis n+1] (n+1 über k)*2k

und dann gibt es ja 

(n+1 über k) =  (n über k-1 ) +  (n über k)


und dann aus der Summe von 1 bis n zwei Summen machen

(oder noch mal nachfragen ) .
Avatar von 289 k 🚀
Tut mir leid, aber irgendwie verstehe ich das nicht so wirklich..
Müsste ich beim Aufteilen der Summe nicht wieso (n über k) haben, weil das aufgeteilte ja wieder ohne n+1 wäre..?
Blicke da irgendwie gar nicht durch bei der Erklärung..

klar, nach dem Aufteilen ist es so:

∑ [k=0 bis n+1] (n+1 über k)*2k 

Da das Aufteilen aber für K=0  und  k=n+1  nicht geht erst mal 

(n+1 über 0)*20   +  ∑ [k=1 bis n] (n+1 über k)*2k   +  (n+1 über n+1 )*2n+1  

= 1  +  ∑ [k=1 bis n] (n+1 über k)*2k     +  2n+1  


=  1  +  ∑ [k=1 bis n] ( (n über k-1 ) +  (n über k) )*2k         +  2n+1  



=  1  +  ∑ [k=1 bis n]  (n über k-1 ) *2k    +      ∑ [k=1 bis n]   (n über k) *2k   +  2n+1  


Indexshift bei der ersten

=  1  +  ∑ [k=0 bis n-1]  (n über k ) *2k+1    +      ∑ [k=1 bis n]   (n über k) *2k   +  2n+1  

und die vordere 1 packe in die 2. Summe als Summand mit k=0

und das  2n+1  als letzten Summand in die erste

=  ∑ [k=0 bis n]  (n über k ) *2k+1    +      ∑ [k=0 bis n]   (n über k) *2k     


aus der 1. Summe eine 2 rausziehen

=  2*∑ [k=0 bis n]  (n über k ) *2k   +      ∑ [k=0 bis n]   (n über k) *2k     

und die Ind. vor anwenden

=  2* 3n    +   3n    

   
=  3* 3n   =  3n+1        q.e.d.

Standardformeln müssen doch nicht bei jeder Aufgabe neu bewiesen werden.

Vielen Dank für die ausführliche Erklärung! Hat mir echt sehr geholfen (:

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community