SKEDSOFT

In doing so, we will use the identity

(Exercise 12.4-1 asks you to prove this identity.)

For the base case, we verify that the bound

holds. For the substitution, we have that

We have bounded E[Y_n], but our ultimate goal is to bound E[X_n]. As Exercise 12.4-4 asks you to show, the function f(x) = 2^x is convex (see page 1109). Therefore, we can apply Jensen's inequality , which says that

to derive that