wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Alternating Sum
        
(Message started by: THUDandBLUNDER on Aug 24^th, 2006, 4:09am)

Title: Alternating Sum
Post by THUDandBLUNDER on Aug 24^th, 2006, 4:09am

For 0 < x < 1, consider S(x) = x - x² + x⁴ - x⁸ + x¹⁶ - x³² +... - ...

Does S(x) tend to a limit as x -> 1 from below, and if so what is this limit?

Title: Re: Alternating Sum
Post by Sameer on Aug 24^th, 2006, 3:39pm

EVEN if I know the answer the ODDs are that somebody will post a nice solution so I will wait[hide]S(x) is an oscillating series as it approaches 1[/hide]

Title: Re: Alternating Sum
Post by Icarus on Aug 24^th, 2006, 6:52pm

Coming up with the value isn't hard. Showing that S converges to it (I'm fairly certain it does) is another matter.

By Hadamard's formula, the series converges to an analytic S for all |x| < 1. Note also that S(x) = x - S(x²), whereby it is clear that S(1-) = 1/2, if it exists at all.

Title: Re: Alternating Sum
Post by Sameer on Aug 24^th, 2006, 11:27pm

what about S(1+) ? Doesn't that tell if S converges if x->1

Title: Re: Alternating Sum
Post by Eigenray on Aug 25^th, 2006, 6:38am

on 08/24/06 at 23:27:14, Sameer wrote:

what about S(1+) ? Doesn't that tell if S converges if x->1

The series for S(x) doesn't converge if x>1. And [hide]S(z) can't be analytically continued outside the unit disk,[/hide] so there's no other way to sensibly define S(x), x>1. But that doesn't really matter, since the question is only asking about the limit from the left.

Title: Re: Alternating Sum
Post by Sameer on Aug 25^th, 2006, 9:42am

Ah ok I misinterpreted x->1 from below!! Thanks for clarifying..

Title: Re: Alternating Sum
Post by Icarus on Aug 25^th, 2006, 5:25pm

Here is one way to show that it converges (though I leave the nasty details where the devil hides out):

Let C(x) be the Cesaro sum of the series: If S_n(x) = x - x² + ... - x^{2^(n-1)}, then C = lim_n (1/n)(S₁ + S₂ + ... + S_n).

The following facts hold:
1) If a sequence converges, then the Cesaro sum converges to the same limit.
2) C(1) converges to 1/2.
3) (the nasty part) C(1-) = C(1).
4) by (1), S(1-) = C(1-) = C(1).

Title: Re: Alternating Sum
Post by Deedlit on Aug 25^th, 2006, 10:02pm

S(x) = x / (1+x) for -1 < x < 1, and lim [x -> 1-] x / (1 + x) = 1/2. :)

Title: Re: Alternating Sum
Post by Barukh on Aug 26^th, 2006, 12:15am

on 08/25/06 at 22:02:37, Deedlit wrote:

S(x) = x / (1+x) for -1 < x < 1, and lim [x -> 1-] x / (1 + x) = 1/2. :)

???

Isn't it true for S'(x) = x - x² + x³ - x⁴ + ... ?

Title: Re: Alternating Sum
Post by Deedlit on Aug 26^th, 2006, 1:53am

Heh heh. Today is just one of those days...

Title: Re: Alternating Sum
Post by Michael_Dagg on Aug 26^th, 2006, 10:39am

You can spot an easy functional relationship between S(x) and S(x^2);
then let x -> 1- and you'll arrive at the same result. I think most
things about this function are proved from that functional relationship.

Title: Re: Alternating Sum
Post by Sameer on Aug 26^th, 2006, 11:40am

S(x) = x - S(x²)

So let's compute S(x²) first

S(x²) = x² - x⁴ + x⁸ ..

sum of series formula

S(x²) = x²/(1+x²)

So S(x) = x - x²/(1+x²)

Computing x->1- gives 1/2

Did I miss anything?

Title: Re: Alternating Sum
Post by Icarus on Aug 26^th, 2006, 12:14pm

x²/(1+x²) = x² - x⁴ + x⁶ - x⁸ + ...
S(x²) = x²/(1+x²) = x² - x⁴ + x⁸ - x¹⁶ + ...

Title: Re: Alternating Sum
Post by Michael_Dagg on Aug 26^th, 2006, 12:16pm

Alternatively, see if you can come up with a g(x) and h(x) such
that you can squeeze it: g(x) <= S(x) <= h(x)

Title: Re: Alternating Sum
Post by Sameer on Aug 26^th, 2006, 12:27pm

on 08/26/06 at 12:14:59, Icarus wrote:

