Wikipedia:Reference desk/Archives/Mathematics/2008 May 31

Mathematics desk
< May 30	<< Apr | May | Jun >>	June 1 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 31

A Decreasing Sequence

While working on a problem, I came across this intermediate problem. Let $f_{n}(x)=\left({\frac {n+x}{n+2x}}\right)^{n}$. I need to show that these functions form a strictly decreasing sequence for x strictly positive. In other words, for $x>0$ I need to show that $f_{n}(x)>f_{n+1}(x)$ for all $n\in \mathbb {N}$. A couple of us have worked on this problem and we have tried all sorts of techniques (including the standard tests and treating the sequence as a continuous function of n and using the derivative test) but we either get inconclusive results or the inequality comes out the wrong way. The question is correct (there is no typo) as one can easily verify the statement by graphing a few terms. Any tips would be welcomed. Thanks guys!
A Real Kaiser (talk) 00:04, 31 May 2008 (UTC)

Well, the result is obviously true for sufficiently large x. This is the route I'm thinking would work:

For the sequence to be decreasing, we require the nth term to be less than the (n-1)th term, ie $\delta =f_{n}(x)-f_{n-1}(x)=\left({\frac {n+x}{n+2x}}\right)^{n}-\left({\frac {n+x-1}{n+2x-1}}\right)^{n-1}<0$. We want to simplify what we need to show to be negative, so multiply out the fractions to get $\delta ={\dfrac {\left[(n+x)^{n}(n+2x-1)^{n-1}-(n+x-1)^{n-1}(n+2x)^{n}\right]}{(n+2x)^{n}(n+2x-1)^{n-1}}}$. It's quite clear the denominator is positive, so we proceed by looking solely at the numerator. Now, $(n+ax-1)^{n-1}=\prod \limits _{k=0}^{n-1}(-1)^{k}(n+ax)^{n-1-k}$. I suspect that you can equate this in terms of powers of k by $(n+x)^{i}(n+2x)^{j}+(-1)^{k}(n+x)^{i+1}(n+2x)^{j-1}$. Those terms which are negative are obviously fine, and if a term is positive, it ought to have modulus less than the previous term (working from k=0 upwards). I think that should work. -mattbuck (Talk) 01:22, 31 May 2008 (UTC)

Here is an outline for proving the above:

1. Define $g_{n}(x)=Log(f_{n}(x))$.
2. Consider ${\partial g_{n}(x) \over \partial n}=0$.
3. Show that this implies $Log(1+{x \over n+2x})={nx \over (n+x)(n+2x)}$
4. Demonstrate by series expansion of the left-hand side that this equation has no solutions for x > 0.
5. Explain why knowing that is sufficient to solve the problem.

Dragons flight (talk) 02:32, 31 May 2008 (UTC)

Consider the logarithm of your function

$\log f_{n}(x)=\log \left({\frac {n+x}{n+2x}}\right)^{n}=n\log \left({\frac {1+{\frac {x}{n}}}{1+{\frac {2x}{n}}}}\right)=-n\log \left({1+{\frac {2x}{n}}}\right)+n\log \left({1+{\frac {x}{n}}}\right)$

substitute $x=-ny$

$\log f_{n}(-ny)=-n\log \left(1-2y\right)+n\log \left(1-y\right)$

series expansion of the logarithms, convergent for |2y|<1 (or n>2|x|)

$\log f_{n}(-ny)=n\sum _{i=1}^{\infty }{\frac {\left(2y\right)^{i}}{i}}-n\sum _{i=1}^{\infty }{\frac {y^{i}}{i}}=n\sum _{i=1}^{\infty }{\frac {2^{i}-1}{i}}y^{i}$

reinsert x:

$\log f_{n}(x)=n\sum _{i=1}^{\infty }{\frac {2^{i}-1}{i}}\left({\frac {-x}{n}}\right)^{i}=-x+{\frac {3x^{2}}{2n}}-\cdots$

For fixed x, for sufficiently big values of n, the series is convergent and the omitted terms are neglegible, and so the sequence f_n(x) is strictly decreasing. It remains to be shown that this is also the case for smaller values of n. Bo Jacoby (talk) 07:47, 31 May 2008 (UTC).

Wow guys, a couple of really good answers. But Dragons flight, in your step three shouldn't it be

$Log\left(1+{\frac {x}{n+x}}\right)={\frac {nx}{(n+2x)(n+x)}}$.

This is how I did it all. I will show all the steps. Maybe I made a stupid mistake somewhere.

Let $f_{n}(x)=\left({\frac {n+x}{n+2x}}\right)^{n}$.

