# Given a polynomial $P$ find $Q$ such that $Q(x)-Q(x-1)-Q(x-2)=P(x)$ for all $x$

Let $P\in\mathbb{Z}[x]$ be a given polynomial of degree $d$. I want to find the unique polynomial $Q\in\mathbb{Z}[x]$ of degree $d$ such that $Q(x)-Q(x-1)-Q(x-2)=P(x)$. It is possible to construct the solution writing $Q=\sum a_i x^i$ and solving the equation first for $a_n$, then for $a_{n-1}$ and so on, but this method requires $O(d^2)$ computations. I would like to solve it using $O(d)$ steps.

Motivation: Let us consider the recurrence $a_n=a_{n-1}+a_{n-2}+P(n)$ (with $a_0$ and $a_1$ given). It is easy to see that $a_n$ can be expressed as follows: $$a_n=\alpha F_n + \beta F_{n+1} + Q(n),$$ with $\alpha=a_1-a_0+Q(0)-Q(1)$ and $\beta=a_0-Q(0)$. This comes from a problem in SPOJ.

One possible approach: Assume we want to compute $a_n$ modulo some prime $p$ (which is small compared with $d$). We can compute $P(0)$, $P(1)$, ...,$P(p-1)$ (this can be done with $O(pd)$ operations) and get a linear system of $p$ equations and $p$ variables $Q(0)$, $Q(1)$, ..., $Q(p-1)$. The matrix of this system is almost triangular and it is easy to solve the system.
Example: $p=5$ $$\begin{pmatrix} 1 & 0 & 0 & -1 & -1 \\ -1 & 1 & 0 & 0 & -1 \\ -1 & -1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 1 & 0 \\ 0 & 0 & -1 & -1 & 1 \\ \end{pmatrix}\begin{pmatrix}Q(0)\\Q(1)\\Q(2)\\Q(3)\\Q(4)\end{pmatrix}= \begin{pmatrix}P(0)\\P(1)\\P(2)\\P(3)\\P(4)\end{pmatrix}$$ This system can be solved in $O(p)$, by precomputing some Fibonacci numbers.
In this way, It is possible to compute $a_n\mod p$ using $O(dp)$ steps. The most expensive part is the computation of the values of $P$.

Question: Is it possible to get a nice closed expression for $Q$ which allows us to compute a particular value $Q(n)$ relatively fast? It does not matter if the answer is modulo $p$ (but it should work for any $p$).

-
You lost me at "This system can be solved in $O(p)$, by precomputing some Fibonacci numbers." I would have thought solving $p$ linear equations, or congruences, would take $O(p^2)$. – Gerry Myerson Jul 11 '13 at 10:23
The system is not a general one. The matrix is almost triangular. I compute $Q(0)$ and $Q(1)$ (using those Fibonacci numbers) and then the rest of the values follow from $Q(x)=Q(x-1)+Q(x-2)+P(x)$. – Quimey Jul 11 '13 at 10:58

This is mostly working.

Let me cosmetically change your equation to $-R(x) + R(x-1) +R(x-2) = P(x)$, where $R(x) = -Q(x)$.

As you mentioned, we could try and find certain values. Observe that:
If $P_0(x) = 1$, then $R_0(x) = 1$.
If $P_1(x) = x$, then $R_1(x) = x+3$.
If $P_2(x) = x^2$, then $R_2(x) = x^2 + 6x + 13$.
If $P_3(x) = x^3$, then $R_3(x) = x^3 + 9x^2 + 39x + 81$.

We begin to see a pattern form. Observe that if $P_n(x) = x^n$, and we have an $R_n(x)$, then for $P_{n-1} (x) = x^{n-1}$, we have

$$P_{n-1} (x) = \frac{ P_n ' (x)}{n} = \frac{ -R_n '(x) +R'(x-1)+R'(x-2) } {n}$$

Hence, this tells us that $R_{n-1} (x) = \frac{R_n ' (x)}{n}$ is a solution. From your claim of uniqueness (which is easily proved), this is the only solution. As such, this allows us obtain that $R_n(x) = n \int R_{n-1}(x) \, dx + C_n$, where $C_n=R_n(0)$ is to be determined.

Let $S_n (x) = R_n(x) - R_n(0)$, which is the indefinite integral of $R_{n-1}$. We get that

$$- S_n(1) - C_n + C_n + S_n(1) + C_n = 1 \Rightarrow C_n = 1 + S_n(1) - S_n(-1)$$

At this point in time, the calculations are still on the order of $O(n^2)$.

However, if we add the condition that we're only interested in mod $p$, then a lot of the calculations can be simplified / cancelled out. In particular, $R_p(x) \equiv x^p + 3 \pmod {p}$.

-
+1 for the trick with the integral, but I can't see how to reduce the computation time. Assume that you get all the $R_i$ for free. In order to get $R$ you have to take a linear combination of the $R_i$ and this is still $n^2$. – Quimey Jul 12 '13 at 11:29
@Quimey I agree, as stated that was mostly working, and I can't get any aspect of it to shorten. – Calvin Lin Jul 14 '13 at 19:07