Question

How do I find the sum from 0 to i of a geometric series in the numerator, combination/factorial in the denominator?

Answer 1

Multiply all terms by i! to get C(i,k)n^k

Multiply all terms by 1^(i-k) to get C(i,k)n^k 1^(i-k)

The sum of all these terms is something you should know. Think about which context does C(i,k) appear?

Answer 2

Generally, knowing how to sum a_n and b_n separately doesn't lead to a nice formula for the sum of (a*b)_n. Sometimes summation by parts is helpful, sometimes not.

Can we find meaning in the expression? n^(k) counts the number of functions that map a k-element set to an n-element set. k is the size of the domain and n-k is the max size of the complement of the range (the set of elements each function doesn't hit). But because the functions are not generally bijective, that is all we can say about the range.

If we knew the functions were bijective, then there would be a nice relationship with combinations, but alas.

In what context did this arise?

Answer 3

So what's constant here?  You have three letters, and i is your index variable.  What is k doing?