Induktion: ∑ [k=0 bis n] (n über k) mal 2^k = 3^n

Question

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

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)*2^k   =  3ⁿ + (n+1 über n+1)*2ⁿ⁺¹

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

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

Vielen lieben Dank schon mal!

Comments

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 2^k 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.

Answer 1

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)*2^k 

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 ) .

Comments

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)*2^k 

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

(n+1 über 0)*2⁰   +  ∑ [k=1 bis n] (n+1 über k)*2^k   +  (n+1 über n+1 )*2ⁿ⁺¹  

= 1  +  ∑ [k=1 bis n] (n+1 über k)*2^k     +  2ⁿ⁺¹  


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



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


Indexshift bei der ersten

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

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

und das  2ⁿ⁺¹  als letzten Summand in die erste

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


aus der 1. Summe eine 2 rausziehen

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

und die Ind. vor anwenden

=  2* 3ⁿ    +   3ⁿ    

   
=  3* 3ⁿ   =  3ⁿ⁺¹        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 (: