The existence of such a representation is not so difficult to imagine once you know any integer can be written as the sum of distinct Fibonacci numbers, as you can see that the densest sum F(2)+F(3)+F(4)+F(5)+F(6)+F(7)+... can change into F(4)+F(6)+F(8)+... as desired. The proof of the uniqueness, however, is a little formal since it often requires a non-constructive argument.
Proof of uniqueness can be done constructively.
Let's say n is an integer with F(m)≤n<F(m+1). Then F(m) must be a summand of n. Otherwise, n is at most:
● F(m-1)+F(m-3)+...+F(2), but n≥F(m)=F(m-1)+F(m-3)+...+F(2)+1, or
● F(m-1)+F(m-3)+...+F(3), but n≥F(m)=F(m-1)+F(m-3)+...+F(3)+1,
contradiction. (A summand of 1 is always considered to be F(2) for the purpose of consecutive Fibonacci number.)
Then n-F(m)<F(m-1). We can then repeat the argument on n-F(m) to write it uniquely as the sum of distinct Fibonacci numbers. Adding F(m) then gives a unique representation of n as the sum of distinct Fibonacci numbers.
(Using induction, of course.)
In fact, this representation is the same as those of the greedy algorithm posted above. ("Greedy algorithm" here means "take the largest Fibonacci number F(m) as summand and repeat for n-F(m).)
Joined: 12/28/2007
Posts: 235
Location: Japan, Sapporo
FractalFusion wrote:
Mister wrote:
The existence of such a representation is not so difficult to imagine once you know any integer can be written as the sum of distinct Fibonacci numbers, as you can see that the densest sum F(2)+F(3)+F(4)+F(5)+F(6)+F(7)+... can change into F(4)+F(6)+F(8)+... as desired. The proof of the uniqueness, however, is a little formal since it often requires a non-constructive argument.
Proof of uniqueness can be done constructively.
Let's say n is an integer with F(m)≤n<F(m+1). Then F(m) must be a summand of n. Otherwise, n is at most:
● F(m-1)+F(m-3)+...+F(2), but n≥F(m)=F(m-1)+F(m-3)+...+F(2)+1, or
● F(m-1)+F(m-3)+...+F(3), but n≥F(m)=F(m-1)+F(m-3)+...+F(3)+1,
contradiction. (A summand of 1 is always considered to be F(2) for the purpose of consecutive Fibonacci number.)
Then n-F(m)<F(m-1). We can then repeat the argument on n-F(m) to write it uniquely as the sum of distinct Fibonacci numbers. Adding F(m) then gives a unique representation of n as the sum of distinct Fibonacci numbers.
(Using induction, of course.)
In fact, this representation is the same as those of the greedy algorithm posted above. ("Greedy algorithm" here means "take the largest Fibonacci number F(m) as summand and repeat for n-F(m).)
So you have proven two identities, which are summarized as a more general statement that the sum of a set of non-consecutive distinct Fibonacci numbers with F(n) largest must be strictly bounded by F(n+1). These only ensure that your "existence proof" process, which is constructive, gives a unique representation, but it doesn't mean that the proof of the uniqueness itself is constructive. This is what I wanted to mean in the above post; I might have confused you...
Retired because of that deletion event.
Projects (WIP RIP): VIP3 all-exits "almost capeless yoshiless", VIP2 all-exits, TSRP2 "normal run"
What is the sparsest sequence of distinct natural numbers for which it can be said "any natural number can be written as a sum of unique numbers in this sequence"?
Not sure how you define "sparse" in this context, but I don't think you'll get better than the binary representation, i.e. the sum of distinct numbers of the sequence 2^n.
What is the sparsest sequence of distinct natural numbers for which it can be said "any natural number can be written as a sum of unique numbers in this sequence"?
If one defines "sparseness" as asymptotic growth rate of element in ordinal...
Suppose that sequence sparser than 2^(n-1) existed:
Without loss of generality, order the sequence f in increasing order.
Then there exists first element in sequece that is greater than 2^(n-1). Call it c (with value k).
Now how would k-1 be represented? It can't involve k or element even greater, because there are no negative numbers.
But it can't be sum of any lesser number because:
sum(f(n),n,1,c-1) <= sum(2^(n-1),n,1,c-1)=2^(c-1)-1<k-1.
So k-1 can't be represented. A contradiction. Thus, there can be no sequence sparser than 2^(n-1).
In fact, the sequence 2^(n-1) can represent all natural numbers as unique
sum of numbers. So 2^(n-1) (1, 2, 4, 8, 16, 32, 64, ...) is the sparsest.
What might be less easy: What is the desnest (asymptitocally slowest growing) such natural number sequence where natural numbers can be expressed as unique sums?
What might be less easy: What is the desnest (asymptitocally slowest growing) such natural number sequence where natural numbers can be expressed as unique sums?
Wouldn't that be the set of all natural numbers? Or did I misunderstand something?
What might be less easy: What is the desnest (asymptitocally slowest growing) such natural number sequence where natural numbers can be expressed as unique sums?
Wouldn't that be the set of all natural numbers? Or did I misunderstand something?
No, and actually it is 2^(n-1) too (at least if sum of numbers is defined as subset sum sense).
Wouldn't that be the set of all natural numbers? Or did I misunderstand something?
I think when he said "unique sums" he didn't just mean "sums of distinct integers", but also "there's only one possible sum per integer". If 5 can be represented as 1+4 and 2+3, then the sums are not unique.
So given the constraint that your sequence does not contain any numbers that aren't required, 2^(n-1) is the only sequence possible.
* Since negative numbers aren't allowed, you need 1 = 2^0 to get a sum for 1
* if your sequence contains all numbers 2^0 .. 2^n, then all numbers 1 .. 2^(n-1)-1 already have a sum. Thus, the smallest value you can add without creating multiple sums is 2^(n+1)
Thus, by induction, the densest sequence possible is 2^(n-1).
Disregarding the first fibonacci number (which is just the same as the second one, ie. 1), can numbers be removed from the sequence while still retaining the property that any natural number can be expressed as the sum of unique values in the sequence?
If the answer is yes, is there a formula that gives all the "unneeded" fibonacci numbers?
Well, there is a very trivial upper limit to the fraction of the Fibonacci numbers you can remove, because we know that the set containing the powers of 2 is the sparsest set with the property. Hence any series which grows faster than powers of 2 cannot fulfil the criterion. Since the Fibonacci numbers and the powers of 2 both grow exponentially (the Fibaonacci numbers can be defined as powers of the golden ratio, rounded to the nearest integer). Hence any set that takes away more than 1 - log(phi)/log(2) of the numbers grows too fast to form unique sums for every integer. This upper limit on the proportion of removable integers turns out to be around 0.306.
(As an aside, the way you can prove that a sequence growing faster than powers of two cannot express every integer as a sum of elements, consider that there are 2^n possible sums of the first n terms in the sequence. If your nth term is greater than 2^n you can't express every number smaller than that as the sum of previous terms because there simply aren't enough distinct possible sums to do the job.)
I can give you a better upper limit: 1. I can also give you a lower limit: 1. You can remove any fibonacci number you like, but only one. Since Warp already removed F(1) = 1, all the other numbers are required.
Relevant property: F(1) + ... + F(n) = F(n+2) - 1
I have a proof of both claims, but with the equation above it should be easy to try for yourself.
Got it! If we remove F(n), then we must express F(n+1) - 1 as F(1) + F(2) + F(3) + ... F(n-1). Therefore we cannot maintain the property by removing F(n) and F(m) if m < n, because we have no way of expressing F(n+1) - 1. If n < m then similarly we cannot express F(m+1) - 1. Neat.
That's the upper bound, correct.
Now you need to prove that any single number can be removed. Though that part of the proof is a bit tedious and not nearly as satisfying.
You can remove any fibonacci number you like, but only one.
I could posit a counter-argument.
Any fibonacci number F(n) in the sum can be substituted with F(n-1)+F(n-2). This means that any F(n) can be removed from the set as long as F(n-1) and F(n-2) are not removed. This sounds to me like you could remove every third fibonacci number, and still be able to express any natural number as a sum of fibonacci numbers.
(Or did you mean under the condition of "a sum of non-consecutive fibonacci numbers"? You didn't make that completely clear.)
That's very sweet of you. Posting a counter-argument two posts below a proof that proves your argument false. What kind of answer do you expect to that?
As I said, I have proven the statement you quoted, and the last few posts in this thread contain all the information required to prove it yourself. Why don't you try working through the problem yourself? It's amazingly more enlightning than throwing random guesswork at a thread and waiting for someone else to provide answers.
And no, there's no hidden condition in my statements. You can remove exactly one fibonacci number from the sequence, and the remaining elements can still be combined to sum up to any natural number, where any fibonacci number is used at most once (though F(1) and F(2) can both be used, allowing you to use the number 1 twice). Remove two, and you can't.
The second part of the proof shouldn't be hard considering that we have already demonstrated that all integers are the sum of non-consecutive Fibonacci numbers.
To construct the sum of k as a sum of Fibonacci numbers disregarding F(n):
Express k as a sum of non-consecutive Fibonacci numbers. [This summation is unique with one exception: F(2k) = F(2k-1) + F(2k-3) + ... + F(1) - in this case take the first expression.] If this set does not include F(n) then we are done.
If it DOES contain F(n), then replace with F(n-2) + F(n-1). If the original sum did not contain F(n-2), then we are done. Note the sum can never contain F(n-1), by definition.
If the sequence does now contain a duplicated F(n-2), we just repeat the process again, splitting F(n-2) into F(n-4) + F(n-3), (noting that we may duplicate F(n-4), but never F(n-3)) and we can repeat this process arbitrarily many times until n reaches 2 or 1. n can never reach one because we have already prohibited precisely the sums that would not terminate before they reached n=1, two paragraphs up. If n reaches 2, we can just "split" F(2) as follows: F(2) = F(1) (=1), and the sequence terminates.
Thus we can construct an integer out of a partial sum of the set of Fibonacci numbers, minus any one element.
Can I have a gold star please?
Incidentally, not only does the Fibonacci subset that Warp mentioned fail to provide a partial sum for every integer, in fact the fraction of integers that can be represented from its partial sums is almost zero, in the technical sense that if you take the numbers high enough the fraction can become as close to zero as you like. The not-every-third-Fibonacci numbers grow at a rate of (golden ratio)^3/2 = 2.058 per term, whereas the number of possible partial sums only doubles every extra term. So eventually the size of the terms in the sequence vastly outstrips the number of possible partial sums, even if every partial sum gave a different integer.
[citation needed]
We've proven that such a sequence exists, and we've given an algorithm to find one such sequence, but we've never proven that such a sequence is unique. In fact, I have a counter-example. ;)
But you may start with the sequence generated by the greedy algorithm if you wish to rely on some of its properties.
thatguy wrote:
n can never reach one because we have already prohibited precisely the sums that would not terminate before they reached n=1, two paragraphs up.
No, you haven't, and I do believe that you need to handle this case. Consider the sum F(1) + F(3) + F(5) + F(100) - and the F(n) you wish to remove is F(5). Can you prove that such a sequence is never generated by the greedy algorithm? Or can you find another way to represent the number after removing F(5)?
Are there any other special cases you may have forgotten?
thatguy wrote:
Can I have a gold star please?
not yet :D The general idea seems to work, just add rigor until a proof appears.
Btw, I tackled the problem the other way around (since I didn't yet know the solution): I removed F(n) (with n > 2) and then tried to generate sequences for all natural numbers.
Numbers 1 to F(n)-1 are easy, use the greedy algorithm, no numbers are missing
F(n) is easy, F(n-2) + F(n-1)
F(n+1) is easy
Anything above F(n+1) is easy if anything below is possible; use the greedy algorithm until you pass F(n+1), then use the modified sequence from this proof for the remainder.
The interval F(n)+1 to F(n+1)-1 is the tricky part. By solving it I did not only notice that any one number can be removed, but also that you cannot remove two.
Fun fact: my variant doesn't rely on the non-consecutive property at all; the existence of a sequence is enough.
Yes, I have proved these sequences you are complaining about are never generated by the greedy algorithm: F(2n-1) + F(2n - 3) + ... + F(1) = F(2n), which can be proved recursively. I did actually note this exception.
I find all you people's proofs hard to follow, honestly. My own proof (to the fact that you can remove any fibonacci number), is a bit different:
Let us assume we can remove any fibonacci number from the sequence F(1), ..., F(n - 1) and still construct all the numbers a < F(n). We can then also construct all the numbers b where F(n) < b < F(n + 1) by taking the sum for b - F(n) (which exists, as a given) and adding F(n).
We then prove we can also remove F(n) from the fibonnaci sequence by taking the sum for b - F(n) and adding F(n - 1) + F(n - 2). We know we can do this because
A) we will never have used both of them, as F(n - 1) + F(n - 2) = F(n) and b - F(n) < F(n)
B) we can safely remove the other one, as per our initial assumption.
Given that our initial statement holds true for F(5) = 5 (you can easily check this by hand), it follows by induction that we can remove any one element from the fibonacci sequence and still construct any given number.
That's very sweet of you. Posting a counter-argument two posts below a proof that proves your argument false. What kind of answer do you expect to that?
Perhaps something less smug, patronizing and sarcastic sounding.
You might not have intended it like that, but you came out sounding like an a-hole.
Yes, I have proved these sequences you are complaining about are never generated by the greedy algorithm: F(2n-1) + F(2n - 3) + ... + F(1) = F(2n), which can be proved recursively. I did actually note this exception.
ah, you were talking about the longest subsequence of that form, not just about full sequences. Sorry I missed that. But to be fair, your description was a bit terse. ;)
Here's your star, then!
@Scepheo: so your proof says that you can remove any number F(n) after you've already removed a number F(k) with k<n? We know that's not possible, so there must be a flaw in there.
I think this is the part where your proof goes poof:
A) we will never have used both of them, as F(n - 1) + F(n - 2) = F(n) and b - F(n) < F(n)
B) we can safely remove the other one, as per our initial assumption.
A) Yes, after removing F(k), k < n, you will still have a sum, and that sum has only used either of F(n-1) or F(n-2)
B) ...but now you're retroactively changing k to either n-1 or n-2! By doing so, you get a different sum for b, invalidating your assumption that the other number wasn't used!
If you remove F(n-1), your sum may contain F(n-2), and if you remove F(n-2), your sum may contain F(n-1). At no point are both used (so A still stands), but there's no proof that you can remove both at the same time and still represent any b you need.
Warp wrote:
You might not have intended it like that, but you came out sounding like an a-hole.
I'm glad you noticed.
You know what else makes one sound like an a-hole? Asking a question, then ignoring the answers that others have spent time to provide for you. Above you were two proofs, one proving that no more than 30.6% of all fibonacci numbers can be removed; another proving that at most one can be removed. Yet you posit an argument suggesting to remove 1/3 of all numbers. Why? I doubt it'd lead to valuable insight. I also doubt it'd help you understand the issue. I doubt that it can, in any way, be considered a good contribution to the thread.
Now I know that these things aren't trivial, for none in this thread. Mistakes are made, misunderstandings happen, details get lost, sometimes things need to be repeated to be understood, and some people ask questions on a completely different difficulty scale than others. That's fine.
What's not fine is that you keep asking questions without trying to answer them on your own. Answering one of your questions can take a good hour of browsing wikipedia for known results, reviewing the previous posts in this thread, dabbling on a piece of paper, reformulating the problem, scribbling some more etc.
I think it's incredibly rude to ask others to invest that amount of time on your problem unless you've spent a good amount of time trying to figure it out yourself. Even more rude to ask more questions before you've made a good effort trying to understand the answers that were already given to you.
And not only is it more considerate towards your fellow forum members, it's also easier to learn and understand the things that seem to interest you by trying to solve these things for yourself. Knowing how many numbers you can remove from the fibonacci sequence is a useless trivia question; knowing how to prove it is a good skill.
And don't tell me it's too hard. This is not a problem about lattice configurations in 17-dimensional hilbert space while approaching relativistic speeds. All you need is wikipedia, highschool math and the will to sit down and work on it. I know you're smarter than this, you were just being lazy.
So go ahead, try the next thing you're curious about for yourself. If you get interesting results, share them. If you think the proof is interesting, pose it as a riddle to the thread, then share your solution later. If you get stuck, post how far you got and ask for help.
But please don't just post a random idea you had five seconds ago and expect everyone else to do the work for you.
Joined: 12/28/2007
Posts: 235
Location: Japan, Sapporo
Tub wrote:
@Scepheo: so your proof says that you can remove any number F(n) after you've already removed a number F(k) with k<n? We know that's not possible, so there must be a flaw in there.
I think this is the part where your proof goes poof:
A) we will never have used both of them, as F(n - 1) + F(n - 2) = F(n) and b - F(n) < F(n)
B) we can safely remove the other one, as per our initial assumption.
A) Yes, after removing F(k), k < n, you will still have a sum, and that sum has only used either of F(n-1) or F(n-2)
B) ...but now you're retroactively changing k to either n-1 or n-2! By doing so, you get a different sum for b, invalidating your assumption that the other number wasn't used!
If you remove F(n-1), your sum may contain F(n-2), and if you remove F(n-2), your sum may contain F(n-1). At no point are both used (so A still stands), but there's no proof that you can remove both at the same time and still represent any b you need.
Scepheo's statement in B) is that you can remove F(n-1) instead of F(n-2) (not both) if F(n-2) is removable, isn't it?
Retired because of that deletion event.
Projects (WIP RIP): VIP3 all-exits "almost capeless yoshiless", VIP2 all-exits, TSRP2 "normal run"
@Scepheo: so your proof says that you can remove any number F(n) after you've already removed a number F(k) with k<n? We know that's not possible, so there must be a flaw in there.
I think this is the part where your proof goes poof:
A) we will never have used both of them, as F(n - 1) + F(n - 2) = F(n) and b - F(n) < F(n)
B) we can safely remove the other one, as per our initial assumption.
A) Yes, after removing F(k), k < n, you will still have a sum, and that sum has only used either of F(n-1) or F(n-2)
B) ...but now you're retroactively changing k to either n-1 or n-2! By doing so, you get a different sum for b, invalidating your assumption that the other number wasn't used!
If you remove F(n-1), your sum may contain F(n-2), and if you remove F(n-2), your sum may contain F(n-1). At no point are both used (so A still stands), but there's no proof that you can remove both at the same time and still represent any b you need.
Ah, no, the latter have of my post aims to proof that, apart from f(k) | k < n, you could also remove f(n). So yes, I am "changing k to n-1 or n-2", but that's okay, since I'm no longer using the fact that f(k) was removed.
Basically, my proof consists of two parts:
1) Proof that we can also make the numbers up to f(n) for any given f(k) removed.
2) Proof that we could also remove f(n) instead and still make the sums.
ah, you were talking about the longest subsequence of that form, not just about full sequences. Sorry I missed that. But to be fair, your description was a bit terse. ;)
Here's your star, then!
STAR GET!
As for the purpose in this thread, I don't think it's necessary to know the solution to a problem in order to ask it; however I do agree that one should at least think about the problem, if only because it might turn out to be trivially easy and not worth asking.
That does not mean that, when Warp posted some clearly incorrect reasoning, he had not thought about it; on the contrary, the fact that he had posted at all shows that he had. In fact in mathematics you can often achieve contradictory results through different lines of reasoning, in which case it is instructive to find the flaw in one of the proofs. In this case, Warp has just forgotten that, when modifying an existing sum of unique Fibonacci numbers, it is not necessarily okay to make the substitution F(n) -> F(n-2) + F(n-1) because F(n-2) or F(n-1) may already appear in the sum.
@Scepheo: so your proof says that you can remove any number F(n) after you've already removed a number F(k) with k<n? We know that's not possible, so there must be a flaw in there.
I think this is the part where your proof goes poof:
