Proof (continued) Inductive step k k x+(l-a nn ak x1 k=1 k=1 ≤anf(xn)+(1-an)f k ≤anf(xn)+(1-an) D Wk k =∑akf(xk) Algebra k=1 c 2001 by Charles E Leiserson Introduction to Agorithms Day17L9.12© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.12 Proof (continued) ( ) ( ) 1 ( ) (1 ) 1 ( ) (1 ) 1 (1 ) 1 1 1 1 1 1 1 1 ∑ ∑ ∑ ∑ ∑ = − = − = − = = = − ≤ + −   − ≤ + −   − = + −   n k k k n k k n k n n n n k k n k n n n n k k n k n n n n k k k f x f x f x f x f x f x f x x α α α α α α α α α α α α α α Inductive step: . Algebra