1. Consider a search graph in which every state has exactly 6 successors. Argue that there are exactly 1+6 + 62 + 63 + 6' paths of length at most 4 starting with the start state. In general, if d is a...

Extracted text: 1. Consider a search graph in which every state has exactly 6 successors. Argue that there are exactly 1+6 + 62 + 63 + 6' paths of length at most 4 starting with the start state. In general, if d is a positive integer, then there are 1+6+6²+6³+. +6d paths of length at most d starting with the start state. You do not have to prove this, but it should be plausible now. Even more general, if b is the exact number of successors of each state, then there are 1+b+b?...+ paths of length at most d starting from the start state. Again, you do not have to prove this, but it should be plausible now.