11.6 Let the state space be a tree with uniform branching

b, and let the solution length be

d. For the special case b = 2 and d = 3, how many nodes are generated in the worst case by breadth-first search and by iterative deepening (counting regenerated nodes as well)? Denote by N(b,d) the number of nodes generated by iterative deepening in the general case. Find a recursive formula giving N(b,d) in terms of N(b,d-1).