Torelli's Sum
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$
- $\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
- 1895: Ruggiero Torelli: Qualche formola relativa all'interpretazione fattoriale delle potenze (Giornale di Matematiche di Battaglini Vol. 33: pp. 179 – 182)
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $34$