When I was a child I had this toy, that was a puzzle consisting of three pegs and approximately eight rings that varied in size and color (though the color was of no significance). Without any understanding of the rules, I would stack the rings miscellaneously with larger rings on top of smaller and vise verse, as well as moving multiple rings at one time. The actual object of this game is to convert the stack of rings, in order starting with the largest at the bottom and smallest on top respectively, from one peg to another moving only one ring at a time. The only other rule is that you can never at any point place a larger ring on top of a smaller ring. This tower of rings set on these pegs is known as the Tower of Hanoi.
When playing the Tower of Hanoi the objective is to make the least moves as possible when transferring the tower of rings from one peg to another. When using only two rings its easy to figure out the least amount of moves, but when the number of rings increase it gets difficult without using some type of formula. With a discussion of this subject in class we came to the conclusion for finding the least amount of moves given the number of rings. Let S(n) be the least number of moves to be made with n number of rings.
S(1) = 1
S(2) = (2 * S(1)) + 1 = (2 * 1) + 1 = 3
S(3) = (2 * S(2)) + 1 = (2 * 3) + 1 = 7
S(n) = (2 * S(n-1)) + 1
