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

  • Thread starter Thread starter SNOOTCHIEBOOCHEE
  • Start date Start date
  • Tags Tags
    Numbers Sums
Click For Summary

Homework Help Overview

The discussion revolves around the problem of whether every number can be expressed as a sum of Fibonacci numbers. The original poster presents a statement about the existence of arbitrarily large numbers that cannot be expressed as a sum of a given number of Fibonacci numbers, seeking insights on how to demonstrate this without providing a formal proof.

Discussion Character

  • Exploratory, Assumption checking, Mathematical reasoning

Approaches and Questions Raised

  • Participants explore the concept of expressing numbers as sums of Fibonacci numbers and draw parallels to powers of ten. They discuss the challenges of showing the existence of numbers that cannot be expressed in such forms, questioning the relationship between Fibonacci numbers and geometric series.

Discussion Status

The discussion is ongoing, with participants offering hints and alternative perspectives. Some suggest methods involving logarithmic comparisons and combinatorial counting, while others express confusion about the connections being made. There is no clear consensus, but several lines of reasoning are being explored.

Contextual Notes

Participants are working under the constraint of not providing formal proofs, which adds complexity to their discussions. They also reference specific numerical examples and properties of Fibonacci numbers, indicating a focus on theoretical exploration rather than concrete solutions.

SNOOTCHIEBOOCHEE
Messages
141
Reaction score
0

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?
 
Last edited:
Physics news on Phys.org
"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?
 
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 ...
 
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?
 
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?
 
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?
 
SNOOTCHIEBOOCHEE said:
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.
 
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?
 
I'm suggesting the same method. So if n is a large number approximately how many Fibonacci's less than n?
 
  • #10
n-1 fibbs less than n?
 
  • #11
SNOOTCHIEBOOCHEE said:
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.
 
Last edited:
  • #12
Ok.
(log(n))^m<n

?
 
  • #13
SNOOTCHIEBOOCHEE said:
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.
 
  • #14
ok

m= log (n)/ Log (P)
 
  • #15
SNOOTCHIEBOOCHEE said:
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?
 
  • #16
m choose k
 
  • #17
SNOOTCHIEBOOCHEE said:
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.
 
  • #18
so it would be m^k then.

would including zero make it (m+1)^k?
 
  • #19
SNOOTCHIEBOOCHEE said:
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?
 
  • #20
wouldnt we just have to choose some n larger than log(n) / log (p) ^k?
 
  • #21
SNOOTCHIEBOOCHEE said:
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.
 

Similar threads

Each integer n>11 can be written as the sum of two composite numbers?
  • · Replies 7 ·
Replies
7
Views
4K
How to prove that every third Fibonacci number is even?
  • · Replies 1 ·
Replies
1
Views
4K
Mathematical Induction Problem Fibonacci numbers
  • · Replies 11 ·
Replies
11
Views
4K
Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Direct Proof that every zero of p(T) is an eigenvalue of T
  • · Replies 24 ·
Replies
24
Views
4K
Sum of a rational number and an irrational number ....
  • · Replies 2 ·
Replies
2
Views
3K
Proving the Existence of a Number with n Divisors
  • · Replies 18 ·
Replies
18
Views
3K
Finding GCD with Fibonacci: Base Case
  • · Replies 1 ·
Replies
1
Views
2K
Every positive real number has a unique positive n'th root
  • · Replies 8 ·
Replies
8
Views
5K
Can Irrational Numbers Be Found Between Any Two Real Numbers?
  • · Replies 8 ·
Replies
8
Views
2K