Solving Combinatorics Sum: Feyman's Logic Problem

  • Context: Undergrad 
  • Thread starter Thread starter nowonda
  • Start date Start date
  • Tags Tags
    Combinatorics Sum
Click For Summary

Discussion Overview

The discussion revolves around solving a combinatorial sum related to Feynman's logic problems, specifically the sum \(\sum_{i=k}^{n} \frac{i!}{(i-k)!}\). Participants explore various approaches and interpretations of the problem, including connections to binomial coefficients and generating functions.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Homework-related

Main Points Raised

  • One participant seeks help with the sum and expresses uncertainty due to a lack of recent mathematical practice.
  • Another participant suggests that the sum can be expressed as \(k! \cdot \binom{i}{k}\) and mentions the gamma function as an alternative representation.
  • A participant clarifies the meaning of "n choose k" as the binomial coefficient and discusses its redundancy in the context of the problem.
  • One participant proposes a series expansion approach to the sum, indicating a potential path to a solution.
  • Another participant introduces generating functions, stating that \(\binom{i}{k}\) can be represented as the coefficient of \(x^k\) in \((1+x)^i\), suggesting a method to compute the sum.
  • A participant shares an image purportedly containing the answer to the original sum, although the content of the image is not discussed in detail.
  • One participant reports a shift in focus to a different problem, the Feynman's Restaurant Problem, and mentions successfully simplifying a related sum.

Areas of Agreement / Disagreement

Participants express various methods and interpretations of the sum, but there is no consensus on a single approach or solution. The discussion remains open-ended with multiple perspectives presented.

Contextual Notes

Some participants express uncertainty about terminology and mathematical concepts, indicating a potential gap in foundational knowledge that may affect their understanding of the problem.

nowonda
Messages
6
Reaction score
0
Hi all,

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

[tex]\sum_{i=k}^{n} \frac{i!}{(i-k)!}[/tex]

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!
 
Physics news on Phys.org
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)
 
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.
 
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
 
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)+...)
 
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.
 
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.
 
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 :)

[tex]\sum_{i=k}^{n} i{i-1 \choose k-1}=k{n+1 \choose k+1}[/tex]

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

Cheers!
 

Similar threads

  • · Replies 29 ·
Replies
29
Views
6K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 13 ·
Replies
13
Views
4K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 3 ·
Replies
3
Views
3K
  • · Replies 3 ·
Replies
3
Views
1K
  • · Replies 8 ·
Replies
8
Views
3K
Replies
1
Views
2K
  • · Replies 9 ·
Replies
9
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K