Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

October 1

Transforming 3 points to a new coordinate plane in 3D Cartesian space

Resolved

Hello,

I've inherited some C code that, among other things, takes three points specified in one 3D Cartesian coordinate system and (indirectly) converts their coordinates to a new coordinate system. For the first two points, the process by which this is done is quite clear. However, for the third point, I can't seem to figure out how the expressions used to determine the X and Y coordinates of the point were derived. Although I could just assume that the code is working fine and move on, I'd like to understand the logic behind the calculations.

I've included the expressions used to determine the coordinates of the three points in the new coordinate system below. In terms of notation, I refer to the points as P1, P2, and P3; the subscripts denote the coordinate (x, y, or z) and the coordinate system (O = old, N = new). For (hopefully) added clarify, I've made the coordinates specified in the old coordinate system red and those in the new coordinate system blue. The coordinates in the old coordinate system are known prior to these computations.

Point 1

${\color {blue}{\mathit {P1}}_{xN}}=0\,$

${\color {blue}{\mathit {P1}}_{yN}}=0\,$

${\color {blue}{\mathit {P1}}_{zN}}=0\,$

This simply indicates that point 1 is the origin of the new coordinate system.

Point 2

${\color {blue}{\mathit {P2}}_{xN}}={\sqrt {({\color {red}{\mathit {P2}}_{xO}}-{\color {red}{\mathit {P1}}_{xO}})^{2}+({\color {red}{\mathit {P2}}_{yO}}-{\color {red}{\mathit {P1}}_{yO}})^{2}+({\color {red}{\mathit {P2}}_{zO}}-{\color {red}{\mathit {P1}}_{zO}})^{2}}}\,$

${\color {blue}{\mathit {P2}}_{yN}}=0\,$

${\color {blue}{\mathit {P2}}_{zN}}=0\,$

This is also straight-forward: the intent is clearly for point 2 to lie on the x axis of the new coordinate system and its position on the x axis to be the magnitude of the vector connecting point 1 and point 2 in the original coordinate system (i.e. the distance between them).

Point 3

${\color {blue}{\mathit {P3}}_{xN}}=\left({\frac {({\color {red}{\mathit {P3}}_{xO}}-{\color {red}{\mathit {P1}}_{xO}})({\color {red}{\mathit {P2}}_{xO}}-{\color {red}{\mathit {P1}}_{xO}})+({\color {red}{\mathit {P3}}_{yO}}-{\color {red}{\mathit {P1}}_{yO}})({\color {red}{\mathit {P2}}_{yO}}-{\color {red}{\mathit {P1}}_{yO}})+({\color {red}{\mathit {P3}}_{zO}}-{\color {red}{\mathit {P1}}_{zO}})({\color {red}{\mathit {P2}}_{zO}}-{\color {red}{\mathit {P1}}_{zO}})}{\color {blue}{\mathit {P2}}_{xN}}}\right)\,$

${\color {blue}{\mathit {P3}}_{yN}}={\sqrt {({\color {red}{\mathit {P3}}_{xO}}-{\color {red}{\mathit {P1}}_{xO}})^{2}+({\color {red}{\mathit {P3}}_{yO}}-{\color {red}{\mathit {P1}}_{yO}})^{2}+({\color {red}{\mathit {P3}}_{zO}}-{\color {red}{\mathit {P1}}_{zO}})^{2}-({\color {blue}{\mathit {P3}}_{xN}})^{2}}}\,$

${\color {blue}{\mathit {P3}}_{zN}}=0\,$

This where things get a bit confusing (for me, at least). Since the new Z coordinate for point 3 is set to zero, clearly points 1, 2, and 3 are being used to define the XY plane of the new coordinate system. Points 1 and 2 have already defined the X axis, so point 3 is then being used to define the orientation of the XY plane overall.

However, I can't figure out how the expressions for ${\color {blue}{\mathit {P3}}_{xN}}\,$ and ${\color {blue}{\mathit {P3}}_{yN}}\,$ were derived. Logically, I'd imagine that the expression for ${\color {blue}{\mathit {P3}}_{xN}}\,$ must represent some sort of projection of point 3 onto the line formed by point 1 and 2, but it's been a long time since I've done projections in 3D and unfortunately the form of this expression doesn't look familiar to me. I'm also unclear on what the expression for ${\color {blue}{\mathit {P3}}_{yN}}\,$ is getting at; it's very close to simply being the magnitude of the line connecting points 1 and 3, but then there's the presence of the additional $({\color {blue}{\mathit {P3}}_{xN}})^{2}\,$ term to be accounted for.

So, if anyone who has more familiarity with 3D coordinate transformations off the top of their head than I do has a possible explanation of how the expressions for ${\color {blue}{\mathit {P3}}_{xN}}\,$ and ${\color {blue}{\mathit {P3}}_{yN}}\,$ were derived, I'd be most appreciative!

Thanks,

Hiram J. Hackenbacker (talk) 00:56, 1 October 2010 (UTC)

P_3xN is the length of the projection of the vector from P_1O to P_3O to the vector from P_1O to P_2O. That is P_3xN = (P_3O - P_1O).(P_2O - P_1O)/||P_2O - P_1O||, where that "." denotes the dot product (see vector projection). They take advantage of the fact that ||P_2O - P_1O|| has already been calculated, since it's P_2xN. P_3yN is then just chosen in such a way to ensure that ||P_3N|| = ||P_3O - P_1O|| since those need to be equal. Rckrone (talk) 03:48, 1 October 2010 (UTC)

Thanks, Rckrone - that clears it up. Hiram J. Hackenbacker (talk) 11:56, 1 October 2010 (UTC)

Poincaré-Hopf Theorem

Assume that M is a compact, orientable, smooth manifold. Does the Poincaré-Hopf theorem tell us that a smooth vector field on M will have at most χ(M) zeros? If not then can someone give a counter example, e.g. a smooth vector field on the torus with two zeros: one with index −1 and one with index +1. — Fly by Night (talk) 09:29, 1 October 2010 (UTC)

