# Solve for equation algebraically

Is it possible to write the following function as $H(x)=$'some expresssion` ? $$D(x) = H(x) + H(x-1)$$

Edit: Hey everyone, thanks for all the great responses, and just to clarify H(x) and D(x) are always going to be polynomials, I wasn't sure if that made too big of a difference so I didn't mention it before.

Edit 2: I'm sincerely sorry if I was too general, I've only really used polynomial equations in my education thus far, so I didn't realize they might not seam just regular to everyone else. Once again I'm very sorry If I didn't give everyone an opportunity to answer the question because of my vagueness. I sincerely appreciate all of your answers and time.

-
Nothing special about $D$ and $H$? – J. M. Oct 17 '11 at 2:17
Nope, just two regular ol' functions. – Ryan Stull Oct 17 '11 at 4:37
Note that $H(x)$ is never completely determined by $D(x)$: you can replace $H(x)$ by $H(x) + P(x)$ for any function $P$ that is periodic with period 1 (e.g. $P(x) = \sin(2 \pi n x)$ for any integer $n$) and get the same $D(x)$. – Robert Israel Oct 17 '11 at 5:04
@Robert: Wouldn't $P(x)$ need to satisfy $P(x)+P(x-1)=0$, which implies a period of $2$? If so, then since $P(x-1)=-P(x)$, if $P(x)$ had a period of $1$, we would need to have $P(x)=0$. – robjohn Nov 12 '11 at 22:19
@Ratz: Restricting to polynomials is a very different situation than "just two regular ol' functions". Now you've had everybody chasing wild geese for weeks. – Henning Makholm Nov 13 '11 at 0:32

I will assume $x$ is an integer, and the functions are $\mathbb N \to \mathbb R$.

If you have a function $H$ such that $D(x)=H(x)+H(x-1)$ then you can add to $H$ the function $c (-1)^x$ for any constant $c$, and it will still be a solution. For example, while $0=0+0$, also $0=(-1)^x+(-1)^{x+1}$.

So the solution is not uniquely determined. How do you expect me to guess which $H$ did you mean when $D=0$? I will instead find all $H$ satisfying the equation.

Suppose

$D(x)=H(x)+H(x-1)$

this means

$H(x) = D(x) - H(x-1)$

This is a recurrence relation. If you know $H(0)$ you can compute all values of $H$ by going back, for example:

$H(2) = D(2) - H(1) = D(2) - (D(1) - H(0)) = D(2) - D(1) + H(0)$

and generally, the signs alternate:

$H(x) = \sum \limits_{i=1}^{x} (-1)^{x-i} D(i) + (-1)^x H(0)$

(easy to write formula for negative numbers too)

General formula:

$H(x) = \sum \limits_{i=1}^{x} (-1)^{x-i} D(i) + (-1)^x c$

where $c$ is any constant. The equation will be satisfied for any choice of $c$. (For more about that stuff, read about affine spaces or nonhomogeneous equations.)

-
Thank you, this is what I was looking for. – Ryan Stull Nov 13 '11 at 1:58
@Ratz: So when I wrote half an hour earlier that $H$ is the alternating sum, it was not what you were looking for? – Phira Nov 13 '11 at 8:50

Yes, although maybe not the prettiest one: $$D(x) - D(x - 1) + \cdots = H(x) + H(x - 1) - (H(x - 1) + H(x - 2)) + \cdots$$ Using summation notation, we have $$\sum_{n=0}^\infty (-1)^nD(x-n) = \sum_{n=0}^\infty (-1)^n(H(x-n) + H(x - n - 1)) = H(x)$$ And there you go.

-
If you're uncertain how this works, I would recommend writing out a few more terms in that first equation, just to see how it goes. – Arthur Oct 17 '11 at 2:32
You're making some assumption about convergence, no? – Gerry Myerson Oct 17 '11 at 2:59

