Data Structures, Algorithms, & Applications in Java
Chapter 55, Exercise 1

(a)

When n > 0,
t(n) = (sum from j=0 to n-1) [t(j)] + n
= t(n-1) + (sum from j=0 to n-2) [t(j)] + n
= t(n-1) + t(n-1) - (n-1) + n
= 2t(n-1) + 1

(b)

Using the substitution method, we get
t(n) = 2t(n-1) + 1
= 2[2t(n-2) + 1] + 1
= 4t(n-2) + 2 + 1
= 4[2t(n-3) + 1] + 2 + 1
= 8t(n-3) + 4 + 2 + 1
.
.
.
= 2nt(0) + 2n-1 + ... + 22 + 21 + 1
= 2nc + 2n - 1
= O(2n)