Convexity lemma Lemma Let f: R>R be a convex function an nd let (ap,a2,.,an) be a set of nonnegative constants such that 2la= 1. Then, for any set x,x2,.,xn) of real numbers, we have ∑axk|s∑a/(x) k=1 k=1 Proof By induction on n. For n=1, we have I=l, and hence fax,sav( trivially c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.8© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.8 Convexity lemma Lemma. Let f : R → R be a convex function, and let {α1, α2 , …, αn} be a set of nonnegative constants such that ∑k αk = 1. Then, for any set {x1, x2, …, xn} of real numbers, we have ( ) 1 1 ∑ ∑ = = ≤  nk k k nk k k f α x α f x Proof. By induction on n. For n = 1, we have α1 = 1, and hence f(α1x1) ≤ α1f(x1) trivially.