No it doesn't mean that (that would be the converse). I can't think at the moment of an example exactly like you say, but here's the standard example of a vector field on the torus with four zeros: Stand the torus up on vertically on its end, and dump syrup on the top of it. The syrup will flow down the torus, and use this flow to define a vector field. This will have four zeros: one at the top (source), one at the bottom (sink), and one at each of the top and bottom of the inner circle (saddles). So there's 4 zeros, of index +1, +1, -1, -1. (This example, with a good picture, is in Guillemin + Pollack's Differential Topology.) You can probably tweak this to make it have 2 zeros. Staecker (talk) 11:53, 1 October 2010 (UTC)

basic combinatorics

Resolved

I am trying to deduce a formula for the number of partitions of an integer, say f(n) where order of the integers dont matter. For example 4 can be written in 8 ways: 4, 2+2, 1+3, 3+1, 1+1+1+1, 1+2+1, 2+1+1, 1+1+2, so f(4)=8. This is how I proceeded: First I already had a proof of this statement: If A is the set $\{(x_{1},...x_{k}):x_{1}+...+x_{k}=n,n\in N\}$ then A has cardinality ${\tbinom {n+k-1}{k-1}}$. Since we basically need to count the number of elements in the set $\{(x_{1},...x_{k}):x_{1}+...+x_{k}=n,1\leq k\leq n\}$, so this number is $\textstyle \sum _{k=1}^{n}{\tbinom {k+n-1}{k-1}}$. How can I simplify this to get $2^{n-1}$ which is supposed to be the answer. Or is there an easier way find f(n)? Thanks. Also regarding the fact of which I already have a proof of, namely, A has cardinality ${\tbinom {n+k-1}{k-1}}$, the proof I have relies on an argument of making bars in between blanks, and actually deals with making selections with repetitions. Is there a wikipedia article about this technique. Thanks-Shahab (talk) 11:14, 1 October 2010 (UTC)

First see Bell number. Then see Multiset#Multiset_coefficients and stars and bars (probability). Bo Jacoby (talk) 11:20, 1 October 2010 (UTC).

I have read them, thanks. "Stars and bars" answers my second question completely. But I am still at a loss for showing $\textstyle \sum _{k=1}^{n}{\tbinom {k+n-1}{k-1}}=2^{n-1}$ to answer my original question. Also I am not sure why you linked Bell numbers.-Shahab (talk) 11:50, 1 October 2010 (UTC)

The arrangements that you are counting are called compositions. Since each of your x_i must be at least 1, the cardinality of A, the compositions of n with k parts, is in fact

${\tbinom {n-1}{k-1}}$

It is true that

$\sum _{k=1}^{n}{\tbinom {n-1}{k-1}}=2^{n-1}$

but a simpler way to count the total number of compositions of n is given in Composition (number theory)#Number of compositions. Gandalf61 (talk) 11:52, 1 October 2010 (UTC)

Thanks a ton!-Shahab (talk) 12:12, 1 October 2010 (UTC)

using CAS to find the catenary parameter a that will give us a curve that will pass through a given point

I want to find the equation of a catenary curve that will pass through the origin and a given (x,y) and (-x,y).

I see that a catenary is described by y=a*cosh(x/a). Since I want my curve to pass through the origin I will just subtract a to move it down to zero at x=0 so my new equation becomes y=a*cosh(x/a)-a. I figure that I can just solve for a in terms of the other variables but when I try to use a CAS (like ti-89 and wolframalpha) I get strange results. If i substitute actual values for x and y I can get a correct approximate numerical result but I cannot get a general equation of a in terms of x and y.

I am expecting that there can only be one value of a to satisfy a given (x,y) but apparently I am wrong. I have tried restricting the domains of a,x and y positive numbers less than infinity but I still can't work it out. Why can't I get a simple single result for a? Thanks so much. --- Diletante (talk) 20:41, 1 October 2010 (UTC)

I think a numerical solution is the best you can hope for since there isn't a way to solve for a with standard functions. The good news is that it's pretty easy reduce the problem to finding the inverse of a single function, namely (1/x)(cosh x -1).--RDBury (talk) 04:27, 2 October 2010 (UTC)

Set α=1/a. Then your equation y=a*cosh(x/a)−a is written cosh(xα)−yα−1=0. The left hand side is a nice entire function of α, and the equation is solved by a root-finding algorithm. Bo Jacoby (talk) 10:48, 2 October 2010 (UTC). The uninteresting solution α=0 is removed by division: $\textstyle -y+{\frac {\cosh(x\alpha )-1}{\alpha }}=0$, and the series expansion is $\scriptstyle -y+{\frac {x^{2}}{2!}}\alpha +{\frac {x^{4}}{4!}}\alpha ^{3}+\cdots =0$. The first approximation $\scriptstyle \alpha ={\frac {2y}{x^{2}}}$ is improved by Newton's method. Bo Jacoby (talk) 21:54, 2 October 2010 (UTC).

Thanks for the good answers. I will be honest and say that all this is a little bit beyond my ability to understand, but I am going to try my best to remember what I learned about approximation in cal 2 and read the articles Bo Jacoby linked. Thanks alot everyone! -- Diletante (talk) 02:08, 3 October 2010 (UTC)

Your premise is correct: Given $x\neq 0$ and y, there is a unique value a for which y=a*cosh(x/a)-a. There is thus a function $f(x,y)$ which gives for any values of x and y the corresponding value of a. However, just because the function exists doesn't mean it can be described in a nice "traditional" form, and indeed this function cannot. What you do next depends on your application. If you just want to be able to take numerical values of x, y and get a, I understand your calculator can already do this for you. You can also find a formula which gives an approximate answer. For example, if x is much larger than y, then $a\cosh(x/a)-a\approx {\frac {x^{2}}{2a}}+{\frac {x^{4}}{24a^{3}}}$, and you can solve that to find an approximate formula for a. -- Meni Rosenfeld (talk) 10:03, 3 October 2010 (UTC)

Ok I hope you all will indulge me for a little bit longer. I see that we can do a taylor series to approximate my f(x)=y. I see that we can solve the 2nd order taylor approximation to get a=2y/x^2. What i do not understand is how I can solve for a for greater orders of the taylor approximation (like the last approximation Meni gave). I take it that this is why Bo Jacoby suggested using the first approximation as a starting point to use newton's method, but I don't understand what that really means. Will newtons method allow me to write a better approximation of a algebraically, or just help me find a numerical result? In short, how can I write an approximation that is a little better than a=2y/x^2? -- 21:32, 3 October 2010 (UTC)

Newton's method is just for numerical results.

To solve the approximation I gave, you can use the method to solve cubic equations. But there's a better way to approach this.

Following RDBury's suggestion, we let $g(b)={\frac {\cosh b-1}{b}}$. We can show that $f(x,y)={\frac {x}{g^{-1}(y/x)}}$. Then we just need to find an approximation for $g^{-1}$. The series expansion of g is $g(b)={\frac {b}{2}}+{\frac {b^{3}}{24}}+{\frac {b^{5}}{720}}+\cdots$, and with some algebraic manipulations we can find as many terms as we want of the expansion $g^{-1}(c)=2c-{\frac {2c^{3}}{3}}+{\frac {26c^{5}}{45}}+\cdots$. Plugging this in, we can find $f(x,y)={\frac {x^{2}}{2y}}+{\frac {y}{6}}-{\frac {4y^{3}}{45x^{2}}}+\cdots$.

Again, this is good for small y. You can also find an approximation good for large y. Also, for any given $y/x$, you can numerically find the value and derivatives of g around that point, and from that find an expression for the values of f around it (so you can get, for example, a formula which is good when $y\approx 5x$). -- Meni Rosenfeld (talk) 08:56, 4 October 2010 (UTC)

You want to find the value of $\scriptstyle \alpha$ for which $\scriptstyle f(\alpha )$ = 0, where $\scriptstyle f(\alpha )$ = $\scriptstyle {\frac {\cosh(x\alpha )-1-\alpha y}{\alpha }}$ ≈ $\scriptstyle {\frac {x^{2}}{2}}\alpha -y.$ A first approximation is $\scriptstyle \alpha _{1}$ = $\scriptstyle {\frac {2y}{x^{2}}}.$ The derivative is, according to the quotient rule, $\scriptstyle f'(\alpha )$ = $\scriptstyle {\frac {x\alpha \sinh(x\alpha )-\cosh(x\alpha )+1}{\alpha ^{2}}}.$ Newton's method is not just for numerical results. The second Newton approximation is $\scriptstyle \alpha _{2}$ = $\scriptstyle \alpha _{1}-{\frac {f(\alpha _{1})}{f'(\alpha _{1})}}$ = $\scriptstyle {\frac {\alpha _{1}f'(\alpha _{1})-f(\alpha _{1})}{f'(\alpha _{1})}}$ or

$\alpha _{2}={\frac {{\frac {x\alpha _{1}\sinh(x\alpha _{1})-\cosh(x\alpha _{1})+1}{\alpha _{1}}}-{\frac {\cosh(x\alpha _{1})-1-y\alpha _{1}}{\alpha _{1}}}}{\frac {x\alpha _{1}\sinh(x\alpha _{1})-\cosh(x\alpha _{1})+1}{\alpha _{1}^{2}}}}$ $=\alpha _{1}{\frac {x\alpha _{1}\sinh(x\alpha _{1})-2\cosh(x\alpha _{1})+2+y\alpha _{1}}{x\alpha _{1}\sinh(x\alpha _{1})-\cosh(x\alpha _{1})+1}}$

This approximation $\alpha _{2}$ is a little better than $\alpha _{1}$ = ${\frac {2y}{x^{2}}}$. Don't forget that $a={\frac {1}{\alpha }}$. So:

$a_{1}={\frac {x^{2}}{2y}}$

$a_{2}={\frac {x^{2}}{4y}}{\frac {{\frac {2y}{x}}\sinh({\frac {2y}{x}})-\cosh({\frac {2y}{x}})+1}{{\frac {y}{x}}(\sinh({\frac {2y}{x}})+{\frac {y}{x}})-\cosh({\frac {2y}{x}})+1}}$

Bo Jacoby (talk) 13:19, 5 October 2010 (UTC).

October 2

more combinatorics

Resolved

I am reading a book on combinatorics and am stuck on the following three problems:

• Why is the identity ${\tbinom {n-1}{k-1}}{\tbinom {n}{k+1}}{\tbinom {n+1}{k}}={\tbinom {n-1}{k}}{\tbinom {n}{k-1}}{\tbinom {n+1}{k+1}}$ called the hexagon identity?
• Compute the following sum: $\textstyle \sum _{k}{\tbinom {80}{k}}{\tbinom {k+1}{31}}$. I can reduce this to ${\frac {\tbinom {80}{30}}{31}}\textstyle \sum _{k}(k+1){\tbinom {50}{k-30}}$ and no further.
• Compute the following sum: $\textstyle \sum _{k\geq 0}{\frac {1}{k+1}}{\tbinom {99}{k}}{\tbinom {200}{120-k}}$. I want to use Vandermonde's convolution here but does it imply that this sum is ${\binom {209}{120}}\textstyle \sum _{k\geq 0}{\frac {1}{k+1}}$? What do I do next? I dont want any summation in the final result.

Can anyone help. Thanks-Shahab (talk) 07:19, 2 October 2010 (UTC)

You might like the book A=B. I'm not sure but it could be helpful for the last two problems. 67.122.209.115 (talk) 09:01, 2 October 2010 (UTC)

The binomial coefficients in the hexagon identity are corners of a hexagon in Pascal's triangle. The infinite series are actually finite sums, as $\textstyle {\tbinom {n}{k}}$=0 for k<0 and for k>n≥0. Bo Jacoby (talk) 10:19, 2 October 2010 (UTC).

Another nice book for learning how to do these manipulations is concrete mathematics. In your case, using generating functions seems a reasonable way for treating the sums. In particular, if you can write your expression in the form $\scriptstyle \sum _{k=0}^{m}a_{k}b_{m-k}$, you can see it as the coefficient of $\scriptstyle x^{m}$ in the power series expansion of the product: $\scriptstyle \left(\sum _{k=0}^{\infty }a_{k}x^{k}\right)\left(\sum _{k=0}^{\infty }b_{k}x^{k}\right)$ (this is the Cauchy product of power series). Note that the Vandermonde's identity is a special case of this. In your case, the task is not difficult (but ask again here if you meet any difficulty). You can do it in the first sum either in the original form (writing $\scriptstyle {\binom {80}{k}}={\binom {80}{80-k}}$; in this case you also need a closed expression for $\scriptstyle \sum _{k=0}^{\infty }{\binom {k}{r}}x^{k}$, which is related to the binomial series with exponent $-(r+1)$ ) or in your reduction, which is simpler to treat (then you need the simpler $\scriptstyle \sum _{k=0}^{\infty }(k+1)x^{k}$). Another possibility in order to proceed from your reduction is, make a substitution: $j:=k-30$ so $k+1=j+31$ and distribute: this leaves you with two sums, $\scriptstyle \sum _{j}{\binom {50}{j}}$ and $\scriptstyle \sum _{j}j{\binom {50}{j}}$ which is identity (6a) here. Your last sum is indeed close to the Vandermonde's identity, but the result you wrote is not at all correct (you should have done something very bad in the middle). You may write $\scriptstyle {\frac {1}{k+1}}{\binom {99}{k}}={\frac {1}{100}}{\binom {100}{k+1}}$; put $\scriptstyle j:=k+1$ so $\scriptstyle {\binom {200}{120-k}}={\binom {200}{121-j}}.$ to get the form of Vandermonde's identity--pma 15:53, 3 October 2010 (UTC)

Thanks pma. I hope you're well:). I solved both the problems.-Shahab (talk) 02:40, 6 October 2010 (UTC)

Second moment of the binomial distribution

The moment generating function of the binomial distribution is $(1-p+pe^{t})^{n}$. When I take the second derivative I get $n(n-1)(1-p+pe^{t})^{n-2}p^{2}e^{2t}+n(1-p+pe^{t})^{n-1}pe^{t}$. Substituting 0 in for t gives me $n(n-1)p^{2}+np$. Why is this not the same as the variance of the binomial distribution $np(1-p)$?--220.253.253.56 (talk) 11:34, 2 October 2010 (UTC)

See cumulant. Bo Jacoby (talk) 11:51, 2 October 2010 (UTC).

The variance is not the same thing as the raw second moment. The variance is

$E((X-\mu )^{2})\,$

where μ is E(X). The second moment, on the other hand, is

$E(X^{2}).\,$

Michael Hardy (talk) 22:30, 2 October 2010 (UTC)

Then why does the article moment (mathematics) say that the second moment is the variance?--220.253.253.56 (talk) 22:50, 2 October 2010 (UTC)

It doesn't. Algebraist 22:53, 2 October 2010 (UTC)

Moment_(mathematics)#Variance--220.253.253.56 (talk) 23:00, 2 October 2010 (UTC)

There are eighteen words in that section. You seem to have neglected to read the third. Algebraist 23:03, 2 October 2010 (UTC)

So what is a central moment and how are they calculated (can you use the moment generating function)?--220.253.253.56 (talk) 23:05, 2 October 2010 (UTC)

Central moment might help. 129.234.53.175 (talk) 15:52, 3 October 2010 (UTC)

In Moment_(mathematics)#Variance, I've now added a link to central moment. Michael Hardy (talk) 02:48, 4 October 2010 (UTC)

There is already a link to Central moment in Moment (mathematics). I think the guideline is not to link to the same article twice. -- Meni Rosenfeld (talk) 08:28, 4 October 2010 (UTC)

Where is that guideline? To me that seems unwise in long articles. Michael Hardy (talk) 19:44, 4 October 2010 (UTC)

Wikipedia:Manual of Style (linking)#Repeated links. It does mention as an exception the case where the distance is large, but here the instances are quite close in my opinion. -- Meni Rosenfeld (talk) 20:35, 4 October 2010 (UTC)

More Limits

Hello. How can I prove $\lim _{x\rightarrow \infty }x^{a}e^{-x}=0,\forall a\in \mathbb {R}$? I tried l'Hopital's rule but get $\lim _{x\rightarrow \infty }{\frac {ax^{a-1}}{e^{x}}}={\frac {\infty }{\infty }}$. Thanks very much in advance. --Mayfare (talk) 15:19, 2 October 2010 (UTC)

Forget l'Hopital's rule and try to visualise what is happening. If a < 0 then both x^a and e^-x tend to 0 as x grows, so the result is obvious. The case a=0 is also easily dealt with. If a > 0 then as x gets larger, x^a grows but e^x grows even more quickly. In fact, if x > 0, then

$e^{x}>{\frac {x^{m}}{m!}}$

where m is the next integer greater than a. So

$x^{a}e^{-x}<{\frac {m!}{x^{m-a}}}$

I'll let you take it from there. Gandalf61 (talk) 16:06, 2 October 2010 (UTC)

It might not be obvious to the questioner that exponentials grow faster than polynomials (or even what a statement like that means). Mayfare, if you want to use l'Hôpital's rule for this, imagine using it over and over until you don't get ∞/∞ any more. What is going to happen? The exponent in the numerator is going to decrease by 1 each time you use the rule, while the denominator stays the same. So what can you conclude? —Bkell (talk) 17:52, 2 October 2010 (UTC)

If the questioner does not understand that an exponential function grows faster than any polynomial, or why this is implied by

$e^{x}=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}$

then they cannot understand why $\lim _{x\rightarrow \infty }x^{a}e^{-x}=0$. At best they are reproducing a method (l'Hôpital's rule) learnt by rote, without understanding. Once they do understand the behaviour of exponential functions then the result is intuitively obvious and a formal proof is easily found. Gandalf61 (talk) 09:25, 3 October 2010 (UTC)

While you can take Bkell's suggestion and work that into a proof, I would suggest using the definition of a limit directly. That is $\lim _{x\rightarrow \infty }x^{a}e^{-x}$ equals 0 if for every ε>0 there exists a δ such that if x>δ then |x^a e^^-x|<|ε|. Note that x^a and e^^-x are both eventually monotone functions. Can you solve |x^a e^x|=|ε| ? Taemyr (talk) 18:24, 2 October 2010 (UTC)

L'Hopital's rule will do it if you iterate it: a becomes a − 1, then after another step it's a − 2, and so on. After it gets down to 0 is less, the rest is trivial. However, there's another way to view it: every time x is incremented by 1, e^x gets multiplied by more than 2, whereas the numerator x^a is multiplied by less than 2 if x is big enough. Therefore it has to approach zero. Michael Hardy (talk) 22:27, 2 October 2010 (UTC)

Noticing that x^a = exp(a ln x) is useful. Then

$\lim _{x\rightarrow \infty }{\frac {a\ln x}{x}}=a\lim _{x\rightarrow \infty }{\frac {1}{x}}=0.$

Since exp(x) is an increasing function, the original product must also go to 0. —Anonymous Dissident^Talk 01:53, 3 October 2010 (UTC)

This seems highly questionable to me. Showing that the ratio of the exponents goes to zero does not prove that the ratio of the original functions goes to zero. For example consider the constant functions f(x) = 1 and g(x) = e.

$\lim _{x\rightarrow \infty }{\frac {\ln f(x)}{\ln g(x)}}=\lim _{x\rightarrow \infty }{\frac {0}{1}}=0.$

but clearly f(x)/g(x) does not go to zero. What you actually need is for the difference in the exponents to go to negative infinity, but that's not any easier to prove than the original problem. Rckrone (talk) 02:17, 3 October 2010 (UTC)

I think it does if both functions are increasing. Your counter-examples seem a little trivial, since they are constant functions (which do not change, let alone strictly increase). Perhaps you are correct in general, but in this case the result seems quite clear. —Anonymous Dissident^Talk 02:24, 3 October 2010 (UTC)

I picked a trivial counter example because it's easy to consider. Here is a case with strictly increasing functions: f(x) = (x-1)/x, g(x) = ef(x). Anyway, I was wrong before about taking logs not helping. If you consider ln(x^ae^-x), which is aln(x) - x, you can show it goes to negative infinity by arguing that the derivative a/x - 1 goes to -1. I guess that's not too bad. Rckrone (talk) 02:32, 3 October 2010 (UTC)

Okay, point well taken. —Anonymous Dissident^Talk 03:02, 3 October 2010 (UTC)

If the OP was thrown off by $a\in \mathbb {R}$ but has already proven that $\lim _{x\rightarrow \infty }x^{n}e^{-x}=0,\forall n\in \mathbb {N}$, then consider applying the squeeze theorem with g(x)=xⁿe^-x and h(x)=x^me^-x where n≤a≤m. See also floor and ceiling functions. -- 124.157.254.146 (talk) 02:52, 3 October 2010 (UTC)

And in case the OP didn't catch the remark by Rckrone above, x^a = e^{a ln(x)} so x^ae^-x = e^{a ln(x) - x} and it can be shown that a ln(x) - x → -∞ as x → +∞. -- 124.157.254.146 (talk) 05:50, 3 October 2010 (UTC)

October 3

k = x + 1/x

Why is this equation so ridiculously difficult to solve using standard high school algebra methods? I can only seem to solve it by running it through Mathematica. John Riemann Soong (talk) 00:58, 3 October 2010 (UTC)

You're solving for x, right? If you multiply through by x you get x² - kx + 1 = 0 and then you can hit it with the quadratic formula. Rckrone (talk) 01:27, 3 October 2010 (UTC)

I just realised this. I actually started from the lens equation (k = S/f - 2, where S and f are known constants) and did a lot of rearranging to get k = di/do + do/di. Must have been too fatigued to realise that having a non-constant term on the other side would be a good thing. John Riemann Soong (talk) 01:55, 3 October 2010 (UTC)

Writing a puzzle

Good evening. I'm trying to write a puzzle but I don't know how to state it right. It's going to start like "Find the greatest value of <some f(x)>" and the solution should require changing f(x) somehow to a polynomial function g(x) (I think g(x) might be x^<some large constant>, but I'm not sure on that) that can be evaluated by taking the nth derivative of g(x) such that it is a constant (that is also the maximum of f(x)) and the n+1th (and every subsequent) is zero. I saw this problem way back when I was studying Calculus in high school and I want to give it to my students. The problem is I can't quite think of how it goes, namely what f(x) to use and how it is turned to g(x). I do remember that there was some way to discourage people from using the derivative test for extrema, hence my guess that g(x)=x^<some large constant>. Can anyone think of a way to present this? Many thanks. PS: It's late and I'm not exactly at my best right now so this won't be the most coherent (or concise). If there are questions just leave them here and I'll get back to you in the morning. Thanks again. --Smith —Preceding unsigned comment added by 24.92.78.167 (talk) 03:29, 3 October 2010 (UTC)

I like "find the minimum of x + 1/x for x > 0". The problem above reminded me of that. 67.122.209.115 (talk) 04:02, 3 October 2010 (UTC)

(edit conflict) This doesn't exactly sound like what you're looking for, but the easiest way to find the maximum value of, say, $f(x)={\frac {2x^{3}-6x^{2}-5x+15}{3-x}}$ is to factor the numerator and cancel the common factor of $3-x$ so you get the polynomial function $g(x)=-2x^{2}+5$, which is easy to maximize. [Of course, in this example $g(x)=f(x)$ except at $x=3$.] If you try to use the derivative test on $f(x)$ directly, you have to use the quotient rule and you'll get an ugly mess. Is this example anywhere close to being on the right track? —Bkell (talk) 04:03, 3 October 2010 (UTC)

You could always compose your polynomial g(x) with a horrific but monotonically increasing function h(x) to get f(x) = h(g(x)). Say, h(x) = e^x*log(x) for x > 0, g(x) = 2x - x^2, giving the deceptively awful f(x) = e^(2x-x^2) log(2x-x^2). The largest input (2x-x^2) is 1 [2x-x^2 -> 2-2x = 0 at x=1 => 2(1)-1^2 = 1], so the answer is e^(1) log (1) = 0. Season the polynomial g(x) and the level of horror of f(x) to taste. 67.158.43.41 (talk) 16:34, 6 October 2010 (UTC)

Continued Fraction Factorisation Method - What is the point?

I've been learning ways of factorising numbers through the Congruence of Squares method, and at the moment I'm looking at the continued fraction method, whereby you use the convergents of a continued fraction expansion of Sqrt(N) in order to find a congruence of squares modulo N: I think http://www.math.dartmouth.edu/~carlp/PDF/implementation.pdf section 2 has one of the few good descriptions of the process I can find online.

However, what I'm struggling to actually see is what the actual advantage of using these convergents is - what do we gain from using the convergents, does it somehow make it easier to find the congruence of squares? Does it typically make it easier to find B-smooth numbers congruent to a square for some small set of primes B, for example? I can see the method is closely related to Dixon's method, but as I said I fail to see why the CFRAC method is actually advantageous - does it perhaps typically find that the A_n² (using the terminology of the linked CFRAC explanation) are congruent to a very small number, in which case more likely to factorise under a set of small primes? Or is it less likely to lead to a trivial factorisation, maybe?

I'd really appreciate any enlightenment - I can see why Dixon's method works, but not how this development helps. Ta very much in advance! Mathmos6 (talk) 17:14, 3 October 2010 (UTC)

Congruence of squares basically requires that you find a bunch of x′s so that x² mod N is small relative to N. The different variations of the method amount to different methods of generating the x′s. There is generally a trade off between the simplicity of the method and how quickly it works; the continued fraction falls somewhere in the middle.--RDBury (talk) 08:52, 5 October 2010 (UTC)

October 4

Name the object

I have a vector bundle $\scriptstyle \pi \,:\,E\,\twoheadrightarrow \,X$ with fibre F. At each point x ∈ X, we have a linear map S_x : F → F which varies smoothly with x. What would we call the whole object S : E → E? I think that each S_x is a type (1,1)-tensor, is that right? If that's true then is S a type (1,1)-tensor field? Any suggestions? — Fly by Night (talk) 13:28, 4 October 2010 (UTC)

Generalized Metric Space

Has anyone thought of generalizing the definition of a metric space in the following direction?

Let X be a set of points. Instead of considering the distance function d to map pairs of elements of X to nonnegative real numbers, let d map into a set S, equipped with a total order ≤, a minimum element 0, and a binary operation + for which 0 is identity and + respects the order in the sense that whenever a, b, c and d are elements of S with a ≤ c and b ≤ d, we have a+b ≤ c+d. Then copy the axioms of a Metric space over, substituting in S, 0, ≤ and + appropriately.

I can quickly think of ways to add more structure to this; this is an extreme generalization. It would certainly be useful to require + to be associative, for example, or to require that it simply be addition in a totally ordered field. My question is has anyone generalized in this direction, and is there a name for such generalized spaces? --24.27.16.22 (talk) 23:22, 4 October 2010 (UTC)

Sorry, I haven't seen such a generalization, though something similar has occurred to me. In particular, when constructing the real numbers from equivalence classes of Cauchy sequences of rationals, the distance "metric" on Q must be defined as mapping into Q instead of R, since R hasn't been defined yet. This breaks the usual definition of a metric, but can be easily solved by allowing a form of your generalization.

As you point out the set S must be totally ordered and have 0 as it's minimum. I'd say S should definitely be a group under addition: you should have inverses so that A+b <= A+c iff b <= c, commutativity so the symmetry of the metric respects swapping the order in the triangle inequality, associativity so the triangle inequality may be generalized to stopping off at n points in any order (since you're already commutative) instead of just 1 on your way between two points, and 0 as above. If S is finite, S = {0} would require the space itself to be trivial. Finite |S| > 1 wouldn't work, since 0 < a => 0 < na for all integers n, but a has finite order in the additive group S, so eventually 0 < Na = 0. So, S must be infinite or the metric space is trivial.

As for multiplicative structure... it seems quite desirable to be able to go from a < nb (n an integer, a and b in S) to a/n < b since this is used all the time in proofs. This would require a version of multiplicative inverses: going from A = na to A/n = a bijectively. So we could define multiplication on (S, positive integers) so that it's invertible, commutative (since na = an from commutativity of S under +) while special-casing 0a = a0 = 0. This gives us a somewhat horrific version of a group under multiplication. It would extend naturally to multiplication of S by rational numbers, which of course respects the order axioms, i.e. for rational q and p, q >= p iff aq >= ap, with equality holding only when q = p. We've gotten pretty close to an ordered field by now, but we're not quite there. We would definitely want distributivity of the above multiplication: a(n+m) = an + am clearly; (a+b)n = an + bn from commutativity of +; I think the inverses above should quickly imply this distributivity must extend to all rational multiplication.

Now aq = ap iff q = p means a(q-p) = 0 iff q=p iff q-p = 0 and in particular each aq for distinct rational q must be distinct. Picking an arbitrary e in S with e not 0, {eq} is isomorphic to Q at this point since addition and multiplication in {eq} can clearly be mapped to addition and multiplication in Q. So, in some sense S must contain Q as a "subfield" (quotes since S isn't itself a field and the isomorphism is nonstandard). I believe at this point we could call e "1" to give for any a in S, (eq)a = qa. In this way we could extend the multiplication above to use a subset of S itself, which must respect the standard commutative ring axioms and is invertible since Q is a field. So, it seems a reasonable metric should at the very least contain an "isomorphic" copy of Q and be a sort of mutant field under a restricted multiplication operation, which in a restricted sense is also an ordered field.

At the bare minimum, then, Q is the "smallest" space a metric should map into. Under the continuum hypothesis, R would then be the next "largest" S not possibly isomorphic to Q, though perhaps R under some restricted multiplication would also work. At the least, we're quite close to R, though not there yet. If we were to use a countable S, the set of distances between points would be countable, so the metric space itself couldn't be uncountable while preserving d(a, b) = 0 iff a = b. At least for larger metric spaces, we'd need an uncountable S, which suggests using R (at the minimum) the vast majority of the time, though again we might be able to get away without defining multiplication on all of R.

One important property of R is the least upper bound property--in fact any ordered field with the LUB property is isomorphic to R. That property is quite important for large chunks of analysis. For instance, a sum of rationals getting arbitrarily close to Sqrt(2) in R, when considered in Q, does not converge. A similar example should be constructable for any S without LUB. For calculus, the metric should almost certainly have the LUB and be very, very close to R.

So after thinking about it, perhaps you could get something interesting out of taking S to be...

1. Countable, though this may degenerate into S = Q
2. Uncountable, with or without LUB but not fully defining multiplication on S--merely define multiplication on a subset {qe} of S as above.

I imagine (1) could be truly interesting if it doesn't degenerate. It would be somewhat akin to the usual discrete vs. continuous divide and so at least heuristically shows promise. I'd guess (2) would give you large chunks of the usual theory and might give a cute little generalization of metric spaces that doesn't serve much practical use. Of course, without looking into the possibilities much more carefully, who knows? 67.158.43.41 (talk) 15:57, 6 October 2010 (UTC)

October 5

Trying to find a recent question in the archives

Resolved

I'm trying to follow a chain of links I explored in the not-too-distant past, but it's one of those things where I can't quite remember enough about it to get started. I think it started with a question asked here about a differential equation or something, and the questioner asked why the solution to the differential equation given in one of our articles contained the variable y as well as x. If I am correctly remembering where I read that, it should be here in the archives somewhere (probably in August or September), but I'm having trouble finding it. Does this ring a bell for anyone? —Bkell (talk) 02:59, 5 October 2010 (UTC)

Oh, I found it: Wikipedia:Reference desk/Archives/Mathematics/2010 September 9#Fitting a parabola and Euler's theorem. —Bkell (talk) 03:04, 5 October 2010 (UTC)

Probability: number of die throws necessary to reach a certain probability of covering all numbers

How do I calculate this:

I have a normal six-sided die. How many times do I need to throw the die to have at least at 50% probability of getting each number (1 through 6) at least once, in any order? How about if the die has 'n' sides and I want a probability of x%?

Thanks in advance219.164.239.187 (talk) 09:37, 5 October 2010 (UTC)

The probability that m independent throws of an n-sided die include all sides is ${\frac {n!}{n^{m}}}S(m,n)$, where S(m,n) is the Stirling number of the second kind.—Emil J. 11:54, 5 October 2010 (UTC)

Using the Inclusion–exclusion principle, if my calculations are correct, we can find that with m throws of an n-sided die, the probability of getting all outcomes is $\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}\left(1-{\frac {k}{n}}\right)^{m}$. Finding m given x requires solving a non-algebraic equation, but for the case $n=6,\ x=50$ you can numerically find $m\approx 12.811$ (so $m=12$ gives 43.78%, and $m=13$ gives 51.39%). -- Meni Rosenfeld (talk) 11:57, 5 October 2010 (UTC)

See also the coupon collector's problem. --Tardis (talk) 15:44, 5 October 2010 (UTC)

Thanks, you people are good! I've got it now.219.164.239.187 (talk) 00:44, 6 October 2010 (UTC)

Truncated lognormal

Hi. This is not homework. Say X is a lognormal variable (with $\mu$ and $\sigma ^{2}$) and $Y=(X|X>A)$ where A is some positive number. I would like to derive experssions for $E[Y]$ and $Var[Y]$. I know this can be done using the Truncated normal distribution but I seem to be getting stuck. Can you help? Thanks. --Mudupie (talk) 11:26, 5 October 2010 (UTC)

Mathematica gives

$\int _{A}^{\infty }{\frac {1}{x{\sqrt {2\pi \sigma ^{2}}}}}\,e^{-{\frac {\left(\ln x-\mu \right)^{2}}{2\sigma ^{2}}}}\ dx={\frac {1}{2}}\left(1+\operatorname {erf} \left({\frac {\mu -\ln A}{{\sqrt {2}}\sigma }}\right)\right)$

$\int _{A}^{\infty }{\frac {1}{x{\sqrt {2\pi \sigma ^{2}}}}}\,e^{-{\frac {\left(\ln x-\mu \right)^{2}}{2\sigma ^{2}}}}x\ dx={\frac {1}{2}}e^{\mu +\sigma ^{2}/2}\left(1+\operatorname {erf} \left({\frac {\mu +\sigma ^{2}-\ln A}{{\sqrt {2}}\sigma }}\right)\right)$

$\int _{A}^{\infty }{\frac {1}{x{\sqrt {2\pi \sigma ^{2}}}}}\,e^{-{\frac {\left(\ln x-\mu \right)^{2}}{2\sigma ^{2}}}}x^{2}\ dx={\frac {1}{2}}e^{2(\mu +\sigma ^{2})}\left(1+\operatorname {erf} \left({\frac {\mu +2\sigma ^{2}-\ln A}{{\sqrt {2}}\sigma }}\right)\right)$

From which you should be able to find the mean and the variance. -- Meni Rosenfeld (talk) 12:37, 5 October 2010 (UTC)

Thank you very much for your help. --Mudupie (talk) 08:08, 7 October 2010 (UTC)

Probability

what is probablity ?make me understand how do question —Preceding unsigned comment added by 117.199.115.19 (talk) 13:22, 5 October 2010 (UTC)

See Probability. -- Meni Rosenfeld (talk) 13:56, 5 October 2010 (UTC)

If you check out the article that Meni linked to, you will see that there are two different ways of looking at probability: The frequentist approach and the Bayesian approach. From the way you formulate your question, I'm pretty sure it's the frequentist approach that you'll want to start with. In its easiest formulation, it goes like this: if you do an experiment, with (say) six different mutually exclusive and equally likely outcomes, the probability of each outcome is one sixth. This implies that if you repeat the experiment a large number of times (for instance observing the frequency of throws of a die that result in a six), the frequency will approach the probability. That is why it is called the frequentist approach. The sum of the probabilities of all possible outcomes is defined to be one. From this definition, and from a few other simple axioms, you can develop a set of rules for calculating the probability of composite events. You can use the fact that the frequency approaches the probability "in reverse", i.e. estimate the probability of an event from the observed frequency. --NorwegianBlue ^talk 21:15, 5 October 2010 (UTC)

October 6

combinatorial identity

Resolved

How do I establish the following identity: $\sum _{k=0}^{m}{\tbinom {m}{k}}{\tbinom {n}{r+k}}={\tbinom {m+n}{m+r}}$. Also is there a book which has many exercises related to such problems. Thanks-Shahab (talk) 02:18, 6 October 2010 (UTC)

I think you need to start from ${\binom {m}{k}}={m! \over k!(m-k)!}$. You should find lots of factors in the factorials cancelling one another out. As for books, I'm sure many end-of-high-school/beginning-college stats textbooks cover this sort of thing in depth. --81.153.109.200 (talk) 05:28, 6 October 2010 (UTC)

Rewrite it as $\sum _{k=0}^{m}{\tbinom {m}{m-k}}{\tbinom {n}{r+k}}={\tbinom {m+n}{m+r}}$ and then as $\sum _{k=0}^{m}{\tbinom {m}{k}}{\tbinom {n}{l-k}}={\tbinom {m+n}{l}}$ and it should be obvious. Algebraist 09:49, 6 October 2010 (UTC)

The "best" way to prove an identity like this, from a combinatorial perspective, is not to play around with manipulating algebraic symbols but to find an interpretation so that both sides are clearly counting the same thing. (This is called double counting.) In the case of $\sum _{k=0}^{m}{\tbinom {m}{k}}{\tbinom {n}{r+k}}={\tbinom {m+n}{m+r}}$, such an interpretation might go like this: The right side clearly counts the number of ways to choose a total of m + r items out of the (disjoint) union of a set M of size m and a set N of size n. When you make such a choice, you are choosing some number of items from M to leave out—call that number k. (In other words, you pick some k items out of M not to include in your collection.) To make up for the k items you didn't include from M, you need to choose r + k items from N in order to bring the total number of chosen items to m + r, as desired. Now, the value of k (the number of items from M that were not chosen) can range from 0 to m, so the number of ways to choose a value for k, then choose k items from M to leave out, then choose r + k items from N to complete the collection, is $\sum _{k=0}^{m}{\tbinom {m}{k}}{\tbinom {n}{r+k}}$, which is the left side of the identity. Since both sides are counting the number of ways to choose a collection of m + r items from the union of M and N, they must be equal. —Bkell (talk) 13:14, 6 October 2010 (UTC)

I can't guarantee I know the BEST book or anything but I know one book that covers a huge amount of this stuff, I would think way more than any "end-of-high-school/beginning-college stats textbooks" (though those are good sources probably). It is Concrete Mathematics by Graham, Knuth, and Patashnik. Chapter 5 is Binomial Coefficients and it is over 100 pages long, including exercises. This chapter goes into stuff that may be beyond what you are looking for but at least the first 40+ pages seem to be about this sort of thing. StatisticsMan (talk) 14:02, 6 October 2010 (UTC)

Thank you all, and especially Bkell:). I have started reading from the Concrete Mathematics book.-Shahab (talk) 14:29, 6 October 2010 (UTC)

Stuck trying to prove a division problem

Hi,

I am stuck trying to prove the following: If A,B,C are positive integers and A|BC, then A|B or A|C.

Here is what i have: Assume A|BC. This means that AX = BC for some positive integer X.

My issue is trying to get A multiplied by some expression to equal B or C. If i divide both sides by C, for instance, i have AX/C = B ---> A(X/C) = B, which would prove A|B if X/C is an integer, but we dont know that X/C is an integer! How can i prove/disprove the statement? I am not looking for someone to shoot me the answer, just help me be unstuck please? :)

