Proof (continued) Inductive step kkk= n-n +(1 k X k=1 k n algebra c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.9© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.9 Proof (continued)   − = + −  ∑ ∑− = =1 1 11 (1 )nk k n k n n n nk k k f x f x x α α α α α Inductive step: Algebra