Fibonacci Numbers problem

Discussion in 'General Math' started by Gregor Rot, Jun 4, 2004.

  1. Gregor Rot

    Gregor Rot Guest

    Hi,
    can somebody give a quick look at this please or give me some direction
    on where to start looking for an answer:

    if F is a Fibonacci number, then F+F! is not a fib. num. for every F>2.

    can this be proven or discarded? (i have proven that this is true for
    2<F<13 with a computer program...)

    tnx & best regards,
    Greg
     
    Gregor Rot, Jun 4, 2004
    #1
    1. Advertisements

  2. Gregor Rot

    mensanator Guest

    As F gets larger than 13, F! has a lot of 0s at the least significant
    end. The number of 0s grows faster than the number of digits in F, so
    F+F! will always have a large block of 0s near the end:

    fib( 3 ) F = 2 F+F! = 4

    fib( 4 ) F = 3 F+F! = 9

    fib( 5 ) F = 5 F+F! = 125

    fib( 6 ) F = 8 F+F! = 40328

    fib( 7 ) F = 13 F+F! = 6227020813

    fib( 8 ) F = 21 F+F! = 51090942171709440021

    fib( 9 ) F = 34 F+F! = 295232799039604140847618609643520000034

    fib( 10 ) F = 55 F+F! = 126964033536582759259651008475665169595
    80321051449436762275840000000000055

    fib( 11 ) F = 89 F+F! = 165079551609084610812169192624536193098
    396662364965418549135207078331710343785
    097393999125707876006627290803829997568
    00000000000000000089

    fib( 12 ) F = 144 F+F! = 555029383273930478955105466055038811799
    998233798276287134307090377320974050790
    704421276194399889413260302964296757872
    427457316014932181834187890765109349598
    440792631659305387180597679852465879035
    748838374340208623616000000000000000000
    0000000000000144

    fib( 13 ) F = 233 F+F! = 968809831240356376446281914271190327334
    107057668048414184152255617657628042106
    246294812244303200295111425862828673485
    601051835270884773253711866852861601188
    768943382892452021980925745460719696427
    232466166178676782029223606651121637220
    993214743432304045990309249378880272995
    523981542654688543556375105349248612473
    099703897904439784234170968006523472643
    833033511643549004183981614317813988279
    189504000000000000000000000000000000000
    00000000000000000000233

    fib( 14 ) F = 377 F+F! = 173390762804963682280963013249611013170
    341292992200637801434962810134891656936
    121867937405784206486063735883850848325
    569811737682295353377418731015936381895
    677892102150821499226962504473571595882
    502354288526561899077132329477060250494
    456333822786887608823182972623045480444
    044059432476830764132960484124809213765
    123254482597336257153716741988107634581
    520917060471892755220271392894414285980
    677901283621626324363341092310704549040
    327024721242410439986884650635387024976
    616790735511337879009694503244041595957
    720190902231038805717448222737188483373
    349859366433199967091287273497186627453
    324946035413694255509804386043827970306
    634400453126660493640550652685368972763
    588696835839983636035046044255592448628
    147864064753664000000000000000000000000
    000000000000000000000000000000000000000
    000000000000000000000000000377

    I don't know if you can prove that a Fibonacci number can't have that
    many 0s at the end, but I know it's true for:

    fib( 3 ) F = 2 F+F! does not match any fib() up to fib( 5 )
    fib( 4 ) F = 3 F+F! does not match any fib() up to fib( 7 )
    fib( 5 ) F = 5 F+F! does not match any fib() up to fib( 12 )
    fib( 6 ) F = 8 F+F! does not match any fib() up to fib( 24 )
    fib( 7 ) F = 13 F+F! does not match any fib() up to fib( 49 )
    fib( 8 ) F = 21 F+F! does not match any fib() up to fib( 96 )
    fib( 9 ) F = 34 F+F! does not match any fib() up to fib( 186 )
    fib( 10 ) F = 55 F+F! does not match any fib() up to fib( 352 )
    fib( 11 ) F = 89 F+F! does not match any fib() up to fib( 654 )
    fib( 12 ) F = 144 F+F! does not match any fib() up to fib( 1197 )
    fib( 13 ) F = 233 F+F! does not match any fib() up to fib( 2165 )
    fib( 14 ) F = 377 F+F! does not match any fib() up to fib( 3874 )
    fib( 15 ) F = 610 F+F! does not match any fib() up to fib( 6873 )
    fib( 16 ) F = 987 F+F! does not match any fib() up to fib( 12102 )
    fib( 17 ) F = 1597 F+F! does not match any fib() up to fib( 21171 )
    fib( 18 ) F = 2584 F+F! does not match any fib() up to fib( 36833 )
    fib( 19 ) F = 4181 F+F! does not match any fib() up to fib( 63771 )
    fib( 20 ) F = 6765 F+F! does not match any fib() up to fib( 109942 )
     
    mensanator, Jun 5, 2004
    #2
    1. Advertisements

  3. Gregor Rot

    Gregor Rot Guest

    Thank you for your answer, it's a start...

    br,
    Gregor
     
    Gregor Rot, Jun 5, 2004
    #3
  4. Gregor Rot

    FJ Guest

    what about this?

    we have that, for a fib. number F_n,

    F_n = F_(n-1) + F_(n-2).

    so assume that F_n + F_n! is a fib. number, then it must follow the
    recursion

    F_n + F_n! = F_(n-1) + F_(n-1)! + F_(n-2) + F_(n-2)! = F_n + F_(n-1)!
    + F_(n-2)!.

    cancelling out F_n from both sides gives

    (*) F_n! = (F_(n-1) + F_(n-2))! = F_(n-1)! + F_(n-2)!.

    this is equivalent to trying to show that (x + y)! = x! + y!. now you
    have simplified the matter to proving that (*) cannot be true.

    hope that helps.

    -FJ
     
    FJ, Jun 14, 2004
    #4
  5. Gregor Rot

    FJ Guest

    i came up with a proof today, so please check this over for errors.

    assume that (x + y)! = x! + y!, and let y>x arbitrarily.

    then for the left side we have x! \prod_{m=x+1}^{x+y} m = x!
    \prod_{m=1}^y (x+m). now moving x! from the right to the left gives

    x! (\prod_{m=1}^y (x+m) - 1) = y!, or,

    \prod_{m=1}^y (x+m) = y!/x! + 1.

    now, for brevity, let z = (x+1)(x+2)...(x+y). then we have

    z(y+1)...(x+y) = (z+1)/z.

    the left side is an integer for all values of x and y integers, but
    the left side is not. since x,y>0, we can only have z=1, but then
    this is impossible since x and y are integers. therefore we have a
    contradiction and our assumption is false.

    lastly, if we consider the case x=y instead of y>x, then our
    assumption tells us that

    (2x)! = 2 x!
    (2x)(2x-1)! = 2x(x-1)!, and cancelling out 2x gives
    (2x-1)!=(x-1)!, which is clearly false. so our assumption fails
    again.

    therefore, if (x + y)! = x! + y! is false for all non-negative
    integers x and y, then it can't be true for fib. numbers. therefore,
    F_n + F_n! can't be a fib. number.

    hope that is right.

    FJ
     
    FJ, Jun 14, 2004
    #5
    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.