L'Hôpital's rule only requires that f'/g' have a limit, not that f'/g' have any convenient type of form. Recursive use of l'Hôpital's rule is a perfectly valid way to show that f'/g' has a limit.
That said, you only have to differentiate twice to get rid of the indeterminacy, since f''(0) is nonzero. You will obtain L=(-1/2)0/f''(0)=0, and hence this is not a counterexample.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
For a function f to be analytic at point x0, it has to be infinitely differentiable at x0, and its taylor series at x0 must converge to the function value f(x0). A function is smooth as long as a small change in x causes a small change in f (see this definition). So being analytic is a much stronger property than smoothness - all analytic functions are smooth, but not the other way around (abs(x) is smooth but not analytic at x=0 since the derivative does not exist at this point).
Maybe someone can correct me if I missed something.
That said, you only have to differentiate twice to get rid of the indeterminacy, since f''(0) is nonzero. You will obtain L=(-1/2)0/f''(0)=0, and hence this is not a counterexample.
ROFL I fail!!!! *facepalms at himself*
That's right, I was careless at that step...
To make it even more embarassing, I ended up actually proving it when I tried to find another counterexample o_O, I think my intuition is not very good. (Or also my math, if the following turns out to be wrong).
If for some n, f(n)(c)!=0, that means limx->c f(x)/(x-c)n != 0, where n is the smallest order non-zero derivative.
I prove that with l'Hopital's rule, it can be made more rigorous with induction, but well, if you keep differentiating the numerator and the denominator, you get:
limx->c f'(x)/n(x-c)n-1 , limx->c f''(x)/n(n-1)(x-c)n-2, ... , limx->c f(n)(x)/n!
Now, if n is indeed the smallest non-zero derivative, all fractions will have a 0/0 indeterminacy, except the last one, which will be different from zero because fn(c)!=0, this is enough to say that the original limit is not zero. Also, assuming that f doesn't get negative for a neighborhood of c, its smallest order non-zero derivative can never be an odd number, since in this case c wouldn't be a local minimum. So, the exponentiation of the two functions can be written without loss of generality as:
(f(x)/(x-c)n)g(x) * ((x-c)n)g(x)
The base in the first factor goes to something other than 0 when x->c and g(x)->0, so that factor has limit 1, and the other one is equivalent to exp(n g(x) ln (x-c)).
For the exponent: n g(x) ln x = n (g(x)/(x-c)) * (x-c)ln (x-c)
Since g(c)=0, the limit of g(x)/(x-c) is g'(c), which exists, since g is smooth. An application of l'Hopital's rule in (x-c)ln(x-c) will show that it goes to 0, so the limit of the exponent is 0 and thus the limit is exp(0)=1.
I'm surprised by this, since it's much weaker than the conditions I read (f and g analytic), in fact that only requires f to be smooth and have derivatives that don't vanish and g to be differentiable at x=c, leaving me to wonder why they put those much stronger conditions there, perhaps because the most common counterexample to that is f(x)= exp(-1/x^2) and g(x)=x^2, a non-analytic function.
If what I wrote is right, that's an interesting problem, it's been a while since I got beat up by a limit, it took me a long time to figure out the division by (x-c)^n, perhaps I'll put it in a test some time.
abs(x) is smooth but not analytic at x=0 since the derivative does not exist at this point
How can it be smooth at x=0 since there's a clear discontinuity in the derivative of the function at that point? (The derivative is -1 when x<0 and 1 when x>=0, hence by definition it's not a smooth function, AFAIK.)
For a function f to be analytic at point x0, it has to be infinitely differentiable at x0, and its taylor series at x0 must converge to the function value f(x0). A function is smooth as long as a small change in x causes a small change in f (see this definition). So being analytic is a much stronger property than smoothness - all analytic functions are smooth, but not the other way around (abs(x) is smooth but not analytic at x=0 since the derivative does not exist at this point).
Maybe someone can correct me if I missed something.
"Smooth" is not a precise term. It can mean various things depending on the context, in topology and differential geometry it's usually taken as class C1 (has a derivative everywhere in the domain and this derivative is continuous) and in real analysis as class C-infinity (admits derivatives of any order and all are continuous in the entire domain).
Not a correction, but an addition, whenever we talk about the Taylor series of a function around a point x0, we also have to mention its radius of convergence, or the interval where the series converges. When a function is analytic at x0, its Taylor series around x0 has a positive radius of convergence (for some non degenerate interval, it converges) and for every x in the interval, the value it converges to must equal f(x).
To be analytic, the function has to be C-infinity, but the converse is not true, the most famous smooth non-analytic function is f(x)=e^(-1/x^2), its Taylor series at x=0 is the null function, so despite it converging it does not converge to f(x). The function I presented in my incorrect attempt is also not analytic at x=0, its Taylor series will diverge for x!=0, having a radius of convergence = 0. An adaptation of it can be made to make a function that's smooth and non-analytic in all its domain.
However, smooth non-analytic functions are usually taken as monsters of real analysis and have little importance outside of the theoretical realm.
Warp wrote:
Randil wrote:
abs(x) is smooth but not analytic at x=0 since the derivative does not exist at this point
How can it be smooth at x=0 since there's a clear discontinuity in the derivative of the function at that point? (The derivative is -1 when x<0>=0, hence by definition it's not a smooth function, AFAIK.)
I think he may be using another definition of the term or confusing smooth with continuous. Anyway, |x| is indeed not smooth, but its derivative doesn't equal 1 at x=0, it doesn't exist.
I was reading http://tvtropes.org/pmwiki/pmwiki.php/Main/TriangRelations (instead of doing work), and started wondering how to count all those combinations of n people in a love relationship with each other.
From the setup these rules are obvious:
1) The relationship between n people is represented by a directional graph consisting of n nodes and which is connected (in other words you can reach any node from any other node by following one or more connections, either forward or backward). That is, no isolated groups.
2) Connections can be one-way or two-way (and count as two different situations).
3) All isomorphic graphs are considered equal, and thus counted only once. (For example, "A loves B, who loves C" is equal to "A loves C, who loves B". It's the same type of relationship, just with the labels changed.)
Is there a formula that tells how many different relationships (ie. different graphs according to the rules above) are possible with n people?
From the setup these rules are obvious:
1) The relationship between n people is represented by a directional graph consisting of n nodes and which is connected
2) Connections can be one-way or two-way
3) All isomorphic graphs are considered equal, and thus counted only once.
Is there a formula that tells how many different relationships (ie. different graphs according to the rules above) are possible with n people?
Assuming this is about number of non isomorphic weakly connected digraphs of n vertices, there is the following:
Number of connected digraphs with n nodes.
That page also gives formula, but it also involves another sequence (which has formula involving yet another sequence, and that one doesn't have simple formula listed, only way to calculate it using maple).
At least the three first values are what they should (too lazy to see if 199 is the correct amount of a graph with 4 nodes), so it's probably exactly that.
That page also gives formula, but it also involves another sequence (which has formula involving yet another sequence, and that one doesn't have simple formula listed, only way to calculate it using maple).
Seems to be a lot more complicated than I expected. (Or perhaps not, thinking about it.)
Logic problem taken from Terence Tao's blog:
There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).
[Added, Feb 15: for the purposes of this logic puzzle, "highly logical" means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.]
Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics (each of them can of course only see 999 of the 1000 tribespeople).
One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe.
One evening, he addresses the entire tribe to thank them for their hospitality.
However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, remarking “how unusual it is to see another blue-eyed person like myself in this region of the world”.
What effect, if anything, does this faux pas have on the tribe?
The interesting thing about this puzzle is that there are two quite plausible arguments here, which give opposing conclusions:
[Note: if you have not seen the puzzle before, I recommend thinking about it first before clicking ahead.]
Argument 1. The foreigner has no effect, because his comments do not tell the tribe anything that they do not already know (everyone in the tribe can already see that there are several blue-eyed people in their tribe). \diamond
Argument 2. 100 days after the address, all the blue eyed people commit suicide. This is proven as a special case of
Proposition. Suppose that the tribe had n blue-eyed people for some positive integer n. Then n days after the traveller’s address, all n blue-eyed people commit suicide.
Proof: We induct on n. When n=1, the single blue-eyed person realizes that the traveler is referring to him or her, and thus commits suicide on the next day. Now suppose inductively that n is larger than 1. Each blue-eyed person will reason as follows: “If I am not blue-eyed, then there will only be n-1 blue-eyed people on this island, and so they will all commit suicide n-1 days after the traveler’s address”. But when n-1 days pass, none of the blue-eyed people do so (because at that stage they have no evidence that they themselves are blue-eyed). After nobody commits suicide on the (n-1)^{st} day, each of the blue eyed people then realizes that they themselves must have blue eyes, and will then commit suicide on the n^{th} day.
Only one of these arguments is valid. The challenge is to say which one of them is, and to point out the mistake in the wrong one. You may get the idea soon enough if you read the blog's comments in the link :P
Joined: 8/6/2006
Posts: 784
Location: Connecticut, USA
There's been a statistics-related question that's been bugging me for a while; I've taken a few stats classes but I'm not sure I have the right knowledge to determine the following:
Say the probability of an event happening is x . If I perform y trials, what is the probability of that event not occurring at all?
e.g. The probability of event A is .99, if I perform 100 trials, what are the chances of that event not occurring once?
I recall beginning to read something about this a while ago, and seeing some sort of natural log component to the answer, but I can't find any information on it currently (it's a tough question to pose on google).
Incidentally, my curiosity stems from bad luck in getting rare drops in games. I would like to be able to say, "Gee, I've killed this enemy 128 times, and still haven't gotten my 1 / 64 drop, the chances of that are xxxxxx!" and totally nerd out.
Say the probability of an event happening is x . If I perform y trials, what is the probability of that event not occurring at all?
The probability that the event does not happen on each trial is 1 - x.
If the trials are independent, then the probability of even not happening in y trials is this to the power of y, i.e. (1-x)^y.
E.g. if x=0.01 (1% chance) and y=100 (100 attempts), this yields ~36.6%.
ElectroSpecter wrote:
Incidentally, my curiosity stems from bad luck in getting rare drops in games. I would like to be able to say, "Gee, I've killed this enemy 128 times, and still haven't gotten my 1 / 64 drop, the chances of that are xxxxxx!" and totally nerd out.
Watch out here. The above assumes trials are independent, which might very well not hold in practice.
Anyway, 128 independent tries at 1/64 chance has all trials fail (1-1/64)^128=~13,3% of the time (if the tries are dependent, the chance of failure can be less or greater).
If the trials are independent, then the probability of even not happening in y trials is this to the power of y, i.e. (1-x)^y.
E.g. if x=0.01 (1% chance) and y=100 (100 attempts), this yields ~36.6%.
You might want to revise that result.
(Hint: The correct number is something like 10-198%.)
I would like to be able to say, "Gee, I've killed this enemy 128 times, and still haven't gotten my 1 / 64 drop, the chances of that are xxxxxx!" and totally nerd out.
FYI, you don't get to "nerd out" unless you were able to do the math yourself. Just saying. :P
Warp wrote:
You might want to revise that result.
(Hint: The correct number is something like 10-198%.)
No, that's the number of "getting the 1% drop every single time!". For the chance of getting no drop in 100 attempts, 0.99^100 ~ 36% is correct.
Joined: 8/6/2006
Posts: 784
Location: Connecticut, USA
Wow, I feel stupid. I should have known that (like I said, I've taken a couple stats classes). I think what threw me off is the article that I started to read a while ago. I guess I misinterpreted the point of it, and thought that what I wanted to know was a bit more complicated.
Suppose you have N marbles and you want to know the number of different possibilities of putting them in K vases. The vases and marbles are not labelled, so if K=2 and N=3, there are only 2 options: {2,1} and {3,0}. The options {1,2} and {0,3} are not considered to be different possibilities. {1,1,1} is not an option because K was only 2. If K were to be 3 (or higher), then {1,1,1} would be an option, so the number of possibilities would then be 3.
Find a function depending on K and N that gives the number of possibilities of putting N marbles in K vases.
Suppose you have N marbles and you want to know the number of different possibilities of putting them in K vases. The vases and marbles are not labelled, so if K=2 and N=3, there are only 2 options: {2,1} and {3,0}. The options {1,2} and {0,3} are not considered to be different possibilities. {1,1,1} is not an option because K was only 2. If K were to be 3 (or higher), then {1,1,1} would be an option, so the number of possibilities would then be 3.
Find a function depending on K and N that gives the number of possibilities of putting N marbles in K vases.
Suppose you have N marbles and you want to know the number of different possibilities of putting them in K vases. The vases and marbles are not labelled, so if K=2 and N=3, there are only 2 options: {2,1} and {3,0}. The options {1,2} and {0,3} are not considered to be different possibilities. {1,1,1} is not an option because K was only 2. If K were to be 3 (or higher), then {1,1,1} would be an option, so the number of possibilities would then be 3.
Find a function depending on K and N that gives the number of possibilities of putting N marbles in K vases.
This is a classical problem. You can represent N marbles with N stars using that trick and the K vases as K-1 bars. In your examples, these configurations correspond to {2,1} and {0,3} respectively:
**|*
|***
What's before the dash is in the first vase, what's after it is in the second. It should be easier to generalize to K vases. The interesting part is that each valid configuration corresponds to exactly one of the permutations and each permutation corresponds to one valid configuration, so you can count the configurations by counting those permutations.
In the general case, we have N identical stars and K-1 identical dashes and want to count the number of permutations. This is given by (N+K-1)!/N!(K-1)! .
Your formula results in 4. This is presumably:
|*** {0,3}
*|** {1,2}
**|* {2,1}
***| {3,0}
As I mentioned when I stated the problem, the answer should be 2. The vases are not labelled so {0,3} and {3,0} are the same possibility and only count once.
Ah, OK.
a_1 + a_2 + a_3 + ... + a_k = n, a_i>=0
We have to count the number of nondecreasing sequences a_i.
b_i = a_(i+1) - a_i
a_i = a_1 + b_1 + ... + b_(k-1)
Throwing this into the first equation, we get:
k a_1 + (k-1) b_1 + (k-2) b_2 + ... + b_(k-1) = n
We have to find the number of non-negative integer solutions to this equation, and we go into additive number theory, that I'm not familiar with, in the place where you got this problem there was any hint of what you should use to solve it?
EDIT: I think there's a generating function for this, if you get P(x) = (1 - x)(1 - x²)...(1 - x^k), and f(x) = 1/P(x), the answer should be f(n)(0)/n! if I recall correctly, but this looks hardly an acceptable answer.
EDIT 2:
The problem is equivalent to determining the number of non-negative integer solutions a_1, a_2, ..., a_k of:
a_1 + 2*a_2 + 3*a_3 + ... + k*a_k = n
We call the number of solutions f(n,k)
There are two possibilities for a_k, if a_k = 0, then we have to find the number of non-negative solutions of:
a_1 + 2*a_2 + 3*a_3 + ... + (k-1)*a_(k-1) = n, which is f(n,k-1).
if a_k>0, a_k>=1 and we have to find the number of non-negative solutions of:
a_1 + 2*a_2 + 3*a_3 + ... + k*(a_k-1) = n-k, which is f(n-k,k)
So, f(n,k) = f(n,k-1) + f(n-k,k), we just need to find the boundary conditions:
f(n,k) = 0, if n<0 or k<=0
f(0,1) = 1,
f(n,k) = f(n,k-1) + f(n-k,k), otherwise
That recurrence involves two variables and because of that it's nearly impossible to find a closed formula. When it depends on n-1 and k-1 you can play with the recurrence satisfied by binomials and get something, but at this case, it depends on n-k. I don't think an elementary closed formula exists.
Nah, I didn't get it as a problem. I stumbled into it and had trouble solving it. Looks like there was a good reason for that. Thanks for your effort though :)
I already managed to solve these problems, but they were interesting to solve, so I'll present them here:
1) I have a string of n bulbs. No two adjacent bulbs can be on. How many possible strings are there?
2) I have a string of n bulbs. Bulbs can be off, red or green. If a bulb is red, the bulbs adjacent can't be red. If a bulb is green, the bulbs adjacent can't be green. How many possible strings are there?
