Solving Combinatorics Sum: Feyman's Logic Problem

[nowonda]

Hi all,

Can anyone gimme any clues to solve the sum below (or solve it outright :D)?

$$\sum_{i=k}^{n} \frac{i!}{(i-k)!}$$

I'm trying to solve one of Feyman's logic problems (bored geek alert) and I'm stuck at this point. And since my high school days are so far behind...

Thanks in advance!
Cheers!

 

[jwatts]

if it helps it's the sum of k! * i choose k

or you could break it down into gamma(i+1)/(gamma(i-k+1)

 

[nowonda]

Thanks for the input, jwatts, but I'm afraid I didn't get much, I did warn you my high school days are way behind me..

What do you mean by "choose k"?

As for the gamma function, I kinda think I'm going to get even farther from the answer, considering my current ability.

 

[jwatts]

n choose k = n!/k!(n-k)! it's called the binomial coefficient

saying it's k!*(n choose k) is kind of redundant but it let's you look at it in a different way
same way as looking at it like a gamma, even though gamma is used for continuous situations normally

 

[jwatts]

ok so the sum goes a bit like this k!(1+ (k+1)+((k+2)(k+1)/2)+((k+1)(k+2)(k+3)/3)+...)

 

[nowonda]

Oh, I see what you mean. Unfortunately that doesn't help, as it's precisely the way I got up to this point :) I'm not familiar with the "n choose k" terminology, that's why I was confused.

Thanks anyway, I'll keep trying.

 

[bpet]

It's possible with generating functions: use the fact that (i choose k) is the coefficient of x^k in (1+x)^i, so the sum is the coefficient of x^k in k!*((1+x)^n-(1+x)^k)/x.

 

[ssd]

Here is the answer. See attached image.

http://i48.tinypic.com/ojj94z.jpg

 

[nowonda]

Thanks a lot for your help, ssd! I really really appreciate it :)

However, in the meantime I changed my approach a bit (was trying to solve Feynman's Restaurant Problem) and I managed to get to a simpler sum, which I was able to calculate, to my complete surprise. I guess it just was way easier, although the method I used is for sure not optimal :)

$$\sum_{i=k}^{n} i{i-1 \choose k-1}=k{n+1 \choose k+1}$$

But thanks again for your solution, I'll sure learn something from your reasoning.

Cheers!