0
$\begingroup$

I have a d-degree polynomial $F(x) = a_0+a_1x+a_2x^2+.....+a_dx^d$

Now I want to evaluate the polynomial $F(x)-F(x-1)-F(x-2)$

What is the easiest way to simplify the polynomial $F(x)-F(x-1)-F(x-2)$

Doing it manually, ie expanding each binomial of (x-1)^k or (x-2)^k and then rearranging the coefficients seems to be very tedious way, I am sure there must be some determinant way of representing the coefficients of the resultant polynomial.

$\endgroup$
6
  • $\begingroup$ Taylor formula? $\endgroup$
    – Gary
    Sep 12, 2022 at 14:25
  • 3
    $\begingroup$ Is it any easier as $f(x+1)-f(x)-f(x-1)$? $\endgroup$
    – Empy2
    Sep 12, 2022 at 14:32
  • $\begingroup$ @Empy2. okay spreading on both sides decreases effort somewhat but I need formula for each coefficients for each x^k as a function of original coefficients. $\endgroup$
    – user1080747
    Sep 12, 2022 at 14:36
  • 1
    $\begingroup$ If you want the coefficients in the form $\sum b_ix^i,$ it's gonna be ugly, other than $b_d=-a_d.$ Even if you write it as $\sum c_i(x-1)^i,$ where it will be less painful, you will get a knot. $\endgroup$ Sep 12, 2022 at 14:36
  • $\begingroup$ @Gary can you elaborate. I know taylors series, but I dont understand how it can help me in rearranging and grouping coefficents. $\endgroup$
    – user1080747
    Sep 12, 2022 at 14:47

1 Answer 1

1
$\begingroup$

Taylor series seems like your best bet, but it is still a mess. Also, Taylor series have a problem when your underlying field is not of characteristic zero.

If $q$ is a polynomial of degree $\leq d,$ then $$q(x)=\sum_{k=0}^d \frac{q^{(k)}(0)}{k!}x^k,$$ where $q^{(k)}(x)$ is the (symbolic) $k$th derivative of $q.$

Letting $q(x)=F(x)-F(x-1)-F(x-2),$ you get:

$$q(x)=\sum_{k=0}^d \frac {F^{(k)}(0) - F^{(k)}(-1) -F^{(k)}(-2)}{k!}x^k.$$

Then $$\frac{F^{(k)}(x)}{k!}=\sum_{i=0}^{d-k} \binom{i+k}k a_{i+k}x^i.$$

So letting $$b_k=\sum_{i=0}^{d-k}\binom{i+k}ka_{i+k}(0^i-(-1)^i-(-2)^i),$$ where we interpret $0^0=1,$ we get: $$q(x)=\sum_{k=0}^{d} b_k x^k.$$

So you get $b_d=\binom{d+0}{d}a_d\left(0^0-(-1)^0-(-2)^0\right)=-a_d,$ and $$\begin{align}b_{d-1}&=\binom{d-1}{d-1}\left(0^0-(-1)^0-(-2)^0\right)a_{d-1}+\binom{d}{d-1}\left(0^1-(-1)^1-(-2)^1\right)a_d\\&=3da_d-a_{d-1}.\end{align}$$


If $P_d$ is the vector space of polynomials of degree $\leq d$ over $\mathbb Q$ or some other field of characteristic zero, we can consider the linear operator $T:P_d\to P_d$ with $T(q(x))=q(x-1).$

The best basis for studying $T$ is $$p_i(x)=\frac{x(x-1)\cdots(x-i+1)}{i!}=\binom{x}{i},$$ for $i=0,1,\dots,d.$ We get: $T(p_{i+1}(x))=p_{i+1}(x)-p_i(x).$ Then if:

$$F(x)=\sum_{k=0}^d a_k p_k(x)$$ you get: $$F(x)-F(x-1)-F(x-2)=(I-T-T^2)(F(x))=\sum_{k=0}^{d} \left(a_k-a_{k+1}-a_{k+2}\right)p_k(x),$$ where we treat $a_{i}$ as zero when $i>d.$

But that doesn't give us an easy way back to the usual basis.

This basis has the property that $-T,$ as a matrix over the basis, is in Jordan normal form, with all $-1$ on the diagonals, and $1$ at every entry just above the diagonal.

This shows that the minimum polynomial for $T$ is $(I-y)^{d+1}.$ That can also be seen when considering $I-T$ as the "finite difference operator" on polynomials of degree $\leq d.$

$\endgroup$
3
  • $\begingroup$ ok Thanks. $b_{d-2}$ wll have 3 terms and so on. .$b_0$, $b_1$ are going to be huge..I understand that. I was wondering if we could form any relation between sucessive coeffients such that if I could get inductively $b_{d-3}$ from $b_{d-2}$ and only add the new coefficients that didn't get list there. $\endgroup$
    – user1080747
    Sep 12, 2022 at 15:16
  • $\begingroup$ Probably not. You can precompute the $d+1$ values $0^i-(-1)^i-(-2)^i$ to slightly improve the calculation time, but it seems like there are $O(d^2)$ terms just in the binomials you need to compute. @LaylaBailey $\endgroup$ Sep 12, 2022 at 15:19
  • $\begingroup$ Ultimately, this is a linear operation on $a=(a_i)_{i=0}^d.$ The matrix is $M=(m_{ij})$ where $m_{ij}=\binom{j}i(0^{j-i}-(-1)^{j-i}-(-2)^{j-i}).$ It would be nice if we could factor $M,$ but it seems unlikely we can. $\endgroup$ Sep 12, 2022 at 15:31

You must log in to answer this question.