Let $g_{n}(x)=\ln(f_{n}(x))=n\ln(n+x)-n\ln(n+2x)$.

${\frac {\partial g_{n}(x)}{\partial n}}=\ln(n+x)+{\frac {n}{n+x}}-\ln(n+2x)-{\frac {n}{n+2x}}=0$

$\Rightarrow \ln(n+x)-\ln(n+2x)={\frac {n}{n+2x}}-{\frac {n}{n+x}}$

$\Rightarrow \ln \left({\frac {n+x}{n+2x}}\right)={\frac {-nx}{(n+2x)(n+x)}}$

$\Rightarrow \ln \left({\frac {n+2x}{n+x}}\right)={\frac {nx}{(n+2x)(n+x)}}$

$\Rightarrow \ln \left({\frac {n+x}{n+x}}+{\frac {x}{n+x}}\right)=\ln \left(1+{\frac {x}{n+x}}\right)={\frac {nx}{(n+2x)(n+x)}}$.

And then, from here how can we conclude that this can't have a solution for x>0? I expanded the series for log(1+y) and plugged in x/(n+x).

$\ln(1+y)=x-{\frac {x^{2}}{2}}+{\frac {x^{3}}{3}}-{\frac {x^{4}}{4}}+{\frac {x^{5}}{5}}-...$

$\Rightarrow \ln(1+{\frac {x}{n+x}})={\frac {x}{n+x}}-{\frac {x^{2}}{2(n+x)^{2}}}+{\frac {x^{3}}{3(n+x)^{3}}}$

But how does this show me that this expression cannot equal to ${\frac {nx}{(n+x)(n+2x)}}$ for any positive x. Even if I perform partial fraction decomposition (treating n as a variable and x as a constant), I get that

${\frac {nx}{(n+x)(n+2x)}}={\frac {2x}{n+2x}}-{\frac {x}{n+x}}$

but I still don't see how that helps us. Should I equate the coefficients? I can equate the fraction with the denominator n+x but what about the one with n+2x? There is nothing on the other side with that same denominator. Now assuming that, I can show this, I even understand the last step The last one is that basically our function's $g_{n}(x)$ derivative is never zero. Therefore (as a function of n) the derivative is either always strictly positive or negative. We plug in n=1 and see that the derivative

${\frac {\partial g_{1}(x)}{\partial n}}=\ln \left({\frac {1+x}{1+2x}}\right)+{\frac {x}{(1+x)(1+2x)}}$

is always negative for x>0. Which means that the derivative is always negative for all n which means that our original function $g_{n}(x)$ is a strictly decreasing function of n which means that the first function $f_{n}(x)=e^{g_{n}(x)}$ is also a strictly decreasing function of n because the exponential is a continuous increasing function and hence it preserves the inequality.A Real Kaiser (talk) 01:49, 1 June 2008 (UTC)

shortest distance in a circle

If you have to move in a circle (i.e. go from degree 300 to 0 or 45 to 90), how you can calculate the shortest distance? Or should you just discard every result above 180 and go to the other one. Is there a formula that always gives the shortest distance? —Preceding unsigned comment added by 217.168.1.77 (talk) 00:30, 31 May 2008 (UTC)

Well, do you mean the direct distance (as the crow flies)? If so, use the cosine rule. For movement by degrees, yes discard anything over 180 and go the other direction. For movement around circumference measured in units or whatever, multiply the circumference by degrees moved and divide by 360. -mattbuck (Talk) 00:49, 31 May 2008 (UTC)

If you're looking for a single expression to give you the shortest distance in the range -180 to +180, you can use modulo operation. Something like: ((angle₂ - angle₁ + 180) mod 360) - 180. Take the absolute value if you only want the magnitude. -- Tcncv (talk) 03:30, 31 May 2008 (UTC)

Assuming that angle mod 360 returns a value in the range from 0 to 360−, if you only want the magnitude, you can also use

min((angle₁ - angle₂) mod 360, (angle₂ - angle₁) mod 360).

 --Lambiam 07:23, 31 May 2008 (UTC)

Mordell Curve

I've looked at your article on the Mordell Curve, which doesn't tell me what I want. I want the parametric form of the Mordell Curve (fixed k = 1), ie y^2 = x^3 + 1. This would help me a lot in anti-differentiating tough functions.

In other words, I want something in the form y = f(t) and x = g(t) that describes y^2 = x^3 + 1.

Is this impossible? It says Euler found the only three integer solutions to the equation, but is there a general solution in terms of a parameter?

