Generalized Fibonacci Formula? Fibonacci Numbers Of Different Orders?

Discussion in 'Recreational Math' started by Patrick D. Rockwell, Nov 5, 2004.

  1. Awhile back, I read a problem in the Probability (Alt.Puzzles) FAQ. The idea
    was, if you tossed a penny N times, what was the probability that among
    those N times, there would be at least ONE occurance of HEADS two or
    more times in a row.

    For N tosses, the FAQ gave the answer as ((2^N)-Fib(N+2))/(2^N) where
    Fib(0)=0, Fib(1)=1, Fib(2)=1, Fib(3)=2, Fib(4)=3, Fib(5)=5, etc.

    For simplicity, lets just talk about occurances in N tosses were HEADS does
    NOT come two or more times in a row. That would be

    Fib(N+2)/(N^2)

    For 5 tosses, it would be 13/32. This would mean that in those 13 tosses,
    two heads were seperated by at least 1 tail toss.

    I then asked myself how many cases in N tosses could there be if there were
    at least TWO tails between any two consecutive head tosses. I counted them
    and the numbers came out like this.


    For at least 1 tail between any two occurances of heads, the number were
    like this.


    N # of ways that two head tosses have at least 1 tail toss
    between them.
    -- -------------------------------------------------------
    0 1
    1 2
    2 3
    3 5
    4 8
    5 13
    6 21
    7 34
    8 55
    9 89
    10 144



    If the number of tails between any two heads is at least 2, then the numbers
    are like this



    N # of ways that two head tosses have at least 2 tail tosses
    between them.
    -- ---------------------------------------------------------
    0 1
    1 2
    2 3
    3 4
    4 6
    5 9
    6 13
    7 19
    8 28
    9 41
    10 60



    If the number of tails between any two heads is at least 3, then the numbers
    are like this



    N # of ways that two head tosses have at least 3 tail tosses
    between them.
    -- ---------------------------------------------------------
    0 1
    1 2
    2 3
    3 4
    4 5
    5 7
    6 10
    7 14
    8 19
    9 26
    10 36



    If the number of tails between any two heads is at least 4, then the numbers
    are like this.

    N # of ways that two head tosses have at least 4 tail tosses
    between them.
    -- ---------------------------------------------------------
    0 1
    1 2
    2 3
    3 4
    4 5
    5 6
    6 8
    7 11
    8 15
    9 20
    10 25


    The patterns in the right columns are easy to see. The first case is just
    the Fibonacci numbers.

    Now, let F(n) be a function.

    In the second case, the pattern seems to be

    F(0)=0, F(1)=F(2)=1, F(N)=F(N-1)+F(N-3) for N>2.

    In the third case, the pattern has the function

    F(0)=0, F(1)=F(2)=F(3)=1, F(N)=F(N-1)+F(N-4) for N>3

    And in the fourth case we have

    F(0)=0, F(1)=F(2)=F(3)=F(4)=1, F(N)=F(N-1)+F(N-5) for N>4


    If you wanted to compute how many cases in N toses you would have at least
    ZERO tails between any two heads, this is easy.

    N # of ways that two head tosses have at least 0 tail tosses
    between them.
    -- ---------------------------------------------------------
    0 1
    1 2
    2 4
    3 8
    4 16
    5 32
    6 64
    7 128
    8 256
    9 512
    10 1024

    And the function here would be

    F(0)=1, F(N)=F(N-1)+F(N-1) for N>0

    I guess that what I want to know is, are there any books, web pages, or
    resources that talk about these patterns and other ways that they can be
    used? Are these patterns (other than the Fibbonacci sequence)
    considered Fibbonacci numbers of other orders?
     
    Patrick D. Rockwell, Nov 5, 2004
    #1
    1. Advertisements

  2. Patrick D. Rockwell

    mensanator Guest

    'So for N=5, you have
    '
    'F(5) = F(4) + F(0)
    ' = 1 + 0
    ' = 1
    '
    'Why does your table show 6 for N=5?
    '
     
    mensanator, Nov 5, 2004
    #2
    1. Advertisements

  3. Patrick D. Rockwell

    Henry Guest

    Henry, Nov 5, 2004
    #3
  4. Oops, I blew it by dropping a term in each of the above formulas. It should
    be the following.

    In the first case,

    F(0)=0, F(1)=F(2)=1, F(3)=F(N-1)+F(N-2) (Fibonacci Series)

    In the second case,

    F(0)=0, F(1)=F(2)=F(3)=1, F(N)=F(N-1)+F(N-3)

    In the third case,

    F(0)=0, F(1)=F(2)=F(3)=F(4)=1, F(N)=F(N-1)+F(N-4)

    In the fourth case,

    F(0)=0, F(1)=F(2)=F(3)=F(4)=F(5)=1, F(N)=F(N-1)+F(N-5)
    In each of the cases, you count the one where there are no heads. For
    example,


    TTTTT
    HTTTT
    THTTT
    TTHTT
    TTTHT
    TTTTH

    This is the case where any TWO heads are seperated by at least 5 tails. You
    can only do it if there are 1 or 0 heads.

    Sorry about my error.
     
    Patrick D. Rockwell, Nov 5, 2004
    #4
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.