And a proof via double induction.
While conducting numerical experiments with partial fractions decomposition, I observed the following pattern:
$\begin{align*} \dfrac{x^n}{(x-a)^k} = \sum_{i=0}^{n-k} \binom{n-1-i}{k-1} a^{n-k-i} x^i + \sum_{i=\max(k-n,1)}^k \dfrac{\binom{n}{k-i} a^{n-k+i}}{(x-a)^i} \end{align*}$
for $n,k \in \mathbb{N}.$ The binomial coefficients are taken to be $0$ where they are otherwise undefined.
A proof is provided below. Double induction is used, abbreviating the above proposition as $P(n,k).$
First Base Case
We prove $P(1,1)$ as the basis for the first induction:
$\begin{align*} \dfrac{x}{x-a} &= \sum_{i=0}^{0} \binom{-i}{0} a^{-i} x^i + \sum_{i=\max(0,1)}^1 \dfrac{\binom{1}{1-i} a^{i}}{(x-a)^i} \\[5pt] &= 1 + \dfrac{a}{x-a} \\[5pt] &= \dfrac{x}{x-a} \end{align*}$
First Inductive Step
Assume $P(n,1)$ for $n \in \mathbb{N}.$ We will show that $P(n+1,1)$ follows.
First, we take the following notation in the theorem to be proved:
$\begin{align*} \dfrac{x^n}{(x-a)^k} = p(m,k) + f(m,k) \end{align*}$
where
- $p(n,k) = \sum\limits_{i=0}^{n-k} \binom{n-1-i}{k-1} a^{n-k-i} x^i$ is the polynomial part, and
- $f(n,k) = \sum\limits_{i=\max(1,n-k)}^k \dfrac{\binom{n}{k-i} a^{n-k+i}}{(x-a)^i}$ is the fractional part.
Note the following:
$\begin{align*} p(n,1) &= \sum_{i=0}^{n-1} \binom{n-1-i}{0} a^{n-1-i} x^i \\[5pt] &= \sum_{i=0}^{n-1} a^{n-1-i} x^i \\[10pt] f(n,1) &= \sum_{i=\max(1-n,1)}^n \dfrac{\binom{n}{1-i} a^{n-1+i}}{(x-a)^i} \\[5pt] &= \sum_{1}^n \dfrac{\binom{n}{1-i} a^{n-1+i}}{(x-a)^i} \\[5pt] &= \dfrac{a^n}{x-a} \end{align*}$
Additionally:
$\begin{align*} p(n+1,1) &= \sum_{i=0}^{n} \binom{n-i}{0} a^{n-i} x^i \\[5pt] &= \sum_{i=0}^{n} a^{n-i} x^i \\[5pt] &= a^n + \sum_{i=1}^{n} a^{n-i} x^i \\[5pt] &= a^n + \sum_{i=0}^{n-1} a^{n-(i+1)} x^{i+1} \\[5pt] &= a^n + x \sum_{i=0}^{n-1} a^{n-1-i} \\[5pt] &= a^n + x p(n,1) \\[5pt] f(n+1,1) &= \sum_{i=\max(-n,1)}^{n+1} \dfrac{\binom{n+1}{1-i} a^{n+i}}{(x-a)^i} \\[5pt] &= \sum_{1}^{n+1} \dfrac{\binom{n+1}{1-i} a^{n+i}}{(x-a)^i} \\[5pt] &= \dfrac{a^{n+1}}{x-a} \\[5pt] &= a f(n,1) \end{align*}$
Finally, using $P(n,1),$ we have
$\begin{align*} \dfrac{x^{n+1}}{x-a} &= x \left( \dfrac{x^n}{x-a} \right) \\[5pt] &= x \left( p(n,1) + f(n,1) \right) \\[5pt] &= x \left( p(n,1) + \dfrac{a^n}{x-a} \right) \\[5pt] &= x p(n,1) + a^n \left( \dfrac{x}{x-a} \right) \\[5pt] &= x p(n,1) + a^n \left( 1 + \dfrac{a}{x-a} \right) \\[5pt] &= x p(n,1) + a^n + \dfrac{a^{n+1}}{x-a} \\[5pt] &= p(n+1,1) + f(n+1,1), \end{align*}$
which proves $P(n+1,1)$ as desired.
First Inductive Conclusion (Second Base Case)
We have proven $P(1,1)$ and shown that $P(n,1) \Longrightarrow P(n+1,1)$ for $n \in \mathbb{N}.$ Therefore, $P(n,1)$ for all $n \in \mathbb{N}.$
Second Inductive Step
Assume $P(n,k)$ for $n,k \in \mathbb{N}.$ We will show that $P(n,k+1)$ follows.
Using $P(n,k),$ we have
$\begin{align*} \dfrac{x^n}{(x-a)^{k+1}} &= \dfrac{1}{x-a} \left( \dfrac{x^n}{(x-a)^k} \right) \\[5pt] &= \dfrac{1}{x-a} \left( p(n,k) + f(n,k) \right) \\[5pt] &= \dfrac{p(n,k)}{x-a} + \dfrac{f(n,k)}{x-a}. \end{align*}$
We will now re-express each term in the sum above.
Using Pascal’s identity in the form
$\begin{align*} \binom{n-1-i}{k-1} = \binom{n-i}{k} - \binom{n-1-i}{k}, \end{align*}$
we have
$\begin{align*} \dfrac{p(n,k)}{x-a} &= \sum_{i=0}^{n-k} \binom{n-1-i}{k-1} a^{n-k-i} x^i \\[5pt] &= \sum_{i=0}^{n-k} \binom{n-i}{k} a^{n-k-i} x^i - \sum_{i=0}^{n-k} \binom{n-1-i}{k} a^{n-k-i} x^i \\[5pt] &= \sum_{i=-1}^{n-k-1} \binom{n-i-1}{k} a^{n-k-1-i} x^{i+1} - a \sum_{i=0}^{n-k} \binom{n-1-i}{k} a^{n-k-1-i} x^i \\[5pt] &= \binom{n}{k} a^{n-k} + \sum_{i=0}^{n-k-1} \binom{n-i-1}{k} a^{n-k-1-i} x^{i+1} \\[3pt] &\phantom{=} - a\left[ \binom{k-1}{k} a^{-1} x^{n-k} + \sum_{i=0}^{n-k-1} \binom{n-1-i}{k} a^{n-k-1-i} x^i \right] \\[5pt] &= \binom{n}{k} a^{n-k} + x p(n,k+1) - a\left[ 0 + p (n,k+1) \right] \\[5pt] &= \binom{n}{k} a^{n-k} + (x - a) p(n,k+1). \end{align*}$
Simplifying the second term in the sum, we have
$\begin{align*} \dfrac{f(n,k)}{x-a} &= \sum_{i=\max(k-n,1)}^k \dfrac{\binom{n}{k-i} a^{n-k+i}}{(x-a)^i} \\[5pt] &= \sum_{i=1}^k \dfrac{\binom{n}{k-i} a^{n-k+i}}{(x-a)^i} \textrm{ (introducing terms equal to 0)} \\[5pt] &= \sum_{i=2}^{k+1} \dfrac{\binom{n}{k+1-i} a^{n-k-1+i}}{(x-a)^i} \\[5pt] &= \sum_{i=1}^{k+1} \dfrac{\binom{n}{k+1-i} a^{n-k-1+i}}{(x-a)^i} - \dfrac{\binom{n}{k} a^{n-k}}{x-a} \\[5pt] &= f(n,k+1) - \dfrac{\binom{n}{k} a^{n-k}}{x-a} \textrm{ (removing terms equal to 0)}. \end{align*}$
Finally, we substitute into our original sum and reach
$\begin{align*} \dfrac{x^n}{(x-a)^{k+1}} &= \dfrac{p(n,k)}{x-a} + \dfrac{f(n,k)}{x-a} \\[5pt] &= \dfrac{\binom{n}{k} a^{n-k} + (x - a) p(n,k+1)}{x-a} + f(n,k+1) - \dfrac{\binom{n}{k} a^{n-k}}{x-a} \\[5pt] &= p(n,k+1) + f(n,k+1), \end{align*}$
as desired.
Second Inductive Conclusion
We have proven $P(n,1)$ and shown that $P(n,k) \Longrightarrow P(n,k+1)$ for $n,k \in \mathbb{N}.$ Therefore, $P(n,k)$ for all $n,k \in \mathbb{N}.$