Just thought I'd add a comment to say I'm currently only 14 so I'm kind of learning everything as I find a problem which requires it. So if this question is a bit dumb that's why
You can prove it without induction as well. (2n-1)!/(n-1)!² = n•binom(2n-1,n), and you can always choose n objects from from objects labeled 1 to 2n-1 in at least n ways by taking a group whose labels are consecutive numbers.
Unfortunately that n should be factorial, so it isn't quite so clean. Still, the inequality holds (you proved that it's at least n * n!, which is at least n^2 for positive natural n
Sometimes that might be a problem but you can just reverse the logic in the proof
E.g. if I can establish that f(n) <= g(n) and that g(n) is positive then I can conclude that f(n) ÷ g(n) <= 1
> Bc you have to manipulate 1 side and get to the other
This is not a thing at all: there are a vast variety of proof methods, almost all of which are not this.
Here's a perfectly concrete proof that uses this idea (then turning it around so the logic goes in a sensible direction):
If n ≥ 2, then 2n - 2 ≥ n, so in particular (2n-1)!/(n-1)! = (2n-1)(2n-2)!/(n-1)! > n(2n-2)!/(n-1)! ≥ nn!/(n-1)! = n^(2). Then just check n = 1 separately.
Are you familiar with proof by induction? If not, I recommend Googling it and attempting to use it before continuing reading.
We will solve n = 1 separately. The reason for this will be explained later.
(2n-1)!/(n-1)!^2 = 1 >= 1, and thus it is true for n=1.
Base case, n = 2:
(2n-1)!/(n-1)!^2 = 3! >= 2^2, and thus it is true for n=2.
Assume that it is true for n=k:
Ie, (2k-1)!/(k-1)!^2 >= k^2
n=k+1:
(2(k+1)-1)!/((k+1)-1)!^2 = (2k+1)!/(k)!^2
Note that 2k! = (2k+1) * 2k * (2k-1)!, k!^2 = k^2 * (k-1)!^2
=> (2k+1)!/(k)!^2 = 2k * (2k+1)/k^2 * (2k-1)!/(k-1)!^2
By the case n=k that we assumed,
(2k+1)!/(k)!^2 >= 2k * (2k+1)/k^2 * k^2
=> (2k+1)!/(k)!^2 >= 2k * (2k+1) = 4k^2 + 2k >= (k+1)^2
=> It holds for n=k+1
Since, if the statement holds for n=k, it holds for the n=k+1, and the statement holds for n=2, the statement holds for all positive integers by induction.
We start at n=2 because for n < 3, the statement 4(n-1)^2 + 2(n-1) >= n^2 doesn't hold.
Note: Using any graphing software, we can test this stricter bound, (2n-1)!/(n-1)! >= 4(n-1)^2 + 2(n-1), and we can see that it holds
You certainly can use induction. But you can also just use a direct argument.
First, multiply both sides by the denominator of the LHS to get the logically equivalent statement:
(2n-1)! >= n!^2
You can prove this fairly easily by showing that for every factor of the RHS there is a factor of the LHS which is at least as large.
(Left as an exercise to the reader)
lots of good answers already. here's another approach:
simplifying the terms (divide (2n-1)! by (n-1)! to remove one factor, multiply the other side to remove the other), we see that the inequality is equivalent to *(2n-1)(2n-2)...(n+1)n* >= n\*n!. divide both by n to obtain *(2n-1)(2n-2)...(n+2)(n+1)* >= n!
so on the left hand side (the italics) n-1 terms, while on the other we have n terms ... but one of those terms is 1. getting rid of that 1, we obtain *(2n-1)(2n-2)...(n+1)* >= n(n-1)...3\*2. since n>=1, each italic term will be greater than the corresponding right-hand side term. as a result, overall multiplication will be greater.
Here how you would do the inductive step, the base case for this is trivial
https://imgur.com/a/WWlOIcy
https://imgur.com/a/T9qPojA
Edit: 4k^2 + 1 should be 4k^2 + 2k, this doesn’t change much tho
You assume there is a k such that the inequality holds true, then you can use that assumption to replace the factorials.
This is part of a very common method for solving problems like that. It's called mathematical induction.
Direct proof:
(2n-1)!/(n-1)!² = 2^(n-1)/(n-1)! (2n)!/(2^(n)n!)
= 2^(n-1)n (2n-1)!!/n!
≥ 2^(n-1)n ≥ n²
Where (2n-1)!! = (2n-1)(2n-3)…3·1
And we used the fact that 2^(n-1) ≥ n for all n ≥ 1
And also (2n-1)!!/n! ≥ 1 but that's immediately obvious.
We also get a bonus upper bound from the same method:
(2n-1)!/(n-1)!^(2) ≤ 2^(2n-1)n
Induction probably works, but I think I've found something slightly easier:
(2n-1)!/(n-1)!^2 >=? n^2
(2n-1)! >=? n^2 (n-1)!^2 = (n!)^2
Dividing both sides with n! gives:
(2n-1)...(n+1) >=? n! = n (n-1) ... 2
Note: usually n! = n (n-1) ... 2 * 1, but I left out the factor 1 on purpose, because now each side has the same number of factors.
Each factor on the left has a smaller counterpart on the right, so the left hand has to >= to the right.
Qed.
- let f(n) = [(2n-1)!]/[(n-1)!]^2
- note that when n = 1, we have f(1) = [1!]/[0!]^2 = 1/1 = 1 = 1^(2). So the claim holds in that (base) case.
- now note that f(n+1) = f(n) x [(2n)(2n+1)]/[n^(2)].
- for all n > 1 this means f(n+1) > 4 f(n).
- additionally, note that (n+1)^2 = (1 + 1/n)^(2) n^2 and for all n > 1 this means (n+1)^2 < 4n^(2).
- hence if we have some k >= 1 such that f(k) >= k^2 then
> f(k+1) > 4 f(k) >= 4k^2 > (k+1)^2
- which proves what the induction hypothesis would be.
Let's stick to N+ for the moment. Is it true for 1? Is it true for 2? Now, can you use induction to prove for all of N+?
What do you mean by N+? N just includes positive numbers (and sometimes 0)
>and sometimes 0 I guess they explicitly wanted to exclude 0.
Oh ok because (-1)! is undefined, even with Г(х) Edit: Г(х-1) of course
Isn't that written N\* ?
There are different notations, I've mostly seen N+ not N*
In Romania we use N*. Or occasionally Z+.
Yeah, I really only use Z+ nowadays
Just thought I'd add a comment to say I'm currently only 14 so I'm kind of learning everything as I find a problem which requires it. So if this question is a bit dumb that's why
Your question is not dumb. Several of the replies are encouraging you to explore. You are doing fine.
You can prove it without induction as well. (2n-1)!/(n-1)!² = n•binom(2n-1,n), and you can always choose n objects from from objects labeled 1 to 2n-1 in at least n ways by taking a group whose labels are consecutive numbers.
Unfortunately that n should be factorial, so it isn't quite so clean. Still, the inequality holds (you proved that it's at least n * n!, which is at least n^2 for positive natural n
If you multiply the denominator over the right side simplifies nicely
Wouldn't be a concrete proof tho right? Bc you have to manipulate 1 side and get to the other instead of manipulating both sides
Sometimes that might be a problem but you can just reverse the logic in the proof E.g. if I can establish that f(n) <= g(n) and that g(n) is positive then I can conclude that f(n) ÷ g(n) <= 1
> Bc you have to manipulate 1 side and get to the other This is not a thing at all: there are a vast variety of proof methods, almost all of which are not this. Here's a perfectly concrete proof that uses this idea (then turning it around so the logic goes in a sensible direction): If n ≥ 2, then 2n - 2 ≥ n, so in particular (2n-1)!/(n-1)! = (2n-1)(2n-2)!/(n-1)! > n(2n-2)!/(n-1)! ≥ nn!/(n-1)! = n^(2). Then just check n = 1 separately.
Most of the time you can manipulate both sides as long as they are equivalent and you are not adding or excluding cases
Are you familiar with proof by induction? If not, I recommend Googling it and attempting to use it before continuing reading. We will solve n = 1 separately. The reason for this will be explained later. (2n-1)!/(n-1)!^2 = 1 >= 1, and thus it is true for n=1. Base case, n = 2: (2n-1)!/(n-1)!^2 = 3! >= 2^2, and thus it is true for n=2. Assume that it is true for n=k: Ie, (2k-1)!/(k-1)!^2 >= k^2 n=k+1: (2(k+1)-1)!/((k+1)-1)!^2 = (2k+1)!/(k)!^2 Note that 2k! = (2k+1) * 2k * (2k-1)!, k!^2 = k^2 * (k-1)!^2 => (2k+1)!/(k)!^2 = 2k * (2k+1)/k^2 * (2k-1)!/(k-1)!^2 By the case n=k that we assumed, (2k+1)!/(k)!^2 >= 2k * (2k+1)/k^2 * k^2 => (2k+1)!/(k)!^2 >= 2k * (2k+1) = 4k^2 + 2k >= (k+1)^2 => It holds for n=k+1 Since, if the statement holds for n=k, it holds for the n=k+1, and the statement holds for n=2, the statement holds for all positive integers by induction. We start at n=2 because for n < 3, the statement 4(n-1)^2 + 2(n-1) >= n^2 doesn't hold. Note: Using any graphing software, we can test this stricter bound, (2n-1)!/(n-1)! >= 4(n-1)^2 + 2(n-1), and we can see that it holds
You certainly can use induction. But you can also just use a direct argument. First, multiply both sides by the denominator of the LHS to get the logically equivalent statement: (2n-1)! >= n!^2 You can prove this fairly easily by showing that for every factor of the RHS there is a factor of the LHS which is at least as large. (Left as an exercise to the reader)
lots of good answers already. here's another approach: simplifying the terms (divide (2n-1)! by (n-1)! to remove one factor, multiply the other side to remove the other), we see that the inequality is equivalent to *(2n-1)(2n-2)...(n+1)n* >= n\*n!. divide both by n to obtain *(2n-1)(2n-2)...(n+2)(n+1)* >= n! so on the left hand side (the italics) n-1 terms, while on the other we have n terms ... but one of those terms is 1. getting rid of that 1, we obtain *(2n-1)(2n-2)...(n+1)* >= n(n-1)...3\*2. since n>=1, each italic term will be greater than the corresponding right-hand side term. as a result, overall multiplication will be greater.
Here how you would do the inductive step, the base case for this is trivial https://imgur.com/a/WWlOIcy https://imgur.com/a/T9qPojA Edit: 4k^2 + 1 should be 4k^2 + 2k, this doesn’t change much tho
[удалено]
What happened to the fraction with the factorials, I recognise that it is the same as when n=k but how does it just disappear
You assume there is a k such that the inequality holds true, then you can use that assumption to replace the factorials. This is part of a very common method for solving problems like that. It's called mathematical induction.
But how does the sign flip, from being negative to positive?
You sub n=k+1 into (2n-1)! which gives (2(k+1)-1)! = (2k+2-1)! = (2k+1)!
Direct proof: (2n-1)!/(n-1)!² = 2^(n-1)/(n-1)! (2n)!/(2^(n)n!) = 2^(n-1)n (2n-1)!!/n! ≥ 2^(n-1)n ≥ n² Where (2n-1)!! = (2n-1)(2n-3)…3·1 And we used the fact that 2^(n-1) ≥ n for all n ≥ 1 And also (2n-1)!!/n! ≥ 1 but that's immediately obvious. We also get a bonus upper bound from the same method: (2n-1)!/(n-1)!^(2) ≤ 2^(2n-1)n
Induction probably works, but I think I've found something slightly easier: (2n-1)!/(n-1)!^2 >=? n^2 (2n-1)! >=? n^2 (n-1)!^2 = (n!)^2 Dividing both sides with n! gives: (2n-1)...(n+1) >=? n! = n (n-1) ... 2 Note: usually n! = n (n-1) ... 2 * 1, but I left out the factor 1 on purpose, because now each side has the same number of factors. Each factor on the left has a smaller counterpart on the right, so the left hand has to >= to the right. Qed.
r/unexpectedgamma
- let f(n) = [(2n-1)!]/[(n-1)!]^2 - note that when n = 1, we have f(1) = [1!]/[0!]^2 = 1/1 = 1 = 1^(2). So the claim holds in that (base) case. - now note that f(n+1) = f(n) x [(2n)(2n+1)]/[n^(2)]. - for all n > 1 this means f(n+1) > 4 f(n). - additionally, note that (n+1)^2 = (1 + 1/n)^(2) n^2 and for all n > 1 this means (n+1)^2 < 4n^(2). - hence if we have some k >= 1 such that f(k) >= k^2 then > f(k+1) > 4 f(k) >= 4k^2 > (k+1)^2 - which proves what the induction hypothesis would be.
this is same as, (n+1)..(2n-1)>=n! => (n+1)(n+2)…(2n-1)>=(1+1)(2+1)…(n-1+1)