Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[silverspawn]

This is probably an easy problem, but what is

sum(k from 0 to n) [(k+1) * (k out of n)]

I figured it can be rewritten as sum (k from 0 to n (k out of n)) + sum (k from 1 to n (k out of n)) + ... + sum (k from n to n (k out of n)) but couldn't solve that either.

[navical]

What do you mean by "k out of n"? Is it "n choose k" i.e. n!/(k!(n-k)!)?

[silverspawn]

yes. (In german we say "n over k" because that's how the operator looks, but that's understood as n/k in english, so I used "k out of n" because that's what it counts.)

[faust]

Well, the sum over all (n choose k) is 2^n, I feel like that should be part of the solution.

Thus, you can rewrite to 2^n+2^n-(n choose 0)+2^n-(n choose 0)-(n choose 1)+... or in other words n*2^n-sum(k from 0 to n-1) (n-1-k)*(n choose k)

Also (n choose k)=(n-1 choose k-1)+(n-1 choose k)

Thus you can rewrite the above sum and should be able to progress in some inductive manner I believe.

[navical]

If you call the original sum S_n then using (n choose k) = (n-1 choose k-1) + (n-1 choose k) you can get a recurrence relation S_n = 2S_{n-1} + 2^{n-1}. This has closed form S_n = (n+2)*2^{n-1} which you can prove by induction.

[heron]

The given sum is the number of ways to color a group of n points with red, green, and blue such that at most one point is colored red (think of each term as selecting k points to color green, and then choosing either one of those k points or no point to be red, and coloring the rest blue).

The number of ways to color points in that fashion is 2^(n-1) * n + 2^n = 2^(n-1) * (n + 2) as navical computed.
The first term is the number of ways if there is a red point, and the second term is the number of ways if there is no red point.

[silverspawn]

Well, the sum over all (n choose k) is 2^n, I feel like that should be part of the solution.

Thus, you can rewrite to 2^n+2^n-(n choose 0)+2^n-(n choose 0)-(n choose 1)+... or in other words n*2^n-sum(k from 0 to n-1) (n-1-k)*(n choose k)

I did try that, but I didn't get any further than the above, because I didn't see how to handle the negative sums any better than the original sum.

The given sum is the number of ways to color a group of n points with red, green, and blue such that at most one point is colored red (think of each term as selecting k points to color green, and then choosing either one of those k points or no point to be red, and coloring the rest blue).

The number of ways to color points in that fashion is 2^(n-1) * n + 2^n = 2^(n-1) * (n + 2) as navical computed.
The first term is the number of ways if there is a red point, and the second term is the number of ways if there is no red point.

That is a really smart and intuitive explanation. Thanks.

It took me a few minutes to figure out how you get from that to the formula but I think I got it. We do 2 cases separately: there is a red point, then first choose that (n) then have 2 choices for any other point (* 2^(n-1)) or there is no red point, then just have 2 choices for each point (+ 2^n). Those cases are disjoint and exhaustive.

[sudgy]

Here's another one:

Say you have a set S of sets, where each subset has size N.  What is the maximum size of S for a given N such that for all pairs of sets in S, they share exactly one element?  My brother and I have figured out that the upper bound is N * (N - 1) + 1, and have verified that that is the case for N = 1, 2, and 3, but haven't found a way to show that that is the answer.

EDIT: Read below, this isn't quite perfect.

[Watno]

I think you missed some restriction in the question, because you can get an arbitrary size for S when N> 1  (by having each s \in S consist of a common element x_0 and further elements x^s_1, ..., x^s_N, where all the x^M_i are different).

[sudgy]

I think you missed some restriction in the question, because you can get an arbitrary size for S when N> 1  (by having each s \in S consist of a common element x_0 and further elements x^s_1, ..., x^s_N, where all the x^M_i are different).

Oh crap, you're right.  Each element needs to be in the same number of sets.

EDIT: Now that I think of it, this might not work either.  I feel like saying that each element needs to be in more than one set could work too, but I'm not sure if that stops the infinite answer.

[silverspawn]

which theorem (I'm sure it exists but I can't find it) states that for a general triangle split like this



it holds that c^2 = p*(p+q)?

[Watno]

I think that statement is false (consider the case where q=0).

In the case of a right triangle, it's an easy consequence of the pythagorean theorem and https://en.wikipedia.org/wiki/Geometric_mean_theorem (Höhensatz in German)

[silverspawn]

aw. I needed it to prove that the triangle is a right triangle and I remembered it from somewhere. well in that case that does not work. thanks.

[heron]

See also https://en.wikipedia.org/wiki/Stewart%27s_theorem .

[silverspawn]

Here's something I've been thinking about again recently

So, a while ago I tried to prove that the derivative of sin is cos using the limit calculation, that's lim h->0 [sin(x + h) - sin(x)] / h. After finishing it, I realized that I used the rule of L'hopital, so I used the fact that sin' = cos in order to prove that sin' = cos. And ofc logically speaking, sin' = cos => sin' = cos is a tautology, so it doesn't prove anything. But then I realized that it's actually still pretty strong evidence – certainly it would be strong rational evidence if you didn't know what the derivative of sin was – because if you postulate an incorrect derivative, the same calculation will most likely get you a contradiction. For example, if you postulate that sin(x)' cos(x)' = x, then what you prove is that sin'(x) = cos'(x) = x => sin(x) = 0, which is a contradiction, so it does give you a valid proof that sin(x)' or cos(x)' does not equal x.

This made me think that perhaps the correct result is the only result that would not yield a contradiction in this way. If that were true and you could somehow prove it to be true, then the tautological proof of sin' = cos would actually become a legit proof. It turns out that's not true, though, because I found two counterexamples: sin' = cos' = 0 and sin' = sin, cos' = cos both return tautologies rather than contradictions. this keeps being true if you also plug them into the limit calculation for cos(x). But I still suspect that the class of contradictions is quite small. maybe that's wrong.

It also made me think about whether this is a formally stateable question. You may not be able to ask "is there another function f such that if sin(x)' = f(x), you get a stable result doing the limit calculation with l'hopital", because if sin(x)' = f(x) for f(x) ≠ cos(x), you would have a contradiction and then everything follows, so it probably would be possible to do the calculation and conclude that sin(x)' = x => sin(x)' = x. This is the general problem of reasoning about logical uncertainty. But at the same time, it is a question that's pretty easy to understand informally. Maybe you could formulate it if you restricted the operations that are allowed, but that sounds weird.

[ConMan]

Not quite the same thing, but in one applied maths course I took the lecturer solved a problem, but at one step he pointed out that there are a bunch of conditions you're meant to check before you do it, and said "We can leave that to the pure mathematicians, we'll just get an answer and check that it works". And he did - once he reached an answer, he proved it was a solution to the original problem, and never bothered to confirm that the process he used to reach it was valid.

[infangthief]

I think what you're saying here is addressed by the concept of logical completeness. I'm a bit rusty on this, but here's what I recall:

A set of axioms may be complete or incomplete. Now consider throwing in a new axiom (say sin' = cos).

If the original set of axioms is complete, then the new axiom will either cause a contradiction, or the new axiom will turn out to be derivable from the other axioms.

If the original set of axioms is incomplete, then it would be possible for the new axiom to be unprovable and yet not cause a contradiction.

So what you're effectively asking is: are my axioms for limit calculation, trig functions, derivatives etc complete?
If they are complete, then any result will either be correct or can be used to generate a contradiction.

[faust]

Then of course, for the question of completeness, we need to consider Gödel's incompleteness theorem, which states that any consistent system with arithmetic cannot be complete. The axioms of limit calculation probably need to include arithmetic rules, so your system will be incomplete; thus, it is guaranteed that there are other axioms you could add (though of course it is unclear that any of them will be of the form sin' = f).

[pacovf]

I mean, if we are getting to that point, the question is, how do you define “sin(x)”?

[fisherman]

This made me think that perhaps the correct result is the only result that would not yield a contradiction in this way. If that were true and you could somehow prove it to be true, then the tautological proof of sin' = cos would actually become a legit proof.

This definitely cannot work without an independent argument showing that sin is differentiable.

For comparison, you can often argue that if a given sequence approaches a limit, then the limit has a certain value. In some cases, this will in fact be the correct limit, while in others the limit will not actually exist.

[theorel]

Here's something I've been thinking about again recently

So, a while ago I tried to prove that the derivative of sin is cos using the limit calculation, that's lim h->0 [sin(x + h) - sin(x)] / h. After finishing it, I realized that I used the rule of L'hopital, so I used the fact that sin' = cos in order to prove that sin' = cos. And ofc logically speaking, sin' = cos => sin' = cos is a tautology, so it doesn't prove anything. But then I realized that it's actually still pretty strong evidence – certainly it would be strong rational evidence if you didn't know what the derivative of sin was – because if you postulate an incorrect derivative, the same calculation will most likely get you a contradiction. For example, if you postulate that sin(x)' cos(x)' = x, then what you prove is that sin'(x) = cos'(x) = x => sin(x) = 0, which is a contradiction, so it does give you a valid proof that sin(x)' or cos(x)' does not equal x.

The other replies are good for the general question, but this specific question seems to have some interesting points in it.
First: note that applying l'Hopital to the general derivative rule produces a tautology:
lim h->0 f(x+h)-f(x)/h=lim h->0 f'(x+h)/1=f'(x).

If you restrict yourself to using the derivative of sin, then you'll get the tautology.  The reason your problem gets wonky is because you're involving the derivative of cos as well, because of the other steps involved in finding the actual solution.
Trying to solve the limit, I assume you used the addition rule for sin, and got to:
sin'(x) = lim h->0 (sin(x)*(cos(h)-1)/h)+ (cos(x)*(sin(h)/h))
Now what's interesting here is that the parts of this equation involving the limit are in fact derivatives at 0.  i.e. lim h->0 (cos(h)-1)/h=cos'(0) and lim h->0 sin(h)/h=sin'(0).
So, applying l'Hopital here is no longer a tautology, it's in fact not changing the equation at all.  So, we have an equation that tells us a relationship between sin'(x) and sin'(0) and cos'(0).  To simplify the form of the relationship let's suppose sin'(x)=f(x) and cos'(x)=g(x) we get:

f(x)=g(0)*sin(x)+f(0)*cos(x).

Now, if we evaluate this at 0 we see that f(0)=g(0)*0+f(0)*1=f(0).  So we can choose any values for f(0) and g(0) and it's valid.  So we get the full set of all solutions:
f(x)=C*sin(x)+D*cos(x).
Note that g(x) does not depend at all on f(x), so it can be whatever you want as long as you choose it first, rather than trying to arbitrarily choose both at the same time.

So, in the end it's funny because using l'Hopital on the derivative rule produces a tautology, but using it on this modified form does not produce a tautology, but actually just expresses what's already true.  The "tautology" element comes from the f(0) evaluation above, but the produced equation is actually a pretty tight constraint on the form of sin'(x).

[gamesou]

A quick math riddle involving fruits

[silverspawn]

Disclaimer: the riddle is very hard and the smallest correct numbers have 20+ digits. Far fewer than 5% of all people could solve this.

[Iridium]

How would you even start solving it? I haven't graduated high school yet, but I know at least up through Calc II, so I figured I would be qualified to post in this thread.

But still, I have no idea how to even start.

[ThetaSigma12]

Disclaimer: the riddle is very hard and the smallest correct numbers have 20+ digits. Far fewer than 5% of all people could solve this.

I took a crack at it. I got (relatively) pretty close with 7, 1, and 1, to 3 and 3/4. Made the numbers bigger and with 23, 3, and 3 I got roughly 4.064, so I assumed you would just keep on using a similar method until it worked. Didn't seem worth taking it to oblivion, and I'm glad I didn't.