vollständige Induktion. Beweise Summe(2^{k-1}(j-k)) = 2^j - (j+1)

Question

kann mir jemand helfen ?

Comments

Vollständige Induktion: Zeige Summe(2^{k-j}(j-k)) = 2^j - (1+j) 

kann mir jemand bei dieser Aufgabe helfen

ich muss zeigen ,dass es für alle j aus natürlichen zahlen und 0 gilt

---

Was ist "und"? Meinst du wirklich: 

" ich muss zeigen ,dass es für alle j aus natürlichen zahlen mit (?) 0 gilt " 

natürlichen zahlen und 0 ist das ℕ_(0) 

---

Ja , genau . Der Induktionsanfang für j = 0 und j = 1 ist klar ich habe aber Probleme mit Induktionsschritt

---

Beim Summenzeichen kann man doch j=0 und j=1 gar nicht einsetzen (?).

0-1 wäre ja -1 über dem Summenzeichen.

1-1 wäre 0 über dem Summenzeichen.

Dann hast du links gar keine Summe.

Das passt eigentlich nicht zu einer Induktionsverankerung.

---

Schau mal hier: https://www.mathelounge.de/391658/vollstandige-induktion-beweise-summe-2-k-1-j-k-2-j-j-1

---

1. Eine formale Erweiterung des Summenzeichens ist die leere Summe: Eine Summe bei der der obere Summationsindex kleiner als der untere Summationsindex ist, heißt leere Summe. Die leere Summen wird als 0 definiert.

aber das ist nicht das Problem.

Ich habe Problem mit Induktionsschritt , da j auch in Summe auftaucht und ich weiß nicht wie es rechnen

---

Der Induktionsschritt ist doch im Link in meinem Kommentar  schon vorgerechnet (?)

---

Danke . Nur habe eine Frage : wo ist 2^j-1 nach der InduktionsVoraussetzung ?

---

BIn zurechtgekommen . Vielen Dank

Answer 1

j=1      2⁰ ( 1-1) =  2¹ - ( 1+1 )

             1*0  =  2 - 2     passt !

wenn es für j stimmt, dann gilt  (jetzt kommt der Induktionsschritt)

Summe k=1 bis j  über   2 ^k-1* ( j+1 - k )

=   Summe k=1 bis j-1  über   2 ^k-1* ( j+1 - k )         +   2^j-1 * ( j+1 - j ) 

  =    Summe k=1 bis j-1  über   2 ^k-1* ( j - k )   +   2 ^k-1      +   2^j-1 *1

= Summe k=1 bis j-1  über   2 ^k-1* ( j - k )   +  Summe k=1 bis j-1  über   2 ^k-1       +   2^j-1 

Ind.vor.

=   2 ^j - ( j+1)        +  Summe k=1 bis j  über   2 ^k-1    

Formel für geom. Reihe

=   2 ^j - ( j+1)    +    2^j  -  1

=  2* 2 ^j - ( j+1)    - 1  

=   2 ^j+1 - ( j+2)       q.e.d.

Comments

Ich verstehe "  =    Summe k=1 bis j-1  über   2 ^k-1* ( j - k )   +   2 ^k-1      +   2^j-1 *1 

" nicht, wie sie es aufgespalten habe. Das ist die zweite Zeile.Können Sie mir es bitte erklären ?

---

In der Summe in der Zeile vorher waren die Summanden ja

2 ^k-1* ( j+1 - k )     bzw 


2 ^k-1* ( j - k   +   1   )   Da löse ich die Klammer auf

= 2 ^k-1   * ( j - k )  +    2 ^k-1   *    1   )   
und dann zwei Summen draus machen

---

wo ist 2^{j-1} nach der InduktionsVoraussetzung ?

---

alleniv: Meinst du diesen Übergang:

= Summe k=1 bis j-1  über   2 ^k-1* ( j - k )   +  Summe k=1 bis j-1  über   2 ^k-1       +   2^j-1  

Ind.vor. 

=   2 ^j - ( j+1)        +  Summe k=1 bis j  über   2 ^k-1     

oder was genau?