1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sums of fibonacci numbers

  1. Sep 30, 2008 #1
    1. The problem statement, all variables and given/known data

    Show (without proof) : For every k, there exists a arbitrarily large n that are not the sum of k fibbonacci numbers.

    3. The attempt at a solution


    Really i am pretty lost here.

    I tried to do a proof by induction, but this didnt work.

    Then i realized i am not supposed to do a proof, and have no clue how to show this is true otherwise.

    Any thoughts?
     
    Last edited: Sep 30, 2008
  2. jcsd
  3. Sep 30, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    "Showing without proof" is a little tricky. Here's a hint. Suppose instead of the Fibonacci numbers you were given the numbers {1,10,100,1000,10000...}. Can you show for every k there is a number so large it can't be expressed as a sum of k powers of ten? Now, what property of the Fibonacci numbers makes them similar to the powers of ten?
     
  4. Sep 30, 2008 #3
    Well a number like k reapeated nines could not be expressed as a sum of k powers of ten.

    But i dont really see the relationship between the two.

    Also its for all K, there exists a arbitrarily large N such that ...
     
  5. Sep 30, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I was thinking more of a number with repeated ones, but sure. It's pretty clear it's true without writing a formal proof. The powers of ten are a geometric series. Is the Fibonacci series "like" a geometric series?
     
  6. Sep 30, 2008 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Let's try and actually prove something in powers of ten case, ok? If n is a large number then there are approximately log(n) (log base 10) powers of 10 less than n. For each of the k numbers we can choose any one of those log(n) numbers. So the number of choices we can make is (log(n))^k. Can you show that for any k there is an n such that (log(n))^k<n?
     
  7. Sep 30, 2008 #6
    Sorry im still not getting it.

    i know that fn = (golden ratio)^n but i dont really see how to do this.

    Is there another way?
     
  8. Sep 30, 2008 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Maybe there's another way but I don't know what it is. You tell me. Call Tn the set of the powers of ten less than n. IF you can prove that for sufficiently large n that the number of ways of selecting k members of Tn is less than n, wouldn't that prove it? And, yes, Fn~(golden ratio)^n. If you have a proof for the powers of ten, then you should be able to see how to handle the fibonaccis. Modulo details.
     
  9. Oct 1, 2008 #8
    In class he did a method (by counting) to show that there exist numbers that are not the sum of 2 fibb numbers.

    That is.

    ther eare only 11 fibb numbers <200 so if 200>= n = fn+fs <= 144

    201 choices... 12 choices each

    at least 57 #'s <200 are not the sums of 2 fibbs... not sure if this can be used.

    Using your method im guessing we would have to take some Mod 10 of Tn.

    and show that K choose Tn < n.

    Also applying this method to the fibbonaci one, what modulus base would i have to use? did i even pic the right one for the powers of 10?
     
  10. Oct 1, 2008 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I'm suggesting the same method. So if n is a large number approximately how many Fibonacci's less than n?
     
  11. Oct 1, 2008 #10
    n-1 fibbs less than n?
     
  12. Oct 1, 2008 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    ??? Where did that come from? You said that the mth Fibonacci fm is approximately P^m (where P is the golden ratio). So to find the number of fm's less than n you want to solve fm=P^m=n.
     
    Last edited: Oct 1, 2008
  13. Oct 1, 2008 #12
    Ok.
    (log(n))^m<n

    ?
     
  14. Oct 1, 2008 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    This isn't going very well. Solve P^m=n for m. Take the log of both sides and solve for m. Review a chapter on logs if you have to.
     
  15. Oct 1, 2008 #14
    ok

    m= log (n)/ Log (P)
     
  16. Oct 1, 2008 #15

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That's better. So m is approximately the number of fibonacci's less than n. How many ways are there to choose k of them?
     
  17. Oct 1, 2008 #16
    m choose k
     
  18. Oct 1, 2008 #17

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Nope. That's the number of ways to choose k DIFFERENT numbers. These k numbers don't all have to be different. Count by choosing the numbers one at a time. How many choices for the first number? How many choices for the second? Etc. (This is actually counting the number of ordered choices, the number of unordered choices is actually less, but that's ok. Since we are going to show the number of choices is too small anyway.) Come think of it, you don't have to choose k numbers either. You could choose less than k. Let's fix that by making 0 one of the options for a choice as well.
     
  19. Oct 1, 2008 #18
    so it would be m^k then.

    would including zero make it (m+1)^k?
     
  20. Oct 1, 2008 #19

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Right, but you'll see the +1 doesn't make much difference, and m is only the approximate number of fibonacci's anyway. Let's just go with m^k. Now can you show you can find an n large enough that m^k=(log(n)/log(P))^k<n?
     
  21. Oct 1, 2008 #20
    wouldnt we just have to choose some n larger than log(n) / log (p) ^k?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Sums of fibonacci numbers
  1. Fibonacci Numbers (Replies: 7)

  2. Fibonacci Numbers (Replies: 1)

  3. Fibonacci Numbers (Replies: 0)

  4. Fibonacci numbers (Replies: 1)

Loading...