# What is $f(x)$ divided by $(x-a)$?

This is an exercise from Spivak's Calculus:

Prove that for any polynomial function $f$, and any number $a$, there is a polynomial function $g$, and a number $b$, such that $f(x)=(x-a)g(x)+b$ for all $x$. (The idea is simply to divide $(x-a)$ into $f(x)$ by long division, until a constant remainder is left. [. . .] A formal proof is possible by induction on the degree of $f$.

I did an adaptation of this question and decided to figure out precisely what $g(x)$ and $b$ are. Here is what I ended up with:

First, presume $f$ takes the form: $$f_n(x)=\sum_{u=0}^{n}c_ux^u$$

Then: $$f_n(x)=(x-a)\sum_{q=1}^{n}\sum_{z=q}^{n}a^{z-q}c_zx^{q-1}+\sum_{z=0}^{n}a^zc_z$$

I've had a really hard time figuring out a clean and nice way to show this is true. But, I'm pretty sure it's accurate. I can't quite show the extensive work in deriving this because it's a lot of synthetic division and long division, then noticing patterns among the remainders and the quotients. My manipulations of double sums are not that great, so I'd appreciate if anyone could either 1) show that I'm wrong (which is very possible) or 2) show how this is right, in a preferably elegant way.

One method is thus: Assuming that $b=\sum_{z=0}^{n}a^zc_z$, then $g(x)$ could be derived by 'basic' algebra: $$\sum_{u=0}^{n}c_ux^u=(x-a)g(x)+\sum_{z=0}^{n}a^zc_z \Rightarrow g(x)=\frac{\sum_{u=0}^{n}c_ux^u-a^{u}c_u}{(x-a)}$$ $$g(x)=\frac{\sum_{u=0}^{n}c_u(x^u-a^u)}{(x-a)}$$ $$\frac{x^u-a^u}{(x-a)}=\sum_{k=1}^{u}a^{u-k}x^{k-1}$$ $$\therefore g(x)=\sum_{u=0}^{n}\sum_{k=1}^{u}a^{u-k}c_ux^{k-1}$$

This seems to contradict what I just wrote, but it brings up another question: Is $$\sum_{u=0}^{n}\sum_{k=1}^{u}a^{u-k}c_ux^{k-1}=\sum_{q=1}^{n}\sum_{z=q}^{n}a^{z-q}c_zx^{q-1}\text{?}$$

I think it is, and I can show that thus:

First, change the right hand side: $\sum_{k=1}^{n}\sum_{u=k}^{n}a^{u-k}c_ux^{k-1}$. Then, make the substitution $e_{u,k}=a^{u-k}c_ux^{k-1}$

So, you have:

$$\sum_{u=0}^{n}\sum_{k=1}^{u}e_{u,k}=\sum_{k=1}^{0}e_{0,k}+\sum_{k=1}^{1}e_{1,k}+\sum_{k=1}^{2}e_{2,k}+\dots+\sum_{k=1}^{n-2}e_{(n-2),k}+\sum_{k=1}^{n-1}e_{(n-1),k}+\sum_{k=1}^{n}e_{n,k}$$ $$\sum_{u=0}^{n}\sum_{k=1}^{u}e_{u,k}=\sum_{k=1}^{n}e_{n,k}+\sum_{k=1}^{n-1}e_{(n-1),k}+\sum_{k=1}^{n-2}e_{(n-2),k}+\dots+\sum_{k=1}^{2}e_{2,k}+\sum_{k=1}^{1}e_{1,k}+\sum_{k=1}^{0}e_{0,k}$$

Each sum can be modified thusly:

$$\sum_{k=1}^{n-j}e_{(n-j),k}=\sum_{k=(1+j)}^{n}e_{(n-j),(k-j)}$$

So, by inspection, the two sums are equivalent.

I guess what my question now amounts to is thus: Are there any methods I'm simply not using that I could be using? And am I incorrect in any of my methods and statements above? Feel free to use a completely different approach to solve this, I'd like to see other approaches.

P.S. If you would like, feel free to provide a proof of the original problem by induction.

-
You can save a lot of messiness by doing an induction. To go from $k-1$ to $k$, use your observation about $\frac{x^k-a^k}{x-a}$. –  André Nicolas Jan 14 '12 at 19:20
$a$ is a root of the polynomial $p(x)=f(x)-f(a)$. Therefore (by the "factor theorem") we can write $p(x)=(x-a)g(x)$ for a polynomial $g(x)$ of lower degree. –  Mark Jan 14 '12 at 19:22
You also have $$g(x)=\sum_{n\ge1}\ \frac{f^{(n)}(a)}{n!}\ (x-a)^{n-1}.$$ –  Pierre-Yves Gaillard Jan 14 '12 at 19:24
That's awesome, Pierre. Could you provide a derivation of that? My mathematical abilities are not so keen on nth derivatives. (It looks oddly familiar, though... I don't know where I've saw it before.) –  000 Jan 14 '12 at 19:29
Dear user22144: This is just Taylor's formula. (I saw your comment by chance. If you write @Xinstead of X, then X is notified.) –  Pierre-Yves Gaillard Jan 14 '12 at 20:00
show 1 more comment

Suppose $f(x)$ is an $n$th degree polynomial. Then $$\begin{eqnarray*} f(x) &=& \sum_{k=0}^n \frac{f^{(k)}(a)}{k!} (x-a)^k \\ &=& \sum_{k=1}^n \frac{f^{(k)}(a)}{k!} (x-a)^k + f(a) \\ &=& (x-a) \sum_{k=1}^n \frac{f^{(k)}(a)}{k!} (x-a)^{k-1} + f(a) \\ &=& (x-a) \underbrace{\sum_{k=0}^{n-1} \frac{f^{(k+1)}(a)}{(k+1)!} (x-a)^{k}}_{g(x)} + \underbrace{f(a)}_b. \end{eqnarray*}$$ As claimed, $g(x)$ is a polynomial (of degree $n-1$) and $b$ is a constant. We have used the fact that the Taylor expansion of a polynomial of degree $n$ terminates at the $n$th term, since $D^m x^n = 0$ for $m>n$. It is a good exercise to show that this $g$ and $b$ agree with your formula for $f$.
I recommend using the Iverson bracket when manipulating double sums (among other things). Here's a sample calculation: $$\begin{eqnarray*} \sum_{a=0}^n \sum_{b=0}^a &=& \sum_{a,b} [0\le a\le n] [0\le b \le a] \\ &=& \sum_{a,b} [0\le b\le a\le n] \\ &=& \sum_{a,b} [0 \le b \le n] [b \le a \le n] \\ &=& \sum_{b=0}^n \sum_{a=b}^n \end{eqnarray*}$$