$H(x)$ could be defined as anything on $[0,1)$, then the relation $$D(x) = H(x) + H(x-1)\tag{1}$$ would define $H(x)$ on the rest of $\mathbb{R}$. For example, for $x\ge0$, $$H(x)=(-1)^{\lfloor x\rfloor}H(x-\lfloor x\rfloor)+\sum_{k=0}^{\lfloor x\rfloor-1}(-1)^kD(x-k)\tag{2}$$ and for $x<0$, $$H(x)=(-1)^{\lfloor x\rfloor}H(x-\lfloor x\rfloor)+\sum_{k=\lfloor x\rfloor}^{-1}(-1)^kD(x-k)\tag{3}$$ Polynomial solutions:

Some interest was shown for polynomial solutions when $D(x)$ is a polynomial. As was done in another recent answer, we can use Taylor's Theorem to show that $$e^{-\mathcal{D}}P(x)=P(x-1)\tag{4}$$ where $\mathcal{D}=\dfrac{\mathrm{d}}{\mathrm{d}x}$, at least for polynomial $P$. Using $(4)$, $(1)$ becomes $$D(x)=\left(I+e^{-\mathcal{D}}\right)H(x)\tag{5}$$ Noting that $$(1+e^{-x})^{-1}=\tfrac{1}{2}+\tfrac{1}{4}x-\tfrac{1}{48}x^3+\tfrac{1}{480}x^5+\dots\tag{6}$$ we can get a polynomial solution of $(1)$ with $$H(x)=\left(\tfrac{1}{2}I+\tfrac{1}{4}\mathcal{D}-\tfrac{1}{48}\mathcal{D}^3+\tfrac{1}{480}\mathcal{D}^5+\dots\right)D(x)\tag{7}$$ Polynomial example:

For example, if $D(x)=x^2$, then using $(7)$, $H(x)=\tfrac{1}{2}x^2+\tfrac{1}{2}x$. Check: $$\left(\tfrac{1}{2}x^2+\tfrac{1}{2}x\right)+\left(\tfrac{1}{2}(x-1)^2+\tfrac{1}{2}(x-1)\right)=x^2$$

-
@Ratz: The polynomial solutions are unique and are given explicitly above. For higher order polynomials, you have to compute more terms of the Taylor expansion for $(1+e^{-x})^{-1}$ and plug them into $(7)$. I had added the polynomial solutions before you had narrowed the scope of your question to polynomials, but since the answer is so nice for polynomials, I added them, too. – robjohn Nov 13 '11 at 16:32

For $x$ an integer, up to a constant, $H(x)$ is the alternating sum of $D(x)$ from 0 up to $x$ (no reason to start at $-\infty$ like Arthur, although this might sometimes be preferable) since

$$((-1)^x D(0)- (-1)^x D(1)+\dots + D(x))+ ((-1)^{x-1}D(0) - (-1)^{x-1}D(1) + \dots + D(x-1)) = D(x)$$

and for $H(x)=0$ the equation gives a recurrence that fixes $D$ given $D(0)$.

Therefore, your problem includes the calculations of all finite sums and you cannot expect a reasonable answer without additional assumptions on your functions.

For example, if your $D$ is a polynomial, then you know that the answer is also a polynomial that can easily be found by an interpolation formula. Clearly, the polynomial equation will then hold for all $x$. For a hypergeometric expression, the Gosper algorithm can be adapted.

For an integrable function, the Euler-Maclaurin formula can sometimes be of use.

But there is no general answer. Sums do not always have simple answers and even if they do, there is no simple way to find them.

-

I'll use lower case, so $d(x) = h(x) + h(x-1)$.

Let $D(x) = \sum \limits_{n=0}^{\infty} d(n) x^n/n!$

and $H(x) = \sum \limits_{n=0}^{\infty} h(n) x^n/n!$.

$H'(x) = \sum \limits_{n=1}^{\infty} h(n) x^{n-1}/(n-1)! = \sum \limits_{n=0}^{\infty} h(n+1) x^n/n!$ so $H(x) + H'(x) = \sum \limits_{n=0}^{\infty} (h(n)+h(n+1)) x^n/n! = \sum \limits_{n=0}^{\infty} d(n+1) x^n/n!$.

