A Formula for the Partial Fractions Decomposition of $x^n/(x-a)^k$

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_{\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_{\max(0,1)}^0 \dfrac{\binom{1}{1-i} (-a)^{i}}{(x+a)^i} \\[5pt] &= 1 + \dfrac{-a}{x+1} \\[5pt] &= \dfrac{x}{x+1} \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+1)^k} = p(m,k) + f(m,k) \end{align*}$


where

  • $p(n,k) = \sum_{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_{\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_{\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_{\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} ) \\[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 \dfrac{x}{x+a} \\[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] &= \left[ x p(n,1) + (-a)^n \right] - a f(n,1) \\[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 \binom{k-1}{k} (-a)^{-1} x^{n-k} + a \sum_{i=0}^{n-k-1} \binom{n-1-i}{k} (-a)^{n-k-1-i} x^i \\[5pt] &= \binom{n}{k} (-a)^{n-k} + x p(n,k+1) + 0 + a p (n,k+1) \\[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_{\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 \in \mathbb{N}.$ Therefore, $P(n,k)$ for all $n \in \mathbb{N}.$