Can Every Number Be Expressed as a Sum of Fibonacci Numbers?

[SNOOTCHIEBOOCHEE]

Homework Statement

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

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?

 

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

 

[SNOOTCHIEBOOCHEE]

Well a number like k reapeated nines could not be expressed as a sum of k powers of ten.

But i don't really see the relationship between the two.

Also its for all K, there exists a arbitrarily large N such that ...

 

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

 

[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 anyone 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?

 

[SNOOTCHIEBOOCHEE]

Sorry I am still not getting it.

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

Is there another way?

 

[Dick]

Sorry I am still not getting it.

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

Is there another way?

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.

 

[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 I am 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?

 

[Dick]

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

 

[SNOOTCHIEBOOCHEE]

n-1 fibbs less than n?

 

[Dick]

n-1 fibbs less than n?

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

 

[SNOOTCHIEBOOCHEE]

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

?

 

[Dick]

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

?

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.

 

[SNOOTCHIEBOOCHEE]

ok

m= log (n)/ Log (P)

 

[Dick]

ok

m= log (n)/ Log (P)

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?

 

[SNOOTCHIEBOOCHEE]

m choose k

 

[Dick]

m choose k

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.

 

[SNOOTCHIEBOOCHEE]

so it would be m^k then.

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

 

[Dick]

so it would be m^k then.

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

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?

 

[SNOOTCHIEBOOCHEE]

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

 

[Dick]

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

There's an 'n' in both expressions. You can't, for example, just pick an n>n^2. You have show such a choice exists. There is something to prove.