Torelli's Sum

From ProofWiki
Jump to navigation Jump to search

Theorem

$\ds \paren {x + y}^{\overline n} = \sum_k \binom n k x \paren {x - k z + 1}^{\overline {k - 1} } \paren {y + k z}^{\overline {n - k} }$

where:

$\dbinom n k$ denotes a binomial coefficient
$x^{\overline k}$ denotes $x$ to the $k$ rising.


Proof

From Rising Factorial as Factorial by Binomial Coefficient:

$\paren {x + y}^{\overline n} = n! \dbinom {x + y + n - 1} n$


Recall Sum over $k$ of $\dbinom {r - t k} k$ by $\dbinom {s - t \paren {n - k} } {n - k}$ by $\dfrac r {r - t k}$:

$\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + s - t n} n$


Let the following substitutions be made:

$r \gets x$
$t \gets -\paren {1 - z}$
$s \gets y - 1 + n z$

and so to obtain:

$\ds \dbinom {x + y + n - 1} n = \sum_k \dbinom {x + \paren {1 - z} k} k \dbinom {y - 1 + n z + \paren {n - k} \paren {1 - z} } {n - k} \dfrac x {x + \paren {1 - z} k}$


Then:

\(\ds \dbinom {x + \paren {1 - z} k} k\) \(=\) \(\ds \dfrac {\paren {x - k z + 1}^{\overline k} } {k!}\) Rising Factorial as Factorial by Binomial Coefficient
\(\ds \leadsto \ \ \) \(\ds \dfrac x {x + \paren {1 - z} k} \dbinom {x + \paren {1 - z} k} k\) \(=\) \(\ds \dfrac {x \paren {x - k z + 1}^{\overline {k - 1} } } {k!}\)


and:

\(\ds \dbinom {y - 1 + n z + \paren {n - k} \paren {1 - z} } {n - k}\) \(=\) \(\ds \dbinom {y - 1 + n z + n - k - n z + k z} {n - k}\)
\(\ds \) \(=\) \(\ds \dbinom {y + k z \paren {n - k} - 1} {n - k}\)
\(\ds \) \(=\) \(\ds \frac 1 {\paren {n - 1}!} \paren {y + k z}^{\overline {n - k} }\) Rising Factorial as Factorial by Binomial Coefficient


Hence:

\(\ds n! \dbinom {x + y + n - 1} n\) \(=\) \(\ds \sum_k \frac {n!} {k! \paren {n - k}!} x \paren {x - k z + 1}^{\overline {k - 1} } \paren {y + k z}^{\overline {n - k} }\)
\(\ds \leadsto \ \ \) \(\ds \paren {x + y}^{\overline n}\) \(=\) \(\ds \sum_k \binom n k x \paren {x - k z + 1}^{\overline {k - 1} } \paren {y + k z}^{\overline {n - k} }\)

$\blacksquare$


Source of Name

This entry was named for Ruggiero Torelli.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Torelli%27s_Sum&oldid=510656"