On Wed, 10 Oct 2007 15:13:33 -0400, "Gary S. Simon"
<garscosi@[EMAIL PROTECTED]
> wrote in
<news:garscosi-91C56B.15133210102007@[EMAIL PROTECTED]
>
in alt.algebra.help:
> My son Dan has been very interested in Fibonacci numbers
> recently. He posits the following:
> Given the sequence of Fibonacci numbers*, in which Fx
> represents the xth term in the sequence, then, for all
> odd values of n:
> 1. all non-negative integers from Fn-1 through f(n+2)-2
> (inclusive) may be expressed as the sum of no more than
> n-2 Fibbonacci numbers.
That's the integers from F_n - 1 through F_{n+2} - 2? So
that if n = 5, for instance, the claim is that each of the
integers from F_5 - 1 = 5 - 1 = 4 through f_7 - 2 = 13 - 2 =
11 is expressible as the sum of at most 5 - 2 = 3 Fibonacci
numbers?
Clearly this can be true only for n > 2, so that n - 2 > 0.
> 2. The number F(n+2)-2 cannot be expressed as the sum of
> fewer than n-1 Fibbonacci numbers.
The two statements contradict each other: (1) implies that
F_{n+2} - 2 can be expressed as the sum of n - 2 Fibonacci
numbers, while (2) says that it cannot. Take n = 7; since
F_9 - 2 = 32 = 21 + 8 + 3 = F_8 + F_6 + F_4 is the sum of
fewer than 5 Fibonacci numbers, (2) must be false as stated.
I suspect that you meant that F_{n+2} - 1 cannot be
expressed as the sum of fewer than n - 1 Fibonacci numbers.
> I believe that (1) can be proven by induction.
It can, but a stronger result follows from Zeckendorf's
Theorem: Every positive integer can be represented as the
sum of one or more distinct Fibonacci numbers. If we
further require that the sum not include any two consecutive
Fibonacci numbers, this representation is unique. (Without
this restriction we could represent 13, say, as itself, as 8
+ 5, as 8 + 3 + 2, etc. With the restriction only the first
of these representations is allowed.)
A proof of this theorem is sketched at
<http://en.wikipedia.org/wiki/Zeckendorf's_theorem>.
Zeckendorf's Theorem implies that we can represent each
positive integer n uniquely in the form
n = SUM[i=2 to k; d_i * F_i],
where each d_i is 0 or 1, d_k = 1, and no two consecutive
d_i and d_{i+1} are both 1. If we list these coefficients
in reverse order, as (d_k, d_{k-1}, ..., d_2, d_1), we get a
(k-1)-tuple of 0's and 1's that begins with a 1 and does not
contain two consecutive 1's. Omitting the parentheses and
commas gives as a sort of 'base Fibonacci' representation of
the number n. Some examples:
Zeckendorf
n representation
-------------------
1 1
2 10
3 100
4 101
5 1000
6 1001
7 1010
8 10000
9 10001
10 10010
11 10100
12 10101
13 100000
(Note that the rightmost digit corresponds to F_2, the
second 1 in the Fibonacci sequence.)
The proof of Zeckendorf's Theorem actually shows how to
construct the Zeck. representation. Let k be the largest
integer such that F_k <= n. If F_k = n, then the Zeck.
repr. is a 1 followed by k - 2 0's. (E.g., 13 = F_7 is
represented by 100000, a 1 followed by five 0's.) If
F_k < n, let n' = n - F_k, and repeat the process using n'
in place of n. For example, suppose that n = 100. The
largest F_k <= 100 is F_11 = 89. 100 - 89 = 11, and the
largest F_k <= 11 is F_6 = 8. 11 - 8 = 3 = F_4. Thus, 100
= F_11 + F_6 + F_4, and its representation is 1000010100.
For any k > 1, the Zeck. repr. of F_k requires k-1 bits, a 1
followed by k-2 0's. If n < F_k, then the Zeck. repr. of n
can't have a 1 for F_k and therefore must have at most k - 2
bits. Moreover, no two consecutive bits are 1's. This
means that if k-2 is even, at most (k-2)/2 bits are 1's, and
if k-2 is odd, at most (k-1)/2 bits are 1's. (In the first
case the representation has the form 1010...10; in the
second, the form 1010...101.) Note that k and k-2 have the
same parity, so we can simplify this a little: if n < F_k,
then the number of 1's in the Zeck. repr. of n is at most
k/2 - 1 if k is even and at most (k-1)/2 if k is odd.
In particular, any positive integer less than F_{n+2} can be
represented as the sum of at most n/2 Fibonacci numbers if n
is even, and at most (n+1)/2 if n is odd. It's not hard to
prove that if n >= 4, then n - 2 >= n/2 when n is even, and
n - 2 >= (n+1)/2 when n is odd. Thus, for all n >= 4 it's
true that any positive integer less than F_{n+2} can be
represented as the sum of at most n - 2 Fibonacci numbers,
and the cases n < 4 can be checked by hand.
If n > 5, n/2 (n even) or (n+1)/2 (n odd) is smaller than
n - 2, so this result is strictly stronger than your son's
(1).
His (2), however, is false, even in my formulation. Take
n = 5. Then 12 = F_7 - 1 has the Zeck. repr. 10101,
corresponding to the sum 12 = 8 + 3 + 1, and so requires
fewer than 5 - 1 = 4 Fibonacci numbers. What *is* true is
that F_{n+2} - 1 requires n/2 Fibonacci numbers, and if n is
odd, F_{n+2} - 1 requires (n+1)/2 Fibonacci numbers.
Moreover, when n is odd F_{n+2} - 1 is the *only* integer
less than F_{n+2} that requires (n+1)/2 Fibonacci numbers.
[...]
Brian
|
