Proof (continued) Inductive step k k k anIn+(l-a n n k=1 ≤an(x)+(-an)∑,“xk k=1 Convexity c 2001 by Charles E Leiserson Introduction to Agorithms Day17L9.10© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.10 Proof (continued)   − ≤ + −   − = + −   ∑ ∑ ∑ − = − = = 1 1 1 1 1 1 ( ) (1 ) 1 (1 ) 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 x α α α α α α α α α Inductive step: Convexity