| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1300.1 | | SSDEVO::LARY | under the Big Western Sky | Mon Sep 24 1990 04:50 | 26 |
| > n
> ---
> \ n-i 2 n 2
> / 2 i <= 2 n
> /----
> i=1
I'm sure there's some closed-form expression for the sum, but you
can very simply can get a lot tighter bound than what you need:
the sum can be rewritten:
n-1 n-2 n-3 n-4
2 + 4*2 + 9*2 + 16*2 + ...
Or, rearranging slightly:
n-1 n-3 n-2 n-3 n-4
(2 + 2 ) + 4*2 + 8*2 + 16*2 + ...
n
All the terms shown are <=2 , and so are all the unshown terms since
(i+1)�/i� < 2 for i > 3
n
So it would appear that the sum is always less than n*2
|
| 1300.2 | by contradiction also | SMAUG::ABBASI | | Mon Sep 24 1990 05:22 | 54 |
| by contradiction, Assume it is false, i.e
n
---
\ n-i 2 n 2
/ 2 i > 2 n
/----
i=1
i.e
n
---
n \ 2 n 2
2 / i > 2 n
/ -----
/ i
/ 2
/----
i=1
i.e
--- 2
\ i 2
/ --- > n
/ i
-- 2
2 2
or ( 1 + 4 + 9 + n ) > n
--- --- --- ---
2 2^2 2^3 2^n
or ( 1 + 4 + 9 + 1 ) > 1
--- ----- ---- ---
2 2 2 3 2 n
2*n 2 n 2 n 2
for n=1 , 1/2 > 1 , not valid, hence assumption is wrong, hence proof
for n=2..infinity Left hand side goes to 0, hence 0>1 not valid, hence
assumption is wrong, hence proof.
p.s.
x=n
you can also proof by / 2
| x
| --- dx and show that this definite I is
/ x <= n^2
x=1 2
/naser
|
| 1300.3 | closed form for sum. | CADSYS::COOPER | Topher Cooper | Mon Sep 24 1990 11:32 | 21 |
| RE: .1
>> n
>> ---
>> \ n-i 2 n 2
>> / 2 i <= 2 n
>> /----
>> i=1
>
>I'm sure there's some closed-form expression for the sum, ...
With Maple's help:
n
---
\ n-i 2 n 2
/ 2 i = 6*2 - n - 4n - 6
/----
i=1
Topher
|
| 1300.4 | One more proof. | CADSYS::COOPER | Topher Cooper | Mon Sep 24 1990 11:46 | 19 |
| Oh yes, nearly forgot. Previous postings adequately proved it, but
using the closed form (and assuming n > 0).
n 2 n 2
6*2 - n - 4n - 6 <=? 2 n
Divide both sides by the (positive) left side:
6 1 4 6
--- - (--- + --- + ----) <=? 1
2 n n n 2
n 2 2 n 2 n
The first term is < 1 for n>2. The other terms can only serve to
reduce the size of the lefthand side of the inequality and so can
be ignored for n>2. The relation is easily checked for n=1 and n=2,
QED.
Topher
|
| 1300.5 | Thanks | CSC32::S_JOHNSON | Lifetime Member of Aye Phelta Thi | Mon Sep 24 1990 12:39 | 3 |
| Thanks. I appreciate everyone's responses.
scott
|
| 1300.6 | how did MAPLE find it ? | SMAUG::ABBASI | | Mon Sep 24 1990 14:35 | 13 |
| ref .3
>With Maple's help:
> n
> ---
> \ n-i 2 n 2
> / 2 i = 6*2 - n - 4n - 6
> /----
i=1
Ok, assuming we did not have this amazing MAPLE, how would one go about
deriving this by hand.
|
| 1300.7 | Guess the answer, then prove it by induction | DECWET::BISHOP | Nihon ga natsukashii ... | Mon Sep 24 1990 15:17 | 7 |
| re .6
You can compute it for several values of n and get the pattern from that, then
prove it by induction. For a formula as complex as this one, however, finding
the pattern would be pretty hard.
Avery
|
| 1300.8 | thanks, But now Iam more curious abot MAPLE ? | SMAUG::ABBASI | | Mon Sep 24 1990 16:00 | 12 |
| rec .7
thanks Avery,
>You can compute it for several values of n and get the pattern from that, then
>prove it by induction. For a formula as complex as this one, however, finding
>the pattern would be pretty hard.
I see how I may try it by hand, But then How did MAPLE do it ?
what analytical method could it have used ? it could not have
used the above method ?
thanks
|
| 1300.9 | | TRACE::GILBERT | Ownership Obligates | Mon Sep 24 1990 19:20 | 33 |
| n
--- n+1
\ i x - 1
/ x = --------
---- x - 1
i=0
Taking derivatives of both sides,
n
--- n n+1
\ i-1 (n+1) x x - 1
/ i x = -------- - --------
---- x - 1 (x-1)^2
i=1
Multiply both sides by x, and take derivatives again,
n
--- 2 n n+1 n+1 n
\ 2 i-1 (n+1) x x - 1 2 x (x - 1) 2 (n+1) x + 1
/ i x = ---------- - -------- + ------------- - --------------
---- x - 1 (x-1)^2 (x-1)^3 (x-1)^4
i=1
Now multiply both sides by `x 2^n', and then let x = �.
n
---
\ 2 n -i n 2
/ i 2 2 = 6 2 - n - 4 n - 6
----
i=1
|
| 1300.10 | like it | HERON::BUCHANAN | combinatorial bomb squad | Tue Sep 25 1990 05:51 | 5 |
| Re: <<< Note 1300.9 by TRACE::GILBERT "Ownership Obligates" >>>
That's neat!
Andrew.
|
| 1300.11 | How did you get Maple to do it? | CSC32::S_JOHNSON | Lifetime Member of Aye Phelta Thi | Tue Sep 25 1990 18:03 | 16 |
| >With Maple's help:
> n
> ---
> \ n-i 2 n 2
> / 2 i = 6*2 - n - 4n - 6
> /----
i=1
I just managed to get maple loaded onto one of our systems. What did
you enter to get the result? I tried sum((2^(n-i))*(i^2)); and it does
not look the same.
thanks for any replies.
scott
|
| 1300.12 | | GUESS::DERAMO | Dan D'Eramo | Tue Sep 25 1990 19:46 | 18 |
| >> I just managed to get maple loaded onto one of our systems. What did
>> you enter to get the result? I tried sum((2^(n-i))*(i^2)); and it does
>> not look the same.
You have to tell Maple what you are "summing over". If you
tell it to sum (2^(n-i))*(i^2) as i varies from 1 to 10 and
n varies from 1 to 5, then it will compute those fifty terms
and add them and tell you that number. If you tell Maple to
sum (2^(n-i))*(i^2) as n varies from -3i to 17i+12, it will
attempt to sum it "symbolically", expressing its result as a
function of i. In this case you need to tell Maple that you
are summing over i, as i varies from 1 to n, and to give the
result symbolically as a function of n. I don't know Maple
syntax so I can't tell you how to do that; it might be some-
thing like sum( (2^(n-i))*(i^2) , i , 1 , n ) or perhaps
sum( (2^(n-i))*(i^2) ; i=1,...,n ).
Dan
|
| 1300.13 | Try simplifying the result | ALLVAX::JROTH | It's a bush recording... | Tue Sep 25 1990 20:05 | 20 |
| > I just managed to get maple loaded onto one of our systems. What did
> you enter to get the result? I tried sum((2^(n-i))*(i^2)); and it does
> not look the same.
say something like
s := sum(2^(n-i)*i^2,i=1..n);
and then say
simplify(s);
The online help for Maple is pretty good - I don't use Maple regularly
enough to be any kind of expert, but rarely have to look at the manual.
You just have to play a little.
I wish I had tools like this ages ago... oh well.
- Jim
|
| 1300.14 | Delaunay's wishes the same | SMAUG::ABBASI | | Tue Sep 25 1990 20:30 | 25 |
| ref .-1 <<< Note 1300.13 by ALLVAX::JROTH "It's a bush recording..." >>>
>I wish I had tools like this ages ago... oh well.
>- Jim
jim, this may makes you feel a little better.
extracted from computing supplementum 4, computer algebra symbolic and
algebric computation, 1982, springer-verlag.
"the introduction of a new technique (the Lie transform) allowed Deprit
to recompute the reduced Hamiltonian of the main problem in lunar
theory. Delaunary spent TWENTY YEARS to the complete the calculation by
HAND. Deprit used only 20 HOURS on a small PC using a computer algebra
package"
Delaunary lived in the 1860's .
also the package found out that Delaunay results were correct up to
order 9.
I bet the same calculation could be done today in 20 MINUTES.
I felt sad for the Late Delaunary after reading this.
I wondar what he would say if he knew this !
/naser
|