I suspect that the solution f(t) = t, g(t) = (t² − 1)^1/3 will not satisfy you.  --Lambiam 07:15, 31 May 2008 (UTC)

The equivalent quadratic equation

$y^{2}=x^{2}+1$

(which is, of course, the equation of an hyperbola) is parameterised by the hyperbolic functions

$y=f(t)=\cosh(t),\quad x=g(t)=\sinh(t)$

Notice that f(t) and g(t) satisfies the differential equations

$g'=f$

$(g')^{2}=g^{2}+1$

For the cubic case you can do the same trick if you have a g(t) that satisfies

$(g')^{2}=g^{3}+1$

The functions that parameterise elliptic curves in this way are called Weierstrass's elliptic functions. They are similar to the trigonometric and hyperbolic functions, except that they have two periods, not one. Gandalf61 (talk) 09:55, 31 May 2008 (UTC)

Thanks Gandalf. The only problem is, trying to find (g')^2 = g^3 + 1 leads me to attempting to find the integral of 1/√(g^3+1) with respect to g, which I was trying to do in the first place. I assume, then, that my integral can be expressed in terms of this Weierstrass function?

I think so, but the simplest expression seems to be in terms of a Hypergeometric series: $\int {\frac {1}{\sqrt {x^{3}+1}}}dx=-x\cdot {}_{2}F_{1}\left({\frac {1}{3}},{\frac {1}{2}};{\frac {4}{3}};-x^{3}\right)$. -- Meni Rosenfeld (talk) 10:29, 2 June 2008 (UTC)

Armonic functions

Suppose u(x,y,z) is armonic in $R^{3}$ and

$\int _{R^{3}}|\nabla u|^{2}<\infty$

can we conclude that u is a constant function on $R^{3}$? --89.97.102.209 (talk) 16:34, 31 May 2008 (UTC)

My gut feeling is yes, u must be constant (in fact, u must be identically zero because any other constant has unbounded integral), but I can't think of a nice proof yet. The maximum principle will surely be useful. (BTW, in English it's spelled harmonic, not armonic.) —Keenan Pepper 17:28, 31 May 2008 (UTC)

Huh? Any constant is possible, since any constant function has zero gradient. Algebraist 18:25, 31 May 2008 (UTC)

Well, any constant will surely satisfy this but that doesn't mean that ONLY a constant will satisfy this inequality. I mean, what if we had the modulus come out to be a decaying exponential which will have a finite volume in all of R^3?A Real Kaiser (talk) 19:49, 31 May 2008 (UTC)

Sorry, forgot about that gradient operator for a second. —Keenan Pepper 19:59, 31 May 2008 (UTC)

Ah, I see a proof now. If u(x,y,z) is a harmonic scalar field ($\nabla ^{2}u=0$), then $\nabla u$ is a vector field with zero divergence ($\nabla \cdot (\nabla u)=0$). It also has zero curl, because the curl of a gradient is zero. Now simply consider the Helmholtz decomposition of $\nabla u$. —Keenan Pepper 20:09, 31 May 2008 (UTC)

game theory question about tennis

I have a question about tennis that's fundamentally a game theory or math problem. It could be generalized to other games with similar scoring structures. The question is, should a player pursue a different strategy during game, set, or match points (either about to lose or about to win) than he would during other points? This is ignoring psychological factors such as surprising the opponent by changing one's strategy. It seems that there is a natural tendency to want to play more conservatively during a match point. But intuitively, it also seems that the rational thing is to stay with the strategy you had used and considered optimal during the rest of the game. However, on the other hand, the outcomes of match points have greater variance than the outcomes of entire matches because the sample sizes are smaller. So players with superior opponents will do better during match points than during entire matches. --MagneticFlux (talk) 20:14, 31 May 2008 (UTC)

You might get better answers if you clarify your question for those of us not familiar with tennis scoring. If I understand Tennis score correctly, games have no time limit, and thus the points are played independently of each other. This means that there are only two possible outcomes for each point - "win" and "lose", and so the only parameter is the probability of winning the point. If we ignore factors such as psychology and fatigue, the optimal strategy (which maximizes this probability) does not depend on "the big picture". However, it certainly can depend on who the opponent is. -- Meni Rosenfeld (talk) 20:46, 31 May 2008 (UTC)

I would argue that it is rational to play more conservatively for your opponent's match-point than for an ordinary point. If you lose your opponent's match-point, you lose the match but if you lose one of the other points, the match goes on. So it's not about surprising your opponent but about playing less risky shots to allow for the heavier downside of losing match-points. I'm not sure if this is the psychological factor you're considering ignoring but I wouldn't ignore it. Zain Ebrahim (talk) 22:08, 31 May 2008 (UTC)

No (again under the assumption that I understand the rules and the points are independent). For a match point, if you win it, you win the match. If you lose it, you lose the match the match goes on and you might lose it. So, you want to win the point, and since this is a boolean random variable, you want to maximize the probability of winning. If it was any other point, you would want to... maximize the probability of winning. There is no difference. -- Meni Rosenfeld (talk) 22:17, 31 May 2008 (UTC)

Not quite - if you lose a match point, the match carries on. The way tennis rules work, it's impossible for both players to be able to win on a single point (you have to win by at least two points). --Tango (talk) 22:21, 31 May 2008 (UTC)

Yeah, I don't know why I wrote that. The conclusion holds, though. -- Meni Rosenfeld (talk) 22:44, 31 May 2008 (UTC)

(edit conflict) I was thinking that, but when I considered it more, it doesn't actually hold up. As Meni says, there are only two possible outcomes, you win the point, or you lose. The optimal strategy is, therefore, to maximise your chances of winning, and that's going to be the same for any point. The idea of playing conservatively is to avoid significant loss at the expense of also avoiding significant gain, but that requires there to be something inbetween winning and losing, which there isn't in a tennis point. --Tango (talk) 22:21, 31 May 2008 (UTC)

It may be that I'm not ignoring the psychological aspect (and I don't think that one should). I was referring to the opponent's match-point (where there is significant downside but the usual upside). Compare this to an ordinary point where the upside and downside are equivalent. With the former, you'd be more interested in minimising the probability of losing the point (is this a different strategy?) where with the latter, you'd want to maximise the probability of winning. Surely, a strategy that minimises the probability of losing would be more conservative than one that maximises the probability of winning? Or have I totally missed something? Zain Ebrahim (talk) 22:41, 31 May 2008 (UTC)

[3ec] Exactly. In chess for example, there is a possibility for a tie, so if a tie or better is needed to win the match, the player should play defensively (or whatever it is that minimizes probability of losing, without caring about the division between a win and a tie). But in tennis the possibilities are more limited, and the phenomenon does not exist. -- Meni Rosenfeld (talk) 22:44, 31 May 2008 (UTC)

You either win a tennis point or you lose it. Thus the two strategies you describe are identical. Algebraist 22:43, 31 May 2008 (UTC)

Yes, if w is the probability of winning, and l is the probability of losing, then $l=1-w$ and thus maximizing the former is identical to minimizing the latter. -- Meni Rosenfeld (talk) 22:47, 31 May 2008 (UTC)

To clarify about what "match point" means, it could be either the point on which you are one point away from winning, or the point on which your opponent is one point away from winning. --MagneticFlux (talk) 20:16, 1 June 2008 (UTC)

Permutations

Hi, I've got a question which i'm a bit stuck with. The question gives a permutation $\pi =(13742)(173)(5867)$, then asks to find a permutation $\sigma$ in $S_{9}$ with $\sigma ^{4}=\pi$ or to prove $\sigma$ cannot exist.

I've had a little attempt, but i don't think i understand the question properly, so a little explanation would be greatly appreciated. Thanks for any help. 212.140.139.225 (talk) 22:39, 31 May 2008 (UTC)

For starters, you'll want to multiply out your expression for π. Algebraist 22:45, 31 May 2008 (UTC)

Oh sorry, i meant to put the disjoint cycle, $\pi =(142)(5867)$, is this what you mean by multiply out? Thanks.

212.140.139.225 (talk) 22:52, 31 May 2008 (UTC)

Yes. Now consider what cycle type σ would have to have. Algebraist 23:00, 31 May 2008 (UTC)

Or just the parity of $\pi$ and $\sigma ^{4}$. -- Meni Rosenfeld (talk) 23:14, 31 May 2008 (UTC)

Yes, or that. I didn't notice the easier route because I was thinking of general values of 4. Algebraist 23:22, 31 May 2008 (UTC)

Ok thanks for your help. I'm not sure i understand what you mean by parity, but here goes. I know $\pi$ is even because it has 8, an even number of inversions so $sign(\pi )=+1$, but how does this help.

Also, this is where i feel i dont understand the question, i thought $\sigma ^{4}=(\pi ^{-3})^{4}=\pi$, so $\sigma =\pi ^{-3}=\pi ^{9}$ as the order of $\pi$ is 12. But i've tried this and it doesn't work so i think theres a fault in my logic rather than assuming $\sigma$ doesn't exist. Thanks again 212.140.139.225 (talk) 23:48, 31 May 2008 (UTC)

I don't follow your reasoning for π being even; what eight transpositions is it the product of? And $(\pi ^{-3})^{4}=\pi ^{-12}$. Algebraist 23:52, 31 May 2008 (UTC)

8 Inversions i have a feeling that is completely unrelated. I think there are 5 transpositions $(14)(42)(58)(86)(67)\ ((33)(99))$ so the cycle is odd.(?)

I probably confused myself with the second point. But since $\pi =\pi ^{13}$ would it be as simple to say $\sigma =(\pi ^{13})^{\frac {1}{4}}=\pi ^{\frac {13}{4}}$ and since the exponent has to be an integer there is no $\sigma$? Thanks again 212.140.139.225 (talk) 00:13, 1 June 2008 (UTC)

It's simpler than that. $\pi$ is odd, therefore so is $\sigma ^{4}$. $\sigma$ is either even, or odd. Try each case and see what happens. --Tango (talk) 00:18, 1 June 2008 (UTC)

(ec)Yes, π is odd. What is the parity of σ⁴? The argument you suggest does not work. Firstly, you have not considered the possibility (for example) that $\sigma =(\pi ^{25})^{\frac {1}{4}}$ (since π=π²⁵), but this can be dealt with. More importantly, all this shows is that σ cannot be a power of π. This does not mean σ cannot exist: for example, taking π=(12)(34), we have π=σ² (where σ=(1324)), even though π has order two. Algebraist 00:24, 1 June 2008 (UTC)

Thanks for the replies, as $\pi$ is odd $\sigma ^{4}$ is odd, i don't know if this applies but with numbers if $\sigma ^{4}$ is odd then $\sigma$ is odd. Is this at all helpful, i feel theres something blidingly obvious i'm missing, I'm new to the idea of cycles so please explain if you feel i'm not understanding it. Thanks again 212.140.139.225 (talk) 00:45, 1 June 2008 (UTC)

The key thing with parity (that is, evenness and oddness) is that it doesn't depend on how you write it. You can write the same permutation using numerous different products of transpositions and it will either always be even or always be odd (for example (12)=(12)(34)(34), one has 1 transposition, the other 3, both are odd numbers). That means you don't have to worry about simplifying $\sigma ^{4}$ to get a minimal number of transpositions, you can just write it as a long sequence of them. If $\sigma$ has n transpositions, how many will $\sigma ^{4}$ have before any simplification? --Tango (talk) 11:49, 1 June 2008 (UTC)

If a permutation is decomposed into a product of disjoint cycles, then a power of that permutation is the product of the corresponding powers of these cycles. For example, ((1 3 4)(2 7 5 6))⁵ = (1 3 4)⁵(2 7 5 6)⁵. A power γⁿ of a cyclic permutation γ is a product of disjoint cycles, all having the same order. For example, (1 5 9 3 2 8 7 4 6)³ = (1 3 7)(2 4 5)(6 9 8). The number of these component cycles and their order depends solely on n and the order of γ. For what orders of γ does γ⁴ have component cycles of order 4?  --Lambiam 08:41, 1 June 2008 (UTC)

That seems overly confusing... It's actually a really simple problem once you spot how to do it. --Tango (talk) 11:49, 1 June 2008 (UTC)

I'd say this approach is more instructive, actually, since it (without too much difficulty) solves all problems of this form, not just the ones that happen to allow parity tricks. Algebraist 00:17, 2 June 2008 (UTC)

Is there a way of knowing which powers of γ will have how many factors?

Clearly the order of those factors has to divide the order of γ. The prime order, and order 2^m are pretty simple, but for instance is there a way of knowing that (1 5 9 3 2 8 7 4 6)³ was going to be a product of 3 cycles without working it out?

I think a cycle γ of length k can only break into smaller cycles when n divides k, because of the order of γⁿ. But does it always? If so how do you know what lengths of cycles it breaks into? GromXXVII (talk) 11:06, 2 June 2008 (UTC)

A k-cycle, raised to the power n, becomes hcf(n,k) (k/hcf(n,k))-cycles. Algebraist 11:57, 2 June 2008 (UTC)

[ec] It may help to consider that a cycle and its powers form a cyclic group. The length of cycles in a power is the order of the element, which is $k/\mathrm {gcd} (k,n)$, and the number of cycles is $\mathrm {gcd} (k,n)$ (thus breaking occurs not only when n divides k, but when n and k have a common factor). -- Meni Rosenfeld (talk) 12:01, 2 June 2008 (UTC)