| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
/ unknown non-negative integers for n<0
|
|
U = | 1 for n=0
n |
| m
| SIGMA B U for n>0
\ k=1 k n-k
B , B , ... , B are positive integers.
1 2 m
Prove that U / U <= 1 + max B for every n>1
n n-1 k
(Trivial examples: Geometric sequences, Fibonachi sequence, ...)
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 219.1 | TAV02::NITSAN | Mon Feb 11 1985 05:02 | 1 | ||
Woops: Unknown non-negative FIXED integer. | |||||
| 219.2 | TRACE::GILBERT | Ownership Obligates | Thu Feb 15 1990 10:17 | 1 | |
I assume the summation should be from 1 to n (not m). | |||||
| 219.3 | AITG::DERAMO | Dan D'Eramo, nice person | Thu Feb 15 1990 14:33 | 4 | |
I think m is correct; for example, for Fibonacci numbers m = 2. Dan | |||||
| 219.4 | KOBAL::GILBERT | Ownership Obligates | Wed Feb 21 1990 12:01 | 79 | |
Well, I'm been making some (very) meager progress on this for m=2.
The case for m=1 is trivial, since in that case:
n
U = B , and so U / U = B <= 1 + max B
n 1 n n-1 1 k
When m=2, we have:
n n
U = c a + c a , where
n 0 0 1 1
c = (U (D-B ) + 2) / (2 D), c = (U (D+B ) - 2) / (2 D),
0 -1 0 1 -1 0
a = (D+B ) / 2, a = (B -D) / 2, and
0 0 1 0
2
D = sqrt( B + 4 B ). (Note that D > B )
0 1 0
Thus, we see that the ratio U / U takes the form:
n n-1
K U + K
a -1 b
--------------, where the K are independent of U .
K U + K -1
c -1 d
The derivative of this ratio with respect to U is
-1
( K K - K K ) / (K U + K )^2,
a d b c c -1 d
and this expands/simplifies to
n n
- 16 B D (B - D) (D+B )
0 0 0
-------------------------------------------------------------------
n n n n 2
{ 2 U [(D-B )(D+B ) + (D+B )(B -D) ] + 4 [(D+B ) + (B -D) ] }
-1 0 0 0 0 0 0
This is positive if n is odd, and negative if n is even. Thus, to maximize
the ratio U / U by choosing U , we should let U be a very large number
n n-1 -1 -1
for odd n, and a very small number for even n (recall that U is constrained
-1
to be an integer >= 0).
If n is odd and we choose a large U to maximize U / U , then the ratio
-1 n n-1
becomes simply K / K , or:
a c
n+1 n+1
U (D-B )(D+B ) + (D+B )(B -D)
n 0 0 0 0
------ = -------------------------------------
U n n
n-1 2 [ (D-B )(D+B ) + (D+B )(B -D) ]
0 0 0 0
n
D (D+B )(B -D)
0 0
= (D+B )/2 - -------------------------------
0 n n
(D-B )(D+B ) + (D+B )(B -D)
0 0 0 0
Which is somewhat larger than (D+B )/2.
0
(That's it so far)
| |||||
| 219.5 | AITG::DERAMO | Dan D'Eramo, nice person | Wed Feb 21 1990 15:41 | 23 | |
An example for m=2 is the Fibonacci sequence:
Let U = 0 (restricted to non-negative integers in general)
-1
and U = 1 and U = U + U for n > 0
0 n n-1 n-2
i.e., B = B = 1 (in general they are positive integers)
1 2
Then the claim in .0 is that for all n>1, U / U <= 2.
n n-1
And for the Fibonacci sequence, this is true--successive
terms don't more than double.
For the general case I would expect that a proof by
induction would be possible and that it wouldn't be
necessary to actually solve for U in closed form.
n
Dan
| |||||