Sequence Pattern and Closed Form

Date: 7/16/96 at 3:19:18
From: Anonymous
Subject: Sequence Pattern and Closed Form

No. of Discs    1  2  3  4  5  6  7    8   9  10 
No. of moves    1  3  7  15 31 63 127 255 511 1023
                 ^  ^  ^  ^  ^  ^   ^   ^   ^
                 2  4  8  16 32 64  128 256 512

I had to continue the pattern after being told the first 4 numbers of
discs and moves. I figured out the rest by doubling the difference
between the moves bit and then realized that M is the difference minus
one. I cannot figure out the rule for the table though. 

I have spent ages on it but I can't do it. Could you help? (Please? :)
Thanks

Date: 7/16/96 at 11:24:13
From: Doctor Jodi
Subject: Re: Sequence Pattern and Closed Form

Hi there!  The number of moves, expressed in relation to the number of 
discs is

(2^(number of discs) )- 1

That is, 2 to the power of the number of discs minus 1.

Hope this helps.  Let us know if you have any other questions.

-Doctor Jodi,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 7/16/96 at 15:30:47
From: Doctor Anthony
Subject: Re: Sequence Pattern and Closed Form

If you had continued the difference table to another row, you would 
have found that you repeated the numbers 2, 4, 8, 16, 32, ...  When 
you have this situation you can be sure that if n is the number of the 
term, then n will be a power in the expression for the nth term.  By 
inspection the terms are generated by the function 2^n - 1

n   2^n -1
-----------
1     1
2     3
3     7
4     15
5     31 
-     -   and so on as we can see this function is generating the 
terms of the sequence.

-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/