• Support PF! Buy your school textbooks, materials and every day products Here!

Binomials and Proof by Induction

  • Thread starter math222
  • Start date
  • #1
10
0

Homework Statement



Prove (n choose k) ≤ ((en)/k)^k by induction on k.

Homework Equations



I can't of anything that's awfully relevant besides the general steps of induction.

The Attempt at a Solution



So I found it true for the k=1 case which was easy enough. Then assumed true the k case. And now have to prove the k+1 case.

So after working on the problem for awhile, I arrived at
((n-k)/(k+1)) * (n choose k) ≤ ((en)/k)^k * ((n-k)/(k+1))

but from here I'm stuck and not sure how to deconstruct the (n choose k) into something workable, let alone construct (n choose k+1). any help would be greatly appreciated.
 

Answers and Replies

  • #2
631
0
I'm not sure I understand the notation. What is "en"?
 
  • #3
10
0
the Euler number, e=2.718 or something i think. so en is e*n
 
  • #4
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,705
1,722

Homework Statement



Prove (n choose k) ≤ ((en)/k)^k by induction on k.

Homework Equations



I can't of anything that's awfully relevant besides the general steps of induction.

The Attempt at a Solution



So I found it true for the k=1 case which was easy enough. Then assumed true the k case. And now have to prove the k+1 case.

So after working on the problem for awhile, I arrived at
((n-k)/(k+1)) * (n choose k) ≤ ((en)/k)^k * ((n-k)/(k+1))

but from here I'm stuck and not sure how to deconstruct the (n choose k) into something workable, let alone construct (n choose k+1). any help would be greatly appreciated.
It might be helpful to note that
[tex] {n \choose k} = \frac{n (n-1) \cdots (n-k+1)}{k!}
= \frac{n^k (1 - \frac{1}{n})(1 - \frac{2}{n}) \cdots (1 - \frac{k-1}{n})}{k!},[/tex] and you can further bound the numerator and denominator.

RGV
 
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,772
911
the Euler number, e=2.718 or something i think. so en is e*n
Then you mean e^n. "en" and "e*n" would be e times n.
 
  • #6
10
0
no i mean e times n. hence en or e*n.
 
  • #7
10
0
i under the bound for the numerator, but i dont understand how to bound the denominator?
 

Related Threads for: Binomials and Proof by Induction

  • Last Post
Replies
5
Views
2K
Replies
5
Views
3K
Replies
3
Views
954
  • Last Post
Replies
1
Views
933
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
6
Views
714
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
2
Views
1K
Top