# Hard Math Problem

Discussion in 'BlackHat Lounge' started by fusilli_jerry89, Oct 16, 2009.

1. ### fusilli_jerry89Regular Member

Joined:
Dec 7, 2008
Messages:
280
40
just wondering if anyone knows how to do this?

Show that nCk >= (n/k)^k

That is, show that n chose k is greater than or equal to (n/k)^k

Any ideas?

2. ### im n0t lurerRegular Member

Joined:
Jun 29, 2009
Messages:
229
54
no sorry, you best bet would be to try make a triangel with 4 angles.. XD

btw what kind of math is that lol?

3. ### oxonbeefBANNEDBANNED

Joined:
Jan 4, 2009
Messages:
2,241
7,873
the proof of binomial coefficient

(x+y)^n = sum(k=0,n, nCk x^(n-k) y^k)

and we want to show that:

nCk = (n!)/(n-k)!k!

is true. So let's use induction on n.

Base case: n = 1. (x+y)^1 = x+y, so 1C0 = 1C1 = 1!/1!0! = 1!/0!1!.

Inductive step: suppose nCk = (n!)/(n-k)!k! for some n and all 0 â‰¤ k â‰¤ n. We'll show it's true for n+1 and all 0 â‰¤ k â‰¤ n+1. So

(x+y)^(n+1) = (x+y)(x+y)^n = (x+y)sum(k=0,n, nCk x^(n-k) y^k)

So multiply through and note that the coefficient on x^(n+1-k) y^k is:

for k = 0: 1 = (n+1)!/(n+1)!0!
for k = n+1: 1 = (n+1)!/0!(n+1)!
for 1 â‰¤ k â‰¤ n: nCk + nC(k-1)

So we want to show that nCk + nC(k-1) = (n+1)!/(n+1-k)!k!. So:

n!/(n-k!)k! + n!/(n+1-k)!(k-1)! = [n!(n+1-k)+n!k]/(n+1-k)!k! = n!(n+1)/(n+1-k)!k! = (n+1)!/(n+1-k)!k!