Thanks! 137.81.118.126 (talk) 08:18, 6 October 2010 (UTC)

The statement is false, try to find a counterexample. -- Meni Rosenfeld (talk) 08:36, 6 October 2010 (UTC)

Is it really? my intuition tells me its true. Perhaps i need to play with primes and composites then? or maybe proof by contradiction? I'll give that a thought... :) 137.81.118.126 (talk) 08:41, 6 October 2010 (UTC)

So far, im choosing B and C, trying different combinations of primes or composites, and the only thing i can make sense of is that you cant divide BC unless you have a prime that is in common with B or C.... so i really dont see how this is false. 137.81.118.126 (talk) 08:48, 6 October 2010 (UTC)

Disproof is simple - as Meni says, you just need to find a counterexample. Look at multiples of 4 or 6 to find one. To create a version of the statement that is true, you need to add an extra condition on A. Gandalf61 (talk) 08:52, 6 October 2010 (UTC)

I think i found it! Let B = C = 3, and A = 9. Then you have that 9|9, but NOT(9|3). The problem doesnt say that i cant have A = BC. Is this the way to go here? and the restriction would be A ≠ BC ? 137.81.118.126 (talk) 08:56, 6 October 2010 (UTC)

Yes, that is a counterexample (personally I would go with $6|2\cdot 3$). No, that's not the restriction, you can have this happen even when $A\neq BC$. -- Meni Rosenfeld (talk) 09:03, 6 October 2010 (UTC)