Since $D'(x) = \sum \limits_{n=0}^{\infty} d(n+1) x^n/n!$, $H(x) + H'(x) = D'(x)$.

The usual integrating factor is $e^x$: $e^x D'(x) = e^x(H(x) + H'(x)) =(e^x H(x))'$, so $e^x H(x) = \int e^x D'(x) dx$ or $H(x) = e^{-x} \int e^x D'(x) dx$. If you can do the integral (and I haven't made too many mistakes) , you can get $H$.

You can integrate by parts, but you still have to deal with $\int e^x D(x) dx$.

Now I'll see what was entered while I was entering this ...

-
And once you have what you're calling $H$, there's still soomething to do to get what OP called $H$. – Gerry Myerson Oct 17 '11 at 3:01
True. It may be difficult to get the exponential generating function for some functions. I wonder what the OP's original D was? – marty cohen Oct 17 '11 at 3:43
Hey this looks promising but it didn't work for the original case I intended. If you look at the simple situation H(x) = x then D(x) = 2x-1 and D'(x)= 2. But then plug into the equation H(x) = e^-x*(|(e^x*2)dx) and the answer comes out to be 2. – Ryan Stull Nov 2 '11 at 23:54

You mentioned an example in one of your comments: if $H(x)=x$, then $D(x)=2x-1$. So let's suppose $D(x)=2x-1$ (for, say, $x=0,1,2,\dots$), and try to recover $H(x)$.

We have $1=D(1)=H(0)+H(1)$. What is $H(0)$? Well, it could be anything. You could take $H(0)=17$; then for $H(x)$ you would get the sequence $$17,-16,19,-14,21,-12,23,-10,\dots$$ given by the formula $H(x)=x+17(-1)^x$. The general solution is not just $H(x)=x$ but $$H(x)=x+H(0)(-1)^x$$ In short, you want a single function $H(x)$, but what we are all telling you in various ways is that for any given $D(x)$ there are infinitely many different $H(x)$.

-

I'm not sure if I'm interpreting the question correctly but I am reading it as follows.

Suppose that $D:\mathbb{R}\rightarrow\mathbb{R}$ is a polynomial with real coefficients. Does there exist a polynomial $H:\mathbb{R}\rightarrow\mathbb{R}$ such that $D(x)=H(x)+H(x-1)$.

Let $D(x)=\sum_{i=0}^na_ix^i$ ($a_n\neq0$). It's pretty clear that we need $H(x)$ to be of degree $n$ also. Let $H(x)=\sum_{i=0}^nb_ix^i$. Now

$H(x)+H(x-1)=\sum_{i=0}^n(b_ix^i+b_i(x-1)^i)$ $=\sum_{i=0}^n\left(b_ix^i+b_i\left(\sum_{j=0}^i{i\choose j}x^{i-j}(-1)^j\right)\right)$

Now we can ask the question what is the coefficient of $x^m$? Now the indices $i$, $j$ satisfy $0\leq j\leq i\leq n$. Hence for the $x^{i-j}$, we need $i-j=m$. This can only happen for $(i,j)\in{(m,0),(m+1,1),\dots,(m+(n-m),n-m)}$. Introduce the index $l=0,1,\dots,n-m$. Using this we can write the coefficient of $x^m$ and hence we solve the system of equations

$a_m=b_m+\sum_{l=0}^{m-n}b_{m+l}{m+l\choose l}(-1)^{m+1}$ for $m=0,1,\dots,n$.

These are equations of the form

$a_m=\sum_{k=m}^n\alpha^m_{k}b_k$. $(*)_m$

Hence the equation $a_n=\alpha^m_nb_n$ determines $b_n$ and we can solve sequentially for $b_{n-1},b_{n-2},\dots,b_0$ so that when we solve the $(*)_m$ the $b_k$ for $k>m$ have already been found. This implies that $H$ is in fact unique.

I hope this is what you were looking for and sorry it's a bit messy --- it's 2 a.m. in Ireland!

-