# Homework Help: Sums of fibonacci numbers

1. Sep 30, 2008

### SNOOTCHIEBOOCHEE

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. Sep 30, 2008

### Dick

"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?

3. Sep 30, 2008

### SNOOTCHIEBOOCHEE

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 ...

4. Sep 30, 2008

### Dick

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?

5. Sep 30, 2008

### Dick

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?

6. Sep 30, 2008

### SNOOTCHIEBOOCHEE

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?

7. Sep 30, 2008

### Dick

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.

8. Oct 1, 2008

### SNOOTCHIEBOOCHEE

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?

9. Oct 1, 2008

### Dick

I'm suggesting the same method. So if n is a large number approximately how many Fibonacci's less than n?

10. Oct 1, 2008

### SNOOTCHIEBOOCHEE

n-1 fibbs less than n?

11. Oct 1, 2008

### Dick

??? 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
12. Oct 1, 2008

### SNOOTCHIEBOOCHEE

Ok.
(log(n))^m<n

?

13. Oct 1, 2008

### Dick

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.

14. Oct 1, 2008

### SNOOTCHIEBOOCHEE

ok

m= log (n)/ Log (P)

15. Oct 1, 2008

### Dick

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?

16. Oct 1, 2008

### SNOOTCHIEBOOCHEE

m choose k

17. Oct 1, 2008

### Dick

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.

18. Oct 1, 2008

### SNOOTCHIEBOOCHEE

so it would be m^k then.

would including zero make it (m+1)^k?

19. Oct 1, 2008

### Dick

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?

20. Oct 1, 2008

### SNOOTCHIEBOOCHEE

wouldnt we just have to choose some n larger than log(n) / log (p) ^k?