Zeigen Sie, dass SUM-PROD für jede Eingabe n ∈ N den Wert Z =(n+1)!

Question

Algorithmus 2 SUM-PROD
Eingabe: n ∈ N
Rückgabe: Z ∈ R
1: P ← 1
2: S ← 0
3: Für k = 1, . . . , n
4: P ← P · k
5: P ← P/2
6: S ← S + k
7: [Ende] Für
8: Z ← S · P
9: Z ← Z/n
10: Gib Z zurück

Zeigen Sie, dass SUM-PROD für jede Eingabe \(n\in\N\) den Wert \(Z =(n+1)! / 2^{n+1}\) zurückgibt. Nutzen Sie
dazu vollständige Induktion.

Comments

Wahrscheinlich heisst es doch $$  Z = \frac{(n+1)!}{2^{n+1}} $$ oder?

---

ja genau so ist es

Answer 1

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.

Comments

Das ganze geht aber auch viel einfacher als der Code den Du da gepostet hast, siehe hier

Das einzige was passiert ist, ist eine Indexverschiebung.