4
$\begingroup$

Consider summing more and more factors of binomial coefficients:

Assuming[n ∈ Integers && n > 0, Sum[Binomial[n, i] // FunctionExpand, {i, 1, n}]] // FullSimplify

-1 + 2^n

Assuming[n ∈ Integers && n > 0, Sum[Binomial[n, i] Binomial[n - i, j] // FunctionExpand, {i, 1, n}, {j, 1, n - i}]] // FullSimplify

1 - 2^(1 + n) + 3^n

Assuming[n ∈ Integers && n > 0, Sum[Binomial[n, i] Binomial[n - i, j] Binomial[n - i - j, k] //FunctionExpand, {i, 1, n}, {j, 1, n - i}, {k, 1, n - i - j}]] // FullSimplify

-1 + 3 2^n - 3^(1 + n) + 4^n

Assuming[n ∈ Integers && n > 0, Sum[Binomial[n, i] Binomial[n - i, j] Binomial[n - i - j, k] Binomial[n - i - j - k, l] // FunctionExpand, {i, 1, n}, {j, 1, n - i}, {k, 1, n - i - j}, {l, 1, n - i - j - k}]] // FullSimplify

1 - 2^(2 + n) + 2 3^(1 + n) - 4^(1 + n) + 5^n

We can see that in each case the result is a sum over integers to the power n with some coefficients. Now I wonder if there is a way to use Mathematica to get the general expression for an arbitrary number of factors of binomial coefficients? (Continuing the above sequence all the way up to n factors of binomial coefficients under n sums.)

$\endgroup$
  • 1
    $\begingroup$ Oh, I'm silly... Seems like the coefficients are just binomial coefficients, power is always the same and sign is alternating... $\endgroup$ – Kagaratsch Mar 2 '17 at 22:16
  • $\begingroup$ Perhaps you should self-answer, or if you do not feel motivated to do so, delete this question? $\endgroup$ – Mr.Wizard Mar 3 '17 at 0:26
8
$\begingroup$

By inspection of the first few terms we can infer that the correct generalization should be:

fun[m_, n_] := Sum[(-1)^(q + m) Binomial[m - 1, q - 1] q^n, {q, 1, m}]

which properly reproduces the results:

Table[fun[m, n], {m, 2, 5}] // MatrixForm

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.