Recurrence Relations

Publisher Summary This chapter presents the theory of recurrence relations. The tower of Hanoi puzzle, for example, involved the recurrence relation Sn+1 = 2Sn + 1. In this situation, the recurrence relation related the minimum number of moves required to transfer a tower of n + 1 rings in the puzzle to the minimum number of moves required to transfer a tower of n rings. The chapter also presents the difference methods. It present the introduction of some of the basic definitions and ideas of the subject called finite differences, and indicate how these ideas may be used to solve recurrence relations. The chapter presents the problem of finding the chromatic polynomial of a map or of its corresponding graph. The empty graph with n vertices is defined to be the graph with n vertices and no edges. The complete graph on n vertices is defined to be the graph on n vertices in which each pair of vertices is joined by an edge. A graph G is connected if there is a path joining every pair of distinct vertices in G.