Motivated by the recurrence relation satisfied by the 4-peg tower of the Hanoi Problem, Matsuura [1] has considered the generalized recurrence relation of the form where a and ß are natural numbers, and S(t, 3) = 2t - 1 is the solution of the 3-peg Tower of Hanoi problem with t discs. This paper studies more closely the above recurrence relation and gives some new relationships, including some local-value relationships. The Reve's puzzle is a particular case of the above recurrence relation with a = 2.