In this chapter, we are going to tackle the first section of our proof, using a method known as 'Proof by Induction'. It allows us to induce the truth of a statement over all terms in a sequence having only proved that it holds for the first term, and that if it's true for any random term, it also holds for the next. Imagine a line of pillars out at sea, evenly spaced apart and stretching into the horizon. If I place you on the first pillar, and build you a portable bridge that spans the gap between one pillar and the next, it follows that you will be able to reach any pillar, even if the line is infinitely long!
In accordance with the above, proofs by induction have two primary parts: the base case, where we prove the statement's truth for the first term; and the inductive step, where we use the inductive hypthesis, which allows assuming the statement's truth for the \(k\)th term, to prove it for the \((k+1)\)th term. To prove anything though, we must know what it is that we are proving, this will now be addressed.
Our goal here is to prove that where an algebraic fraction has a denominator of the form \((x+a)^n\) and a numerator which is a power of \(x\) with exponent less than the denominator's order, it can be decomposed into a sum of fractions where the numerators are constant, and the denominators are the powers of \((x+a)\). Formally stated, we want to prove that constant \(A\)s exist where \[ \frac{x^m}{(x+a)^n}\equiv \frac{A_1}{x+a}+\frac{A_2}{(x+a)^2}+\dots+\frac{A_n}{(x+a)^n} \] \[ \textrm{where}\quad n,m\in\mathbb{Z}\quad\textrm{and}\quad 0\leq m\lt n \textrm{.} \] We are going to use induction to prove this. However, a problem lies in the existence of two variables. Induction only allows us to vary one at a time. To get around this, we leave \(n\) as completely general, and induce the statement over all values of \(m\).
In our base case, we let \(m=0\), which makes things nice and simple, as \(x^0\) is already constant, it's just \[ \frac{1}{(x+a)^n} \equiv \frac{0}{x+a} + \frac{0}{(x+a)^2} + \dots + \frac{1}{(x+a)^n} \textrm{.} \] No further proof is required for this, so we can move on the inductive step. Our inductive hypthesis lets us assume the truth of our statement for \(m=k\), so \[ \frac{x^k}{(x+a)^n} \equiv \frac{B_1}{x+a} + \frac{B_2}{(x+a)^2} + \dots + \frac{B_n}{(x+a)^n} \] \[ \textrm{where} \quad k+1\lt n \] Recall that the important part of this is that all \(B\)s are constant.
Our objective now is to prove RHS numerator constancy for a LHS numerator power of \(k+1\). We start with some manipulation of the expression: \[ \frac{x^{k+1}}{(x+a)^n}\equiv x\times\frac{x^k}{(x+a)^n} \] \[ \equiv x\times\left(\frac{B_1}{x+a}+\frac{B_2}{(x+a)^2}+\dots+\frac{B_n}{(x+a)^n}\right) \] \[ \equiv\frac{B_1x}{x+a}+\frac{B_2x}{(x+a)^2}+\dots+\frac{B_nx}{(x+a)^n} \] This is a good start. We have a sum of terms that are all of the same form, \[ \frac{x}{(x+a)^n} \textrm{.} \] However, looking at their composition and noticing the \(n\) in the denominator, there's a slight scare that we might need a whole separate proof by induction to deal with them. Fortunately, we can decompose them with just a bit of rearranging! \[ \frac{x}{(x+a)^n}\equiv\frac{x+a-a}{(x+a)^n} \] \[ \equiv\frac{x+a}{(x+a)^n}-\frac{a}{(x+a)^n} \] \[ \frac{x}{(x+a)^n}\equiv\frac{1}{(x+a)^{n-1}}-\frac{a}{(x+a)^n} \] Having sidestepped several additional pages of working, we can return to our main identity.
Substituting what we found in, we get the following: \[ \frac{x^{k+1}}{(x+a)^n}\equiv\frac{B_1x}{x+a}+\frac{B_2x}{(x+a)^2}+\dots+\frac{B_nx}{(x+a)^n} \] \[ \equiv B_1\left(1-\frac{a}{x+a}\right)+B_2\left(\frac{1}{x+a}-\frac{a}{(x+a)^2}\right)+\dots+B_n\left(\frac{1}{(x+a)^{n-1}}-\frac{a}{(x+a)^n}\right) \] \[ \equiv B_1+\frac{B_2-B_1a}{(x+a)}+\dots+\frac{B_n-B_{n-1}a}{(x+a)^{n-1}}-\frac{B_na}{(x+a)^n} \] We're practically there, all of these \(B_n-B_{n-1}a\) terms are constant and pose no problem. The only thorn in our side is the initial \(B_1\), whose existence is not permitted in our definition of partial fraction decomposition, as all terms must be fractions.
To deal with this problematic \(B_1\) term, we must prove it is equivalent to \(0\). To begin, we return to our inductive assumption. \[ \frac{x^k}{(x+a)^n}\equiv\frac{B_1}{x+a}+\frac{B_2}{(x+a)^2}+\dots+\frac{B_n}{(x+a)^n} \] \[ k+1\lt n \] We will now commence a proof by contradiction. We wish to prove that \(B_1=0\), so we will assume it is not. \[ B_1\neq0 \] We will now multiply out the identity in our assumption. \[ x^k=B_1(x+a)^{n-1}+B_2(x+a)^{n-2}+\dots+B_n \] Notice that, after expansion, \(x^k\) and \(B_1x^{n-1}\) are the highest powers of \(x\) on each side of the identity. Since both sides of an identity are the same function of \(x\), they must have the same index, giving: \[ k=n-1 \] \[ k+1=n \textrm{.} \] However, this violates our inductive assumption that \(k+1\lt n\), therefore \(B_1=0\).
The method above, with its explicit reference to the inequality \(k+1 \lt n\), emphasises that the induction we are using is not over an infinite number of terms, in fact there are exactly \(n\) terms. This poses no problem however. To return to the analogy earlier, the number of pillars in the line does not matter. Whether there's 4, 256, or an infinite number, so long as you are placed on the first pillar, and given the bridge, all can be reached.
Although we've managed to avoid dealing with the two variables (\(n\) and \(m\)) separately in this instance, induction really shows its worth throughout the wider proof in that, by using it on one variable at a time, we are able to steadily add the layers of generality necessary to achieve the original, very broad, statement. The history of induction itself is reminiscent of this slow creep. As a concept, its been used since the era of Ancient Greece, and has been refined over time until, in 1665, it found itself in its modern form on the pages of Pascal. It is a highly useful technique which you will be seeing alot more of over the coming chapters!
Returning to our proof, we can use the nonexistence of \(B_1\) to continue from where we left off: \[ \frac{x^{k+1}}{(x+a)^n}\equiv\frac{B_2}{x+a}+\frac{B_3-B_2b}{(x+a)^2}+\dots+\frac{B_n-B_{n-1}b}{(x+1)^{n-1}}-\frac{B_nb}{(x+a)^n} \] \[ \equiv\frac{A_1}{(x+a)}+\frac{A_2}{(x+a)^2}+\dots+\frac{A_n}{(x+a)^n} \square \] We have now proved the partial fraction decomposition for denominators with a single distinct factor.