Results 1 to 4 of 4

Math Help - Number sequences and exponents

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    1

    Number sequences and exponents

    I'm pretty new to this site, so if this is in the wrong section (I think it is), please tell me what to do!

    First off, I need a better way to word all this...but mostly I'm just looking for an explanation to this:
    The difference between integers to the 1st power is 1.
    1^1-0^1=1

    The difference between the difference between integers to the 2nd power is 2.
    2^2-1^2=3
    1^2-0^2=1

    3-1=2

    The difference between the difference between the difference between integers to the 3rd power is 6.
    3^3-2^3=19
    2^3-1^3=7
    1^3-0^3=1

    19-7=12
    7-1=6

    12-6=6

    And, the difference between the difference between the difference between the difference between 4th power is 24.
    4^4-3^4=175
    3^4-2^4=65
    2^4-1^4=15
    1^4-0^4=1

    175-65=110
    65-15=50
    15-1=14

    110-50=60
    50-14=36

    60-36=24

    If the exponent for the example above is n, then n! is the result (from what I can tell). Why?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Starting with a sequence a_0, a_1, ..., a_n.
    Continuing to do the difference the way you showed gives the same result as:
    \sum_{k=0}^n \binom{n}{k}(-1)^ka_k

    Why? Draw a graph corresponding to the subtraction. Something like (for your 3rd power case):
    19
    \
    12
    / \
    7 6
    \ /
    6
    /
    1

    [doesn't really look nice since spaces are removed]

    The number of times an initial number in the sequence is added or subtracted is the number of paths from that number to the answer. It is positive or negative depending on (even/odd) parity of how many up edges are taken.

    Now:
    You are starting with the sequence: n^n, (n-1)^n, ..., 1^n, 0^n
    So the answer after doing the differencing is:
    \sum_{k=0}^n \binom{n}{k}(-1)^k(n-k)^n

    This is the same as n! by a simple counting argument with inclusion-exclusion.

    Consider the set of all words of length n over an alphabet of n characters, call this W.

    n! counts the number of words in W with no repeating characters.

    \sum_{k=0}^n \binom{n}{k}(-1)^k(n-k)^n counts all words in W, then subtracts all words that only use at most n-1 characters (which requires inclusion exclusion).

    These two statements count the same thing.
    Last edited by snowtea; January 5th 2011 at 08:28 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Master Of Puppets
    pickslides's Avatar
    Joined
    Sep 2008
    From
    Melbourne
    Posts
    5,236
    Thanks
    28
    Similar to snowtea, its a start

    \displaystyle \sum_{i=1}^n (-1)^{2i+1}\times (i^i-(i-1)^i) = n!
    Last edited by pickslides; January 5th 2011 at 08:15 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Quote Originally Posted by snowtea View Post
    Why? Draw a graph corresponding to the subtraction. Something like (for your 3rd power case):
    19
    \
    12
    / \
    7 6
    \ /
    6
    /
    1

    [doesn't really look nice since spaces are removed]
    My ascii diagram in the above post would look better in a code block (unfortunately it is too late to edit):

    Code:
    19
      \
      12 
     /  \
    7    6
     \  /
      6
     /
    1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number sequences
    Posted in the Algebra Forum
    Replies: 5
    Last Post: June 6th 2010, 06:20 AM
  2. RSA and number of decryption exponents
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 17th 2010, 11:24 AM
  3. Number sequences
    Posted in the Algebra Forum
    Replies: 7
    Last Post: February 16th 2009, 06:14 AM
  4. mixed number exponents
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 20th 2008, 06:47 AM
  5. Puzzling Number Sequences
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: February 16th 2007, 04:02 PM

Search Tags


/mathhelpforum @mathhelpforum