Exponential height recurrence E=E∑Zm(2ma1,xk) k=1 ∑E[zmk( 2. maxlk-1,n- k k=1 22E[Znk ]. E[max(Yk-1, n-k] k=1 ∑E[Yk1+y=k 4∑E Each term appears k=0 twice and reindex c 2001 by Charles E Leiserson Introduction to Algorithms Day 17 L9. 22© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.22 Exponential height recurrence [ ] ( ) [ ] ( ) ∑ ∑ ∑ ∑ ∑ − = = − − = − − = − − = − − = ≤ + = ⋅ = ⋅   = ⋅ 1 0 1 1 1 1 1 1 1 1 [ ] 4 [ ] 2 2 [ ] [max{ , }] 2 max{ , } 2 max{ , } n k k n k k n k n k nk k n k n k nk k n k n k n nk k n k E Y n E Y Y n E Z E Y Y E Z Y Y E Y E Z Y Y Each term appears twice, and reindex