Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

i am learning maths so fast here in MSE, thank you guys so much for being here to help us!

so now, my next step towards proficiency: :).

i am trying to prove that $\binom{n}{k}\frac{1}{n^k}\leq\frac{1}{k!}$ for $n\geq1$ and for all $k\in\Bbb{N}$. My first problem is that i never tried to prove a statement with induction where i have two dependencies. here $n$ and $k$.

induction base: $n=1$ and $k=1$. $\binom{1}{1}\frac{1}{1^1}\leq\frac{1}{1!}$ which is okay.
inductive hypothesis: for $n\geq1$ and for all $$k\in\Bbb{N},~~\binom{n}{k}\frac{1}{n^k}\leq\frac{1}{k!}$$ 1)first induction step: $$n\rightarrow n+1~~ \text{and}~~ k,\binom{n+1}{k}\frac{1}{(n+1)^{k}}\leq\frac{1}{(k)!}$$ 2)second induction step: $n$ and $$k\rightarrow k+1,~~\binom{n}{k+1}\frac{1}{(n)^{k+1}}\leq\frac{1}{(k+1)!}$$

1)$$\binom{n+1}{k}\frac{1}{(n+1)^{k}}=\Bigg(\binom{n}{k}+\binom{n}{k-1}\Bigg)\frac{1}{(n+1)^{k}} =\\ \binom{n}{k}\frac{1}{(n+1)^{k}} + \binom{n}{k-1}\frac{1}{(n+1)^{k}} \leq \frac{1}{(k)!}$$

2) Help.

I am having hard time to prove further in calculations, can you pls show me further? is 1) right? i am not sure

share|improve this question
1  
For two-point induction, you first prove the basis case for $n=k=1$, and then you have two inductive steps, first proving that if the hypothesis holds for $n=x$ and $k=y$ then $\implies$ the hypothesis holds for $n=x+1$ and $k=y$ and then show that if the hypothesis holds for $k=x$ and $n=y$ then $\implies$ that it holds for $k=x+1$ and $n=y$. –  Shaktal Dec 23 '12 at 20:43
1  
I assume you only want yes or no. It is insufficient, $k$ and $n$ are independent. –  André Nicolas Dec 23 '12 at 20:44
1  
For a non-induction, combinatorial proof: ${n\choose k}k!$ is the number of ordered lists of length $k$ with entries taken from a set of size $n$ without repetition allowed, whereas $n^k$ is the number of ordered lists of length $k$ with entries taken from a set of size $n$ with repetition allowed. The lists in the former category are in the latter category but not necessarily vice-versa, which establishes the inequality by rewriting as so: ${n\choose k}k!\le n^k\iff {n\choose k}\frac{1}{n^k}\le k!$. –  anon Dec 24 '12 at 1:19
    
great @anon i forgot that, nice remembering und explanation! thanks a lot –  doniyor Dec 24 '12 at 6:47
add comment

2 Answers 2

up vote 7 down vote accepted

In general, for inductions involving two independent natural numbers (here, $n$ and $k$, with $n, k \ge 1$), the strategy is as follows:

  • You first prove the basis case for $n=k=1$, which you have done.

  • Then you state an inductive hypothesis that the property holds for $n = a$ and $k = b$.

  • Then you need two inductive steps, and for each you assume the inductive hypothesis to be true, i.e. you'll want to use the inductive hypothesis to

    • First, prove the hypothesis also holds for $n=a+1$ and $k = b$; and
    • Then, prove that the hypothesis also holds for $ n=a, k = b+1$.
share|improve this answer
    
Oh, okay, that is what i was looking for, great thanks alot –  doniyor Dec 23 '12 at 20:51
    
Good...you're on your way then! –  amWhy Dec 23 '12 at 20:52
    
can you pls check my edited question? –  doniyor Dec 23 '12 at 21:24
    
Yes, the statement immediately following each inductive step is what you want to prove: can you show more justification? –  amWhy Dec 23 '12 at 21:27
add comment

Note that $k! \dbinom{n}k = \dfrac{n!}{(n-k)!} = n(n-1)(n-2) \cdots (n-k+1)$. Hence, you want to show that $$n(n-1)(n-2) \cdots (n-k+1) \leq n^k$$ Can you now show this?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.