Results 1 to 4 of 4

Thread: Determining the formula of this sequence?

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    168

    Determining the formula of this sequence?

    I was given the sequence
    0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, ...
    and I'm looking for a method to determine an explicit formula for this.
    I've tried doing difference columns, and I always end up with 2^n being the 2nd difference.

    Anyone know a way to figure this out?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by paupsers View Post
    I was given the sequence
    0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, ...
    and I'm looking for a method to determine an explicit formula for this.
    I've tried doing difference columns, and I always end up with 2^n being the 2nd difference.

    Anyone know a way to figure this out?
    Good idea to look at differences. So you found:

    $\displaystyle (u_{n+2}-u_{n+1})-(u_{n+1}-u_n)=2^n$,

    assuming the first term is $\displaystyle u_1=0$.

    If you sum the above equalities for $\displaystyle n$ ranging from 1 to $\displaystyle n$, you get a telescoping sum on the left, and a geometric sum on the right, which leads to:

    $\displaystyle (u_{n+2}-u_{n+1})-(u_2-u_1)=2+2^2+\cdots +2^n = 2^{n+1}-2$,

    hence

    $\displaystyle u_{n+2}-u_{n+1}=2^{n+1}-1$.

    Summing again this latter equality we have again a telescoping sum on the left and a geometric sum (minus constant terms) on the right, and we get:

    $\displaystyle u_{n+2}-u_2=(2^2-1)+\cdots+(2^{n+1}-1)$,

    hence (change of variable)

    $\displaystyle u_n = (2^2-1)+\cdots +(2^{n-1}-1)+1$

    and finally $\displaystyle u_n=2^n-n-1$. Same method works in many situations.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by paupsers View Post
    I was given the sequence
    0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, ...
    and I'm looking for a method to determine an explicit formula for this.
    I've tried doing difference columns, and I always end up with 2^n being the 2nd difference.

    Anyone know a way to figure this out?
    The Encyclopaedia of Integer Sequences gives: $\displaystyle 2^n-n-1$

    CB
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, paupsers!

    Given the sequence: .$\displaystyle 0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, \hdots$

    I'm looking for a method to determine an explicit formula for this.
    I've tried doing difference columns, and I always end up with 2^n being the 2nd difference.
    This is true . . . and should give you a big hint.
    Consider the general form: .$\displaystyle f(n) = 2^n$

    How does it compare with the given sequence?

    $\displaystyle \begin{array}{c|cccccccccc}\hline
    n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
    \text{Sequence:} & 0 & 1 & 4 & 11 & 26 & 57 & 120 & 247 & 502 & 1013 \\ \hline
    f(n) = 2^n & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 & 1024 \\ \hline
    \text{Error:} & +2 & +3 & +4 & +5 & +6 & +7 & +8 & +9 & +10 & +11\\ \hline
    \end{array}$


    If we use $\displaystyle f(n) = 2^n$, each term is too large by $\displaystyle (n+1)$

    Therefore, the explicit formula is: .$\displaystyle F(n) \;=\;2^n - (n+1)$

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Determining Formula for a graph
    Posted in the Algebra Forum
    Replies: 23
    Last Post: Jun 13th 2011, 07:13 PM
  2. determining formula for sequences.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Dec 14th 2008, 10:33 AM
  3. sequence formula
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Oct 28th 2007, 06:47 AM
  4. Geometric Sequence, Determining common ratio.
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Sep 19th 2007, 10:20 PM
  5. Help on determining a probability formula
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: Jun 30th 2006, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum