Proving Inequality: n Choose k <= 1/k!

In summary: As n > 0 you can instead try proving the equivalent statement:\binom n k \le \frac {n^k}{k!}##n! < n^n ##So what inequality might hold for the largest k terms of n! ?Thanks for the replies.
  • #1
neemer
22
0

Homework Statement

mathshity.JPG


its the second one.
let n∈ℕ \ 0 and k∈ℕ show that
(n choose k) 1/n^k <= 1/k!

Homework Equations



axioms of ordered fields?

The Attempt at a Solution



[/B]i have been working on this all afternoon. I know 0<k<n since its a requirement for (n choose k). I've tried induction, base case works but cannot figure out how to do inductive step. I don't really think induction is the correct method. I've tried cases, n=k is easy to prove but n>k i cannot figure out. Any help getting me started in the right direction would be appreciated.
 
Physics news on Phys.org
  • #2
As n > 0 you can instead try proving the equivalent statement:

[tex]\binom n k \le \frac {n^k}{k!}[/tex]
 
  • #3
##n! < n^n ##
So what inequality might hold for the largest k terms of n! ?
 
  • #4
Thanks for the replies.

I tried playing around with these for an hour this morning. When trying to prove that equivalent statement, Its obvious that its true but I still don't know how to "prove" it. Leaves me in the same situation as before just allows me to cancel a factor of 1/k! from either side of the inequality.

RUber, that inequality holds for all n>=2 i believe. Since k has to be less than n though the only way I could write k in terms of n is n-1 and at this point i am struggling again on what to do next.

Right now I'm thinking cases is the best way to try and prove this since its easy to prove the inequality for n=k. I just need to prove that it holds for n>k and then I would be done.
 
  • #5
I don't think you need induction, this is a straightforward relation.
##\left( \begin{array}{c} n\\k \end{array} \right) \frac{1}{n^k} \leq \frac{1}{k!} ##
Is saying:
##\frac{n!}{(n-k)!(k)!}\frac{1}{n^k} \leq \frac{1}{k!} ##
Which is equivalent to (for k >0)
##\frac{\left( \prod_{i = n-k+1}^n i \right) }{(k)!}\frac{1}{n^k} \leq \frac{1}{k!} ##
So as you said by cancelling out the ##\frac{1}{k!} ## the relation you need to prove is :
##\frac{\left( \prod_{i = n-k+1}^n i \right) }{n^k} \leq 1##
And for k= 0 :
##\frac{n!}{(n-k)!(k)!}\frac{1}{n^k} =1 \leq \frac{1}{k!} =1 ##
 
  • #6
ok I'm able to understand most of this. I am a little confused how you changed n!/(n-k)! into that product but i can see that it makes sense. Isn't k=0 just one case though? Wouldn't i still need to prove somehow that the inequality holds for k>0 but still k<n?
 
  • #7
## \frac{5!}{(5-2)!}= \frac{5*4*3*2*1}{3*2*1}=\prod_{i=5-2+1}^5 i =\prod_{i=4}^5 i=4*5.##
The first relation I wrote above (with the product notation) is for any k not equal to zero, then for k=0, the relation is just 1=1.
I find it odd that it seems your definition of natural numbers includes zero. That is not what I am used to. In any case, it just adds one case to the proof.
 
  • #8
Ok thanks I am pretty sure I got it now.
 
  • #9
neemer said:

Homework Statement

View attachment 74442

its the second one.
let n∈ℕ \ 0 and k∈ℕ show that
(n choose k) 1/n^k <= 1/k!

Homework Equations



axioms of ordered fields?

The Attempt at a Solution


[/B]
i have been working on this all afternoon. I know 0<k<n since its a requirement for (n choose k). I've tried induction, base case works but cannot figure out how to do inductive step. I don't really think induction is the correct method. I've tried cases, n=k is easy to prove but n>k i cannot figure out. Any help getting me started in the right direction would be appreciated.

If you insist on posting images (which is discouraged in PF) you should at least attempt to post them correctly--not sideways like you did. If you want help, don't make it difficult for us to see what you are doing.
 

1. What is the significance of proving n Choose k <= 1/k!?

Proving n Choose k <= 1/k! is important because it is a fundamental inequality in combinatorics and probability theory. It has many applications in areas such as statistics, computer science, and economics. Additionally, understanding this inequality can help in solving more complex problems involving combinations and permutations.

2. What is n Choose k?

n Choose k is a mathematical expression that represents the number of ways to choose k objects from a set of n objects. It is also known as the binomial coefficient and is denoted as "n choose k" or "nCk". It is calculated using the formula n! / (k! * (n-k)!).

3. How do you prove n Choose k <= 1/k!?

One way to prove this inequality is by using mathematical induction. This involves proving the base case (n=1) and then assuming the inequality holds for n=k and proving it for n=k+1. Another approach is to use combinatorial arguments, where you can show that the left side of the inequality represents the number of combinations of k objects from a set of n objects, and the right side represents the number of distinct permutations of k objects. Therefore, the inequality holds true.

4. What are some real-world applications of this inequality?

This inequality has various real-world applications, such as in statistics to calculate probabilities of events, in computer science to analyze the complexity of algorithms, and in economics to model decision-making processes. For example, in economics, this inequality can be used to show that choosing a smaller number of options from a larger set can result in a higher probability of success.

5. Are there any exceptions to this inequality?

Yes, there are some exceptions to this inequality. One exception is when k=0, where the left side of the inequality becomes 1 and the right side becomes 0. Another exception is when k>n, where the left side becomes 0 and the right side is undefined. In these cases, the inequality does not hold true.

Similar threads

Replies
12
Views
813
  • Calculus and Beyond Homework Help
Replies
15
Views
975
  • Calculus and Beyond Homework Help
Replies
6
Views
398
  • Calculus and Beyond Homework Help
Replies
9
Views
846
  • Calculus and Beyond Homework Help
Replies
6
Views
965
  • Calculus and Beyond Homework Help
Replies
4
Views
969
  • Calculus and Beyond Homework Help
Replies
1
Views
546
  • Calculus and Beyond Homework Help
Replies
1
Views
440
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
482
Back
Top