Zeigen Sie (z.B. induktiv), dass Algorithmus tatsächlich für jedes n ∈ ℕdas Polynom pn(t) korrekt auswertet.

Question

Betrachten Sie das folgende Problem: Gegeben den Koeffizientenvektor

a = (a₀, a₁, . . . , a_n)T ∈ℝⁿ⁺¹ und t ∈ ℝ, werte das durch a definierte Polynom n-ten Grades

pn(x) := a_nx ⁿ + a_n−1x ⁿ⁻¹ + · · · + a₁x + a₀ = ∑ⁿ_k=0 a_kx^k
an der Stelle x = t aus.
Um dieses Problem zu lösen bekommen Sie die folgende  Algorithmus zur Verfügung gestellt:

Algorithmus Poly
Eingabe: a ∈ ℝⁿ⁺¹, t ∈ ℝ
Rückgabe: P = p_n(t)
1: P ← a_n
2: Für k = 1, . . . , n
3: P ← P · t + a_n−k
4: [Ende] Für
5: Gib P zurück

a.) Zeigen Sie (z.B. induktiv), dass Algorithmus tatsächlich für jedes n ∈ ℕdas Polynom p_n(t) korrekt auswertet.