x²/(1+x²) = x² - x⁴ + x⁶ - x⁸ + ...
S(x²) = x²/(1+x²) = x² - x⁴ + x⁸ - x¹⁶ + ...

ugh.. i knew it came too easy and so had to be some problem... ok I think I need lunch to think this over!! Thanks Icarus for pointing this out..

Title: Re: Alternating Sum
Post by THUDandBLUNDER on Aug 26^th, 2006, 1:07pm

on 08/26/06 at 12:27:05, Sameer wrote:

ok I think I need lunch to think this over!!

S(x⁴) = ?

Title: Re: Alternating Sum
Post by Eigenray on Aug 26^th, 2006, 1:34pm

on 08/25/06 at 17:25:10, Icarus wrote:

The following facts hold:

By the process of elimination...

Quote:

3) (the nasty part) C(1-) = C(1).

...are you sure about that?

Attached is a graph of S(e^{-2^-x}) (in red).

Following [link=http://www.math.harvard.edu/~elkies/M259.02/gamma.pdf]Exercise 5[/link], by Poisson summation, for A>1, and z = e^{-2^-x},

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (-A)ⁿz^{2^n} = 1/log 2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif Gamma((log A - (2n-1)pi i)/log 2)e^{x(log A - (2n-1)pi i)},

where the sum is over all integers n. I don't see how to let A->1, because when A=1, the sum on the left doesn't converge (as n->-infinity). But, when z -> 1 (x->infinity), the sum for negative n is "-A/(1+A)-ish", which does go to -1/2, so in some sense
S(z) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n>=0 z^{2^n} ~^* 1/2 + 1/log 2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif Gamma(-(2n-1)pi i/log 2)e^{-(2n-1)pi i x}
= 1/2 + 2/log 2 Re[ Gamma(pi i/log 2)e^{pi i x} + Gamma(3pi i/log 2)e^{3pi i x} + ... ].

Gamma(iy) decays exponentially as y->infinity; compare S(z) (red) to F₁(x) (blue):
F₁(x) = 1/2 + 2/log 2 Re[ Gamma(pi i/log 2)e^{pi i x} ]
= 1/2 + 2/log 2 |Gamma(pi i/log 2)|cos(pi x + Arg Gamma(pi i/log 2)).
Arg Gamma(pi i/log 2) ~ .48 pi, so this is why S(z)=1/2 for x close to an integer.

^*Anybody know how to make this precise?

Title: Re: Alternating Sum
Post by Eigenray on Aug 26^th, 2006, 2:20pm

My previous post notwithstanding, there is in fact an elementary solution to the original question, though you'll quite likely need to use a computer to show [hide]the existence of an x with S(x)>1/2[/hide].

Followup: show that S(z) doesn't extend continuously to any connected open set intersecting the unit circle.

Harder: do any radial limits exist?

Title: Re: Alternating Sum
Post by THUDandBLUNDER on Aug 26^th, 2006, 3:08pm

on 08/26/06 at 12:27:05, Sameer wrote:

ok I think I need lunch to think this over!!

Looks like someone stole your thunder, Sameer! :D

Title: Re: Alternating Sum
Post by towr on Aug 26^th, 2006, 3:38pm

on 08/25/06 at 17:25:10, Icarus wrote:

The following facts hold:
1) If a sequence converges, then the Cesaro sum converges to the same limit.

But we want the reverse, don't we?
A Cesaro sum might converge if the original sequence doesn't.

Title: Re: Alternating Sum
Post by Sameer on Aug 26^th, 2006, 6:01pm

on 08/26/06 at 15:08:49, THUDandBLUNDER wrote:

Looks like someone stole your thunder, Sameer! :D

Yes, most definitely especially this being some of the things I studied as math in my electrical engineering... my eyes lit up with something in putnam i can try my hand at!! .. most of the questions in putnam go over my head!! :-/

Title: Re: Alternating Sum
Post by THUDandBLUNDER on Aug 27^th, 2006, 8:37am

on 08/26/06 at 18:01:53, Sameer wrote:

most of the questions in putnam go over my head!! :-/

In spite of Eigenray's admirable display of mathematical erudition, this is not one of them.
You can still solve this for yourself by noting that S(x) > S(x⁴) and S(0.995) > 1/2

Title: Re: Alternating Sum
Post by Icarus on Aug 27^th, 2006, 2:00pm

on 08/26/06 at 15:38:55, towr wrote:

But we want the reverse, don't we?
A Cesaro sum might converge if the original sequence doesn't.

It is somewhat pointless now, since that Eigenray and T&B want to be such poor sports about it as to disprove my claim of (3) >:(, but had (3) been true, it would have been sufficient.

The problem, if the answer were positive, would not require the series for S to converge at 1, only that the limits S(x) themselves converge as x --> 1-. Since S(x) = C(x) for x < 1, this is the same as saying C(x) converges as x --> 1-.

I went this way because Cesaro sums converge much more easily than regular limits, and are usually more stable. Further, I had already established that the limit of S, if it existed, was the Cesaro sum of the series for x=1.

Alas, there really was a devil hiding in those details, as Eigenray and Thud&Blunder have made clear. :-[

Title: Re: Alternating Sum
Post by Barukh on Aug 27^th, 2006, 11:24pm

Eigenray, how did you get these graphs?

Title: Re: Alternating Sum
Post by Eigenray on Aug 28^th, 2006, 2:14pm

In[1]:=S[z_]= Sum[(-1)^n z^(2^n), {n,0,Infinity}];
F[x_,n_]= 2/Log[2] Re[Sum[Gamma[(2k-1)Pi I/Log[2] E^((2k-1)Pi I x), {k,1,n]};
Plot[{S[E^(-2^(-x))], 1/2+F[x,1]}, {x,5,15}, PlotRange->{.492,.503}, AxesOrigin->{5,.5}, PlotStyle->[RGBColor[1,0,0]}, {RGBColor[0,0,1]]]

or some such.

Title: Re: Alternating Sum
Post by Eigenray on Aug 28^th, 2006, 8:34pm

I finally got around to working out the details:

For Re(a)>0, b,c>0, let

f(x) = e^{ax-be^(cx)}.

Note that f(n) decays exponentially as n->-infinity, and even faster as n->infinity, so everything I say below should be true.

The Fourier transform F of f can be computed by substituting t=be^cx below:
F(w) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif f(x)e^{-2pi i xw}dx
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif e^{x(a-2pi i w)}e^{-be^(cx)}dx
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif (t/b)^{(a-2pi i w)/c} e^-tdx/(ct)
= b^{(2pi i w-a)/c}/c http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif t^{(a-2pi i w)/c - 1} e^-tdt
= b^{(2pi i w-a)/c}/c Gamma((a-2pi iw)/c),
by the integral definition of [link=http://en.wikipedia.org/wiki/Gamma_function]Gamma(z)[/link] for Re(z)>0. By [link=http://en.wikipedia.org/wiki/Poisson_summation_formula]Poisson summation[/link],

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif f(n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif F(n),

where the sum is over all integers n. Fix z=e^-b < 1, set c=log 2, and for A>1, set a=log(-A) = log(A) + pi i. Then

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (-A)ⁿz^{2^n} = 1/log 2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif Gamma((log A - (2n-1)pi i)/log 2)e^{x(log A - (2n-1)pi i)}

Let S(z,A), T(z,A), denote the sum on the LHS above restricted to n>0, and n<0, respectively, and let U(x,A) denote the RHS. Now, we'll let A->1+.

The [link=http://en.wikipedia.org/wiki/Dominated_convergence_theorem]dominated convergence theorem[/link], applied to the counting measure, says that if we have a series http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c_n(A) depending on A, with c_n(A) -> c_n for each n, and |c_n(A)|<b_n for some b_n with http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif b_n finite, then http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c_n(A) -> http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c_n.

Since |(-A)ⁿz^{2^n}| < b_n=2ⁿz^{2^n} for 1<A<2, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n>0 b_n converges (by the n-th root test, say), we have S(z,A) -> S(z) as A->1+.

Determining T(z) = lim_A T(z,A) is more tricky, since the series T(z,1) doesn't converge. For convenience set t=1/A < 1, r=1-z > 0, so that
T(z, A) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n>0 (-t)ⁿ(1-r)^{1/2^n}
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n>0 (-t)ⁿ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k>=0 (-r)^k/k! (1/2ⁿ) (1/2ⁿ-1) ... (1/2ⁿ-(k-1))
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n>0 (-t)ⁿ + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n>0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k>0 c_n,k,r(t),
where c_n,k,r(t) = -(-t)ⁿr^k/k! [((k-1)2ⁿ-1) ... (2ⁿ-1)]/2^nk.
Since |c_n,k,r(t)| < r^k/2ⁿ, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif r^k/2ⁿ < r/(1-r), we have, for fixed z, as A,t -> 1,

T(z,A) = (-t)/(1+t) + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n,k>0 c_n,k,r(t)
-> -1/2 - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n,k>0 (-1)ⁿ r^k/k! [((k-1)2ⁿ-1) ... (2ⁿ-1)]/2^nk
= -1/2 - r http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n>0 (-1/2)ⁿ - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k>1 c_k,r,
where
|c_k,r| < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n>0 |c_n,k,r| < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n>0 r^k/(k2ⁿ) = r^k/k,
so
T(z) = -1/2 + r/3 + g(r),
where
|g(r)| < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k>1 r^k/k < 1/2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k>1 r^k = 1/2 r²/(1-r) < r² = O((1-z)²),
uniformly for 1/2 < z < 1.

I'll skip the details, but an elementary argument from the product formula gives |Gamma(iy)| < 2^{-y^2/(2(y+1))}/y, and this suffices to show that for fixed x,
U(x,A) -> U(x) := 1/log 2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif Gamma(m pi i/log 2)e^{x m pi i},
where the sum is over odd m. Putting this all together, we have that

S(z) = -T(z) + U(x)
= 1/2 - (1-z)/3 + g(z) + 2/log 2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{m>0 odd} Re[ Gamma(m pi i/log 2)e^{x m pi i} ],
where z = e^{-2^(-x)}, and g(z) = O((1-z)²).

Numerically, we have
U(x) = 0.00275 cos(pi (x+.48 )) + 10^-9 cos(pi (x+.72)) + O(10^-16).

Attached is a graph of
-S(z) + 1/2 - (1-z)/3 + 2/log 2 |Gamma(pi i/log 2)|cos(pi x + Arg[Gamma(pi i/log 2)])
(as a function of z). You can see the O((1-z)²) error term from T(z), as well as an oscillation of about 10^-9, so you know I didn't just make all this up ;D.

Title: Re: Alternating Sum
Post by Sameer on Aug 29^th, 2006, 4:05pm

on 08/27/06 at 08:37:09, THUDandBLUNDER wrote:

In spite of Eigenray's admirable display of mathematical erudition, this is not one of them.
You can still solve this for yourself by noting that S(x) > S(x⁴) and S(0.995) > 1/2

Eigenray just demonstrated that as x->1- the sum oscillates.. hence proving that it diverges.. (right?). Is that what you were trying to tell me using S(x) > S(x^4) and S(0.995) > 1/2 (our previously obtained limit). Is there a easier way to show this diverges? Needs more thought.. there must be something very basic I am missing here..

Title: Re: Alternating Sum
Post by Eigenray on Aug 29^th, 2006, 6:15pm

on 08/29/06 at 16:05:51, Sameer wrote:

Is that what you were trying to tell me using S(x) > S(x^4) and S(0.995) > 1/2 (our previously obtained limit)

Replacing x with [hide]t^1/4[/hide] might be more suggestive...

Title: Re: Alternating Sum
Post by Barukh on Aug 30^th, 2006, 1:35am

Sameer, may be the following explanation will be helpful:

1. As shown by Icarus, if the limit exists, it equals 1/2.

2. Therefore, if we can find a sequence of numbers x₀ < x₁ < x₂ < ... converging to 1-, for which S(x_n) > 1/2 + constant, it will be shown that the limit doesn't exist.

3. Take x₀ = 0.995, and x_n = x_n-1^1/4. We have:

a) x_n is increasing and converges to 1-.
b) S(x₀) > 1/2.
c) S(x_n) is increasing, as indicated by T&B.

I've got 2 additional question:

1. Is there a way to predict the existance of numbers like 0.995 without resorting to numerical methods?

2. Consider the sequence S(x_n) above. Does it have a limit, and if yes, what's its value?

Sorry, if Eigenray's post(s) already answer these questions.

Title: Re: Alternating Sum
Post by Sameer on Aug 30^th, 2006, 10:44am

on 08/30/06 at 01:35:12, Barukh wrote:

Sameer, may be the following explanation will be helpful:

2. Consider the sequence S(x_n) above. Does it have a limit, and if yes, what's its value?

Sorry, if Eigenray's post(s) already answer these questions.

Yes indeed Barukh that was the lines I was thinking as well.. so it ultimately turns to be the definition of limit that disproves the existence of limit!! :D

For part 2. I am betting the limit tends to 1. Since for |x| < 1, x^(1/4) is increasing and it will tend to 1. For nth term will be x^(1/n) and as n-> infinity x^(1/n) will tend to 1.

Title: Re: Alternating Sum
Post by Barukh on Sep 1^st, 2006, 4:01am

on 08/30/06 at 10:44:45, Sameer wrote:

For part 2. I am betting the limit tends to 1. Since for |x| < 1, x^(1/4) is increasing and it will tend to 1. For nth term will be x^(1/n) and as n-> infinity x^(1/n) will tend to 1.

I doubt this is the case. Remember, we are considering the sequence S(x_n), and not the sequence x_n.