Question

(25) prove by induction that the Horner algorithon is correct

Answer 1

Proving Horner Correct PRE: val 0, i=n POST: valE=0" AU] x 1 2. 3. L: - this is the tricky part - hints: find something "in between" PRE and POST that incorporates the loop counter, i. at PRE, val(i) val(n) = 0 at POST, val(i) = val(-1) -0" AL] x look at example iterations to see what the pattern is start with this template, and we will fill in the ??: - AG] x? L: val(i) look at example iterations for j=n-3. The coefficients involved are A[n-2], A[n-1] and A[n]. So if we are referencing AG], then j in this summation ranges from n-2 to n; in general, this is i+1 to n: A] x? L: vali) Now we need the exponent of x. Look at the exponent for A[n] for successive iterations of i. It is x°, x1, x2 as i takes on the values (n-1), (n-2), and (n-3). The value of j at A[n] is n. Thus, in general, we could guess that the exponent is x-(i+1): L: val(i) i+1" A] x-(*+1) = You might also see this by just inspecting the examples: the sum is being built from the "end" of the polynomial towards the bottom Remember, L only has to be a guess. If you can't see from inspection that it's correct, that's all the more reason that we are proving correctness in the first place

Proving Horner Correct (cont'd) We didn't cover this in recitation. Prove L holds by induction: 4. at start of loop i=n L: val n+1.. = sum is empty, = 0 val is 0 in PRE, so it's [ok] Base: Show that if L holds for val(i) then it holds for val(i-1) Ind. step: in loop, val re-assigned: val A[i]xval(i Then i re-assigned to i-1, so this value is carried to next iter: val(i-1) A[i]x - val(i) By inductive hypothesis: val(i-1) A[i]x -£i.j" A] x-(i+1) Renaming "i" to "i+1": val(i) A[i+1x-£ei+2" AU] x-(i+2) Add x after A[i+1], move x inside summation: val(i) A[i+1] x +i+2" A[] x-(+1) Combine sum: val(i) - Σ->10 A1 x+1) [ok] At end of loop, i=-1. Εvaluate val(-1 ) = Σ-1+1" Αl xf1+1) = Σ- Α This is POST, so it proves correctness 5. 6. The loop terminates because i is initialized to n, then decremented on every loop iteration