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 2^n - 1 plus die Summe von k=2^n bis 2^{n+1} - 1
Die erste Summe ist laut Induktionsvoraussetzung größer n-halbe
Die zweite Summe besteht aus 2^n Summanden, die je größer als der
letzte sind. Also ist die 2. Summe größer als
2^n / (2^{n+1} - 1) > 2^n / 2^{n+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 2^n mal der erste Summand, also kleiner
als 2^n / 2^n = 1
Also beide zusammen (Das ist aber (**********) kleiner als n+1.
q.e.d.
