Für den Induktionsschritt betrachtest du erst mal die Summe
von k=1 bis 2^{n+1} - 1 (************)
Das ist die Summe
von k=1 bis 2n - 1 plus die Summe von k=2n bis 2n+1 - 1
Die erste Summe ist laut Induktionsvoraussetzung größer n-halbe
Die zweite Summe besteht aus 2n Summanden, die je größer als der
letzte sind. Also ist die 2. Summe größer als
2n / (2n+1 - 1) > 2n / 2n+1 = 1/2
Also ist die Summe (************) größer als n-halbe + 1/2
also größer als (n+1)-halbe.
Außerdem ist nach Ind.vor. die erste Summe kleiner n und die zweite
ist kleiner als 2n mal der erste Summand, also kleiner
als 2n / 2n = 1
Also beide zusammen (Das ist aber (**********) kleiner als n+1.
q.e.d.
