View source for Analytic Number Theory/Partial fraction decomposition

== Existence theorem ==
{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Theorem 2.1 (Existence theorem of the partial fraction decomposition)''':

Let <math>f, g</math> be polynomials over a unique factorisation domain, and let <math>g = \prod_{j=1}^n p_j^{k_j}</math>, where the <math>p_j</math> are irreducible. Then we may write
:<math>\frac{f(x)}{g(x)} = q(x) + \sum_{j=1}^n \sum_{l=1}^{k_j} \frac{a_{l, j}(x)}{p_j(x)^l}</math>,
where <math>a_{l, j}</math> are polynomials of degree strictly less than <math>p_j</math> and <math>q</math> is a polynomial. The term on the right hand side is called the '''partial fraction decomposition of <math>\frac{f}{g}</math>'''.}}

{{wikipedia|Partial fraction decomposition}}

'''Proof''':

We proceed by induction on <math>n</math>. For <math>n=1</math>, the statement is true since by division with remainder, we may write
:<math>f(x) = q_1(x) p_1(x) + r(x)</math>
with <math>\deg (r) <  \deg(p_1)</math> to obtain
:<math>\frac{f(x)}{g(x)} = \frac{q_1(x)}{p_1(x)^{k_1 - 1}} + \frac{r(x)}{g(x)}</math>,
and we have reduced the degree of the denominator by one (the latter summand already satisfies the required condition). By repetition of this process, we eventually obtain a denominator of one and thus a polynomial.

Let now the hypothesis be true for <math>n \in \mathbb N</math>, and assume that <math>g = \prod_{j=1}^{n+1} p_j^{k_j}</math>. Write <math>G = \prod_{j=1}^n p_j^{k_j}</math> and <math>H = p_{n+1}^{k_{n+1}}</math>. By irreducibility, <math>\gcd(G, H) = 1</math>. Hence, we find polynomials <math>S, T</math> such that <math>1 = SG + TH</math>. Then
:<math>\frac{f}{g} = \frac{f(SG + TH)}{g} = \frac{fSG}{g} + \frac{fTH}{g}</math>.
Each of the summands of the last term can by the induction hypothesis be written in the desired form.{{QED}}

== Technique ==
No matter how complicated our fraction of polynomials <math>\frac{f}{g}</math> may be, we can give the partial fraction decomposition in finite time, using easy techniques. The method, which for the sake of simplicity differs from the one given in the above constructive existence proof, goes as follows:
# Split the polynomial <math>g</math> into irreducible factors.
# Using division with remainder of <math>f</math> by <math>g</math>, reduce to the case <math>\deg(f) < \deg(g)</math> (the resulting polynomial <math>q</math> is allowed in the formula of theorem 2.1).
# Solve the equation given in theorem 2.1 for the <math>a_{l, j}</math> (this is equivalent to solving a system of linear equations; namely multiply by <math>g</math> and then equate coefficients).

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Theorem 2.2''':

The algorithm given above always terminates and gives the partial fraction decomposition of <math>\frac{f}{g}</math>.}}

'''Proof''': Due to theorem 2.1, in step three we do obtain a system of linear equations which is solvable. Hence follow termination and correctness.{{QED}}

=== Exercises ===

{{BookCat}}