Proof (continued) Inductive step ∑axk=1anxn+(1 dk xk k=1 n ≤anf(xn)+(1- an) ak xk k=1 n ≤anf(xn)+(1-an)∑,f(x k=1 Induction c 2001 by Charles E Leiserson Introduction to Agorithms Day17L9.11© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.11 Proof (continued) ∑ ∑ ∑ ∑ − = − = − = = − ≤ + −   − ≤ + −   − = + −   1 1 1 1 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 n k n n n n k k k f x f x f x f x f x f x x α α α α α α α α α α α α α Inductive step: Induction