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

by Justin Skycak on

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*}

\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}.$

Tags: