Sum over k of r-kt choose k by r over r-kt by z^k
Jump to navigation
Jump to search
Theorem
Let $n \in \Z_{\ge 0}$ be a positive integer.
Let $\map {A_n} {x, t}$ be the polynomial of degree $n$ defined as:
- $\map {A_n} {x, t} := \dbinom {x - n t} n \dfrac x {x - n t}$
for $x \ne n t$.
Let $z = x^{t + 1} - x^t$.
Then:
- $\ds \sum_k \map {A_k} {r, t} z^k = x^r$
for sufficiently small $z$.
Proof
From Sum over $k$ of $\paren {-1}^k$ by $\dbinom n k$ by $\dbinom {r - k t} n$ by $\dfrac r {r - k t}$ and renaming variables:
- $\ds \sum_j \paren {-1}^j \dbinom k j \dbinom {r - j t} k \dfrac r {r - j t} = \delta_{k 0}$
where $\delta_{k 0}$ is the Kronecker delta.
Thus:
- $\ds \sum_{j, k} \paren {-1}^j \dbinom k j \dbinom {r - j t} k \dfrac r {r - j t} w^k = 1$
We have:
\(\ds \) | \(\) | \(\ds \sum_{j, k} \paren {-1}^j \dbinom k j \dbinom {r - j t} k \dfrac r {r - j t} w^k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_j \paren {-1}^j \dfrac r {r - j t} \sum_k \dbinom k j \dbinom {r - j t} k w^k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_j \paren {-1}^j \dfrac r {r - j t} \sum_k \dbinom {r - j t} j \dbinom {r - j t - j} {k - j} w^k\) | Product of $\dbinom r m$ with $\dbinom m k$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_j \paren {-1}^j \dfrac r {r - j t} \dbinom {r - j t} j \sum_k \dbinom {r - j t - j} {k - j} w^k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_j \paren {-1}^j \map {A_j} {r, t} \sum_k \dbinom {r - j t - j} {k - j} w^k\) | Definition of $\map {A_j} {r, t}$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_j \paren {-1}^j \map {A_j} {r, t} \paren {1 + w}^{r - j t - j} w^j\) | Binomial Theorem |
Now let:
- $x = \dfrac 1 {1 + w}$
\(\ds x\) | \(:=\) | \(\ds \dfrac 1 {1 + w}\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds z\) | \(=\) | \(\ds -\frac w {\paren {1 + w}^{1 + t} }\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \paren {1 + w}^{r - j k - j} w^j \paren {-1}^j\) | \(=\) | \(\ds z^r z^j\) |
Thus:
\(\ds \sum_j \map {A_j} {r, t} z^j \paren {1 + w}^r\) | \(=\) | \(\ds 1\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_j \map {A_j} {r, t} z^j\) | \(=\) | \(\ds \paren {1 + w}^{- r}\) | |||||||||||
\(\ds \) | \(=\) | \(\ds x^r\) |
This needs considerable tedious hard slog to complete it. In particular: Establish the fact that we have convergence by ratio test and estimates for large $k$. Or use complex variable theory to establish that the function is analytic around $x = 1$. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Finish}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |
$\blacksquare$
Also see
- Binomial Theorem: obtained by setting $t = 0$ in this result
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $25$
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.9$: Generating Functions: $(21)$