Den Induktionsanfang für \( n = 1 \) kannst Du wahrscheinlich nachvollziehen?
Der Algorithmus definiert die Folgen
$$ s_{n+1} = s_n +n+1 $$ und $$ p_{n+1} = p_n \frac{n+1}{2} $$
Für \( p_n \) ergibt sich daraus \( p_n = \frac{n!}{2^n} \)
Das Ergebnis berechnet sich aus $$ z_n = \frac{s_n p_n} {n} $$
Der Induktionsschluss lautet jetzt wie folgt
$$ z_{n+1} = \frac{ s_{n+1} p_{n+1} } { n+1} = \frac{( s_n + n+ 1 ) p_n \frac{n+1}{2}}{ n+1 } = \frac{ s_n p_n + p_n(n+1) }{ 2 } $$
Wegen der I. V. folgt
$$ z_{n+1} = \frac{ \frac{(n+1)! \cdot n }{2^{n+1} } + \frac{n!}{2^n} \cdot (n+1) } { 2 } = \frac{(n+2)!}{2^{n+2}} $$ was zu beweisen war.