(edit conflict) I know much more about this now. It is simply that to force an error in the statement, A has to be a combination of the factors of B and C such that A > BC. This works for things too like A= 27, B=C=9. I just needed to think outside the box. Thanks alot everyone! 137.81.118.126 (talk) 09:08, 6 October 2010 (UTC)

See Euclid's lemma. Bo Jacoby (talk) 09:12, 6 October 2010 (UTC).

No, I still don't think you get it. You can't have $A>BC$ and $A|BC$. If you meant $A>B,\ A>C$ then that's still not it - think about $6|8\cdot 9$. Bo's link will give you the missing ingredient to the statement being true, but you may want to try to figure it out yourself first. -- Meni Rosenfeld (talk) 11:12, 6 October 2010 (UTC)

hmm, maybe then 6|8*9 because it contains prime factors of BOTH B and C which are exclusive? (in this case it borrows a 3 from C, and B doesnt have a 3. It also uses a 2 from B, and C has no 2. Is that what you are getting at? 137.81.118.126 (talk) 12:38, 6 October 2010 (UTC)

That's not exactly it either, consider $36|12\cdot 18$. I'm not getting at anything. It's possible to characterize the situation $A|BC,\ A\not |B,\ A\not |C$ using the prime factorizations of A, B, C. In any case, Euclid's lemma tells us that this situation is impossible if A is prime. -- Meni Rosenfeld (talk) 13:05, 6 October 2010 (UTC)

include or not to include

I am about to publish a mathematical proof and thought I would begin with a germane quotation from the Hebrew bible / "old testament". However, since I am including a bible quotation in a somewhat patronizing way (as I am not a believer in any bible), I thought I would also include a brief, pertinent quotation from the Qu'ran (the Arabic bible).

My question is, would this patronizing quotation from two ancient texts, specifically the latter, be received very negatively? Specifically, would any Jewish or Israeli readers here be offended if a math proof began with a relevant quote from the Qu'ran (after a relevant quote from Ecclesiastes)? I am not really trying to start a debate, and I might as well pull both (leaving no quote). The only reason I even think to include one is because I have seen this done a lot of times in other serious scientific works. (That introductory quote probably even has a special name, though this name escapes me at the moment). Obviously what I have seen is mostly Christian bible (/"bible as literature") quotations. someone else mentioned that while secular, Israeli high courts often quote hebrew scripture as well in their judgments, likely for the same historical flavor I am seeking.

So I would just like practical advice, your honest gut reaction please. You do not have to specify any reasons for your advice, I appreciate the advice itself most, and this is really not that big of a deal to me. Thank you. 85.181.48.173 (talk) 16:35, 6 October 2010 (UTC)

Are you writing something that is explicitly patronizing, or is it just that you feel that including a quotation without believing the Tanakh is patronizing? If the former it depends. If the latter then I don't think there should be a problem with including a quotation from either the Tanakh or the Qur'an or both. (note the position of apostrophe in Qur'an - it denotes that it is pronounced "Qur an" rather than "Qu ran".) -- Meni Rosenfeld (talk) 17:11, 6 October 2010 (UTC)

Good work Meni! — Fly by Night (talk) 19:59, 6 October 2010 (UTC)

Optimal strategy for coin flipping game

The game proceeds as follows. A player flips a coin as many times as he likes. At each stage the player has some fraction of heads of the total number of coin flips. If the player decides to stop at some point then the fraction of heads at that point is what he will win. So, if after 7 coin flips the player has 4 heads, the player will win 4/7 dollars if he decides to stop here.

The problem is then, of course, to decide if after N coin throws of which M are heads, to continue or to stop. Count Iblis (talk) 19:31, 6 October 2010 (UTC)

Well, the game is memoryless, so at any point the expected fraction of heads you should expect to obtain in the future is 1/2, regardless of your past performance. (This assumes that you know the coin is fair.) This seems to indicate to me that as soon as your fraction M/N at any point is greater than 1/2, you should stop. —Bkell (talk) 19:55, 6 October 2010 (UTC)

(ec) Is there an entry fee? Say 0.5 dollars? But whatever the entry fee, the flipper can set a threshold (say 75%) and carry on flipping until he achieves that percentage. If he fails in the first 100 throws, maybe by 1000 he'll have got there. Or by 1,000,000 flips. Or by 10^99 flips... IE keep going forever until your desire is achieved. The lower the threshold, the more likely it is to be achieved in finite time. -- SGBailey (talk) 20:00, 6 October 2010 (UTC)

I thought about that, but the law of large numbers implies that the fraction will almost surely converge to 1/2 as N goes to infinity, which means that, for any fixed threshold r > 1/2, there will almost surely be a point beyond which the fraction never exceeds r. So it's not clear to me that you can say, "You can always reach a given threshold if you flip long enough." I believe it is also true that if there is a maximum allowed number of flips, even if that maximum is enormous (but finite), then you should stop the first time your fraction rises above 1/2, because the expected fraction of heads you'd get in the future if you continue is 1/2, meaning that you expect your cumulative fraction to drop. —Bkell (talk) 20:22, 6 October 2010 (UTC)

It's true that you cannot say "You can always reach a given threshold", but it's also not true that the best you can expect is 1/2. And I don't think you can say that the analysis would be as you specify if the maximum number of flips is large but finite. The analysis is more complicated than that. For the original case, the strong law of large numbers implies that, if your current position is M/N, then the distribution at time N + P is normal with mean:

${\frac {M+{\tfrac {1}{2}}P}{N+P}}$

and standard deviation

${\frac {\sqrt {{\tfrac {1}{12}}P}}{N+P}}$

It follows then that, if M is sufficiently close, but larger than N/2, then the strategy of waiting until time P, and then continuing if the new value is less than 1/2, would produce a better result. — Arthur Rubin (talk) 20:45, 6 October 2010 (UTC)

[ec] Let's denote by $f(m,n)$ the expected gain if the player plays optimally and has already made n throws of which m are heads. Then we have $f(m,n)=\max \left({\tfrac {m}{n}},{\tfrac {1}{2}}(f(m,n+1)+f(m+1,n+1))\right)\;\!$. It can also be seen that

1. If n is large and m is significantly larger than $n/2$ (by some multiple of ${\sqrt {n}}$, I think) then $f(m,n)=m/n$ exactly (realized by stopping).
2. If n is large and m is approximately or less than $n/2$, then $f(m,n)\approx 1/2$.
3. If n is small, $f(m,n)$ can be significantly more than half. If we limit the number of tosses to 1000, then $f(0,1)=0.582395...$ and $f(11,20)=0.558973...$ (so at (11,20) you should keep playing). Without the limit, f is slightly higher.

How to find an exact value for f is something I'll keep working on. -- Meni Rosenfeld (talk) 20:46, 6 October 2010 (UTC)

For whomever it may interest, here are the minimal values of m for which you'll want to stop, assuming a limit of 1000 throws (the real values should only be slightly off, if at all), for $n=1,2,3,\ldots ,50$:

1, 2, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 12, 12, 13, 13, 14, 14, 15,
15, 16, 16, 17, 17, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28

-- Meni Rosenfeld (talk) 20:58, 6 October 2010 (UTC)

The continuous approximation may be easier to solve: Given a Wiener process W(t) with instantaneous variance 1/12, try to solve the stopping problem with payoff W(t)/t. (Or, it might not be easier or relevant.) — Arthur Rubin (talk) 21:07, 6 October 2010 (UTC)

That's indeed the plan. I do believe it's easier and relevant. This reminds me of the nerd sniping problem - at first I thought "well, at least I can get an approximation by starting with the obvious boundary conditions and solving inwards". Then it turned out the boundary conditions were not obvious at all, and before I knew it I was deep in some very vicious differential equations. -- Meni Rosenfeld (talk) 21:16, 6 October 2010 (UTC)

It's a simple Parabolic partial differential equation (aka, 1-dimensional heat equation) with a free boundary condition (for which we don't have an article, although we have a stub for yet another free boundary condition of which I had never heard.) It may be similar to the adaptation of the Black–Scholes model to American options, but much less complicated. — Arthur Rubin (talk) 21:51, 6 October 2010 (UTC)

Some formalization. Consider Bernoulli random variables (with p=1/2)$X_{1},X_{2}\ldots$. Denote $S_{n}=\sum _{i=1}^{n}X_{i}$. Then $Y_{n}={\frac {S_{n}}{n}}$ is exactly your pay off after n throws. Centralize it with $Z_{n}=S_{n}/n-1/2$ (which incidentally would be your profit if you paid 1/2 to participate in the game) to get

$E(Z_{n+1}|Z_{n})=Z_{n}\left(1-{\frac {1}{n+1}}\right)$, $n\geq 1$

.So understandably, you should continue flipping the coin as long as $Y_{n}<1/2$ per Bkell above. And intuitively, Bkell's suggestion above also makes sense because on average the next throw will decrease your pay off if $Y_{n}>1/2$ However the issue is more complicated because if we look at

$P(\sup _{k>n}Y_{k}>Y_{n}),$

which is clearly more than 1/2. And what's about $E(\sup _{k>n}Y_{k})$? (Igny (talk) 23:19, 6 October 2010 (UTC))

Set theory notation

If you don't understand the first part, don't worry; just stick with it. The first part is just a motivation. The last part should be simple and I'm annoyed that I can't answer it for myself. Any way, here goes...

The set of functions in n variables with critical point 0 and whose hessian matrix has corank k ≤ n has codimension 1⁄2·k·(k+1) in the space of function germs with critical value 0 at 0. Thus, the set of functions of corank 2 has codimension 3, the set of functions of corank 3 has codimension 6, and those of corank 4 have codimension 10. That means that in generic one and two parameter families of functions we have only singularities of corank 1. If the number of parameters is less than six we have singularities of corank at most 2. If the number of parameters is less than 10 we have singularities of corank at most 3. If the number of parameters is less than 15 we have singularities of corank at most 4. In general, if the number of parameters is less than 1⁄2·k·(k+1) then we have singularities of corank at most k. I want to express this relationship the other way around. So, if the number of parameters is less than p then we have singularities of corank at most k(p). Well, we can invert p < 1⁄2·k·(k+1). We consider 2k² + k – 2p = 0, and so

$k=-{\frac {1}{2}}\pm {\frac {1}{2}}{\sqrt {1+8p}}.$

The positive sign of the radical is the correct one since k ≥ 0. Since k should be a whole number we use the floor function:

$k(p)=\left\lfloor -{\frac {1}{2}}+{\frac {1}{2}}{\sqrt {1+8p}}\right\rfloor .$

Evaluating the the sequence { k(p) : p ≥ 0} give a sequence where the first two terms are equal to 1, the next three terms are equal to 2, the next four terms are equal to 3, the next five terms are equal to 4, etc. In other words:

$\{k(p):p\geq 1\}=\{1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,\ldots \}\ .$

After all that, here's my question:

• Can anyone come up with a set notation definition that doesn't use radicals or the floor function?

— Fly by Night (talk) 21:26, 6 October 2010 (UTC)

Minimal domain hash function

First, I want to define what I mean by hash to avoid confusion... Given unique values I₀, I₁, ... I_n over the domain R_I, a hash function H(I) will return a unique values J₀, J₁, ... J_n over the domain R_J. Often, to ensure uniqueness, R_J is much larger than R_I. What I want to learn about is how to solve the following problem. Given a set of unique values I, create a hash function that ensures unique values in J with a minimal domain R_J. The catch is that the values of I given do not completely fill the domain. For example, you can receive A, H, U, and T over the domain A through Z. I am not interested in sequential hash functions, such as the trivial "mod by the size of the domain" hash. The order of I should not be the same as the order of J - that is the entire point of the problem being solved. This function should randomize the order of the original values and replace the actual values with new values. I assume this problem has both a common name and a simple solution, but I haven't been able to find it. -- kainaw™ 23:34, 6 October 2010 (UTC)

See minimal perfect hashing. 72.229.127.238 (talk) 05:48, 7 October 2010 (UTC)

Complete theory with a finite number of countable models

I'm teaching an intro Model Theory course, and I'm getting to the number of countable models (Vaught's Conjecture, Morley's Theorem). I'd like to give an example of complete theories with 3, 4, 5, ... countable models. I know Ehrenfeucht's standard example, of course. Unfortunately, I wasn't really thinking ahead and put the 3 model version of it on the final, so I can't use that. I'm aware of a fair number of results suggesting that all examples are fundamentally the same as Ehrenfeucht's, but I just need it to be superficially different. Preferably hiding the linear order, for example. —Preceding unsigned comment added by 130.195.5.7 (talk) 23:53, 6 October 2010 (UTC)

October 7

More general form (and an image) for sine's continued fraction.

Hi.

I'd like to add a more general notation for the "continued fraction" section of the Sine article.

There are other notation styles listed here: Generalized continued fraction#Notation.

Any suggestions for an image/diagram for this section would be appreciated too.

Thanks —Pengo