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.

$${n \choose k} \le \left({en \over k}\right)^k$$

Could anyone give me a hint how to prove this by induction on $k$? (I can prove it without induction)

share|improve this question
    
Is $n$ taken to be some fixed natural number? –  amWhy Feb 22 '13 at 17:03
    
Yes, the inequality should be true for every n. –  adamG Feb 22 '13 at 17:07

3 Answers 3

up vote 3 down vote accepted

Looking back at the answers that have been posted while I was working on this, I see that this is similar to AmWhy's argument. I will post it anyway since there is more detail (and color).

The base case is $$ \binom{n}{1}=n\le en=\left(\frac{en}{1}\right)^1\tag{1} $$ We avoid $k=0$ due to division by $0$.

Suppose the inequality is true for $\displaystyle\binom{n}{k}$, then $$ \begin{align} \binom{n+1}{k+1} &=\frac{n+1}{k+1}\binom{n}{k}\\ &\color{#C00000}{\le}\frac{n+1}{k+1}\color{#C00000}{\left(\frac{en}{k}\right)^k}\\ &=\frac{n+1}{k+1}\left(\frac{k+1}{k}\right)^k\left(\frac{en}{k+1}\right)^k\\ &\color{#C00000}{\le}\frac{n+1}{k+1}\color{#C00000}{e}\left(\frac{en}{k+1}\right)^k\\ &\color{#C00000}{\le}\frac{n+1}{k+1}e\left(\frac{e\color{#C00000}{(n+1)}}{k+1}\right)^k\\ &=\left(\frac{e(n+1)}{k+1}\right)^{k+1}\tag{2} \end{align} $$ Using $(1)$ and $(2)$, we see that $$ \binom{n}{k}\le\left(\frac{en}{k}\right)^k\tag{3} $$ For $n\ge k\ge1$.

share|improve this answer
    
+1, nice details... –  amWhy Feb 22 '13 at 21:34
    
To me this is the only correct answer (so far), and the only one that uses any property of the number $e$ (other than $e>1$). –  Marc van Leeuwen Feb 22 '13 at 23:00
    
@MarcvanLeeuwen: in AmWhy's answer, right after the inductive hypothesis, $$ e\ge\left(\frac{k+1}{k}\right)^k $$ is used; it is just a bit more obscured. –  robjohn Feb 22 '13 at 23:43
    
Well you are very generous. In similar situation when grading exams I would have to conclude "absent" rather than "obscured". One criterion one can apply is whether an argument ever uses a necessary ingredient, which as I said would be "where does one use that $e$ denotes $2.71828\ldots$ rather than some other real number?" here. But of course this is not an exam. Anyway, a nice proof. –  Marc van Leeuwen Feb 23 '13 at 5:37
    
robjohn: I edited to make explicit what was a "bit more obscured" in my ealier post, the obscurity referenced by @MarcvanLeeuwen. If you think that in editing, my answer resembles yours too closely, PLEASE, say the word, and I'll roll-back to the previous edit; I will have no objections to doing so. –  amWhy Feb 23 '13 at 16:42

General approach for proof by induction on $k$, for a given $n$:

$${n \choose k} \le \left({en \over k}\right)^k\tag{1}$$

First, we establish the base case $P(1)$: let $k = 1$ and show that the inequality holds.

Then we assume the inductive hypothesis, that is, assume the truth of $P(k)$, as given in $(1)$.

Then, using the inductive hypothesis, you test to see whether $$P(k+1) = {n \choose k+1} \le \left({en \over k+1}\right)^{k+1}$$

The challenging part is the last: use what you know (having proved it without induction) to write $P(k+1)$ in terms of the assumed inductive hypothesis. Then it's simply manipulating to exhibit the final form of the inequality you are seeking to establish.


Update: You're on your way, and almost there, with your inductive step. Recall, as robjohn notes below your post, you want to prove $$\binom{n}{k+1} \leq \left(\frac{en}{k+1}\right)^{k+1}.$$ Making a few tweaks with respect to your work, we have that:

$$ \begin{align} \\ \binom{n}{k+1} & = \frac{n}{k+1}\binom{n-1}{k} \\ \\ & \leq \frac{n}{k+1} \left(\frac{e(n-1)}{k}\right)^k \quad\quad\quad\tag{inductive hypothesis} \\ \\ & = \frac{n}{k+1}\left(\frac{k+1}{k}\right)^k \left(\frac{e(n - 1)}{k+1}\right)^k \\ \\ & \leq \frac{en}{k+1} \left(\frac{e(n-1)}{k+1}\right)^k \\ \\ & \leq \frac{en}{k+1} \left(\frac{en}{k+1}\right)^k \\ \\ & = \left(\frac{en}{k+1}\right)^{k+1} \\ \\ \end{align}$$

share|improve this answer
    
Thanks. You have probably misunderstood me slightly. I know what induction is, but I cannot find the key step to bring it to the right form. Is it straightforward from this point? –  adamG Feb 22 '13 at 17:19
    
OK got it, thanks! –  adamG Feb 22 '13 at 17:26
    
I notice that my argument is similar to yours (+1). If you wish, I will delete mine. I posted it since I have included some more detail. –  robjohn Feb 22 '13 at 21:28
    
I skipped some steps, @Marc, though it can easily be justified, as per robjohn. And given robjohn's post, to go in and "fill in the details" I left out NOW, at this point, would appear inappropriate. But you've raised a good point, and I would not submit as is, if I were assigned this problem. But let me be clear, my original intent was to point out an oversight of the OP, not to do the proof for him/her. –  amWhy Feb 22 '13 at 23:06
    
@Marc I went ahead to make explicit what I did not make explicit in my earlier post. If robjohn doesn't object to this edit, it will stand as is, else I'll roll back and attempt to describe in words what was too obscure in my earlier step following the inductive hypothesis. –  amWhy Feb 23 '13 at 16:44

Induction step:

$${n \choose k+1}={n\over k+1}{n-1 \choose k} \le {n\over k+1} \left({e(n-1) \over k}\right)^k \le {n\over k} \left({en \over k}\right)^k \le \left({en \over k}\right)^{k+1}$$

share|improve this answer
    
Nicely done.${}$ –  Brian M. Scott Feb 22 '13 at 17:59
3  
The estimate is supposed to be $$ \binom{n}{k+1}\le\left(\frac{en}{k+1}\right)^{k+1} $$ is it not? –  robjohn Feb 22 '13 at 19:20
    
You're right. Your solution is the correct one. –  adamG Feb 23 '13 at 12:05

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.