# Difference equation and formal series

For a given formal series $g(x)=\sum_{k=0}^\infty g_k x^k$ I would like to find a formal series $f(x)=\sum_{k=0}^\infty f_k x^k$ such that they satisfy the difference equation $$f(x+1)-f(x)=g(x).$$

Is there any description of all $g(x)$ for which $f(x)$ exists?

• What is $f(x+1)$ for a formal series? (Maybe you want $f$ to have a radius of convergence larger than $1$?) – Pietro Majer Dec 14 '16 at 15:53
• Well, for some formal series the coefficients of $f(x+1)$ are well defened. I just want to undestend how to describe all $g(x)$ such that $f(x)$ and $f(x+1)$ exist and the equation is satisfied. – Sasha Dec 14 '16 at 18:49
• If you want $f(x+1)$ to be well-defined then $f$ must be convergent with radius of convergence at least $1$, so this question is more difficult. In particular, you mus specify the domain to which $x$ belongs. – Loïc Teyssier Dec 14 '16 at 19:43
• By writing $f(x+1)$ you are not just allowing formal series, but have to specify what convergence of a series of scalars means: are you using real scalar, $p$-adic,....? If you could write your function $g(x)$ as a series $\sum_{n \geq 0} c_n\binom{x}{n}$ then it is easier to describe a (non-formal) solution, namely $f(x) = \sum_{n \geq 1} c_{n-1}\binom{x}{n}$. Over the $p$-adics these would be expressible also as power series provided they are $p$-adic $C^1$-functions. I suspect you are not considering $p$-adic coefficients. – KConrad Dec 14 '16 at 20:30
• @Sasha, if $f$ is convergent then so is $g$ !! – Loïc Teyssier Dec 15 '16 at 6:13

In general, this question makes sense at a formal level near $\infty$ only, i.e. for power series involving negative powers of $x$. Setting $z:=\frac{1}{x}$, the equation becomes a so-called homological equation $$F(\Delta(z))-F(z)=G(z)$$ where $$\Delta(z):=\frac{z}{1+z}$$ and $F(z):=f(\frac{1}{z})$, $G(z):=g(\frac{1}{z})$.

An obvious obstruction is $G(0)=0$, because $\Delta(0)=0$. Notice that $\lim_{n\to +\infty}\Delta^{\circ n}(z)=0$, so that you can use telescoping sums : $$F(z)=F(0)+\sum_{n=0}^{\infty}G\circ\Delta^{\circ n}(z).$$ This expression is well-defined at a formal level provided $G'(0)=0$ (essentially because $\Delta^{\circ n}(z)=\frac{z}{1+nz}\sim_{n\to\infty}\frac{1}{n}$). Hence the only obstruction is the value of $G(0)=G'(0)=0$.

On the other hand, if you wish to study convergence of $F$ then you need a more detailed and subtle analysis.

• Thank you! if we are talking about formal series, why $\lim_{n \rightarrow \infty} \Delta^n(z)=0$? Naively, if $\Delta^n(z)=\frac{z}{1+nz}=z-nz^2+\dots$, then the limit for small $z$ does not exist. – Sasha Dec 14 '16 at 16:32
• You can't use this expansion for big values of $n$. – Loïc Teyssier Dec 14 '16 at 16:34
• I guess, for any finite $n$ this expansion should work. Then I would like to take the limit in the space of formal series in $z$, is it correct? – Sasha Dec 14 '16 at 16:37
• And another question: why I can not ask my question as it is? It is obvious that there solutions to my equation in the space of formal series of the variable $x$, I just want to describe the space of all possible $g(x)\in \mathbb{C}[[x]]$ – Sasha Dec 14 '16 at 16:43
• No, it is not obvious, since for general formal power series $f(x)$ at $0$ the object $f(x+1)$ does not make sense (e.g. when the radius of convergence of $f$ is less than $1$, as pointed out earlier), as is the case when $g$ is divergent. If you give additional conditions on $g$ (for instance, $g$ polynomial) then your question makes sense globally indeed provided you can prove the object $f$ is, say, entire. But as Pietro noticed elsewhere, since $f$ is far from being unique, the global problem is "difficult". – Loïc Teyssier Dec 14 '16 at 18:17

The equation $f(x+1)-f(x)=g(x)$ can be viewed as a "discrete derivative", hence a solution $f(x)$ can not be expected to be unique.

\begin{align} f(x+1)-f(x)&=\sum_{j\geq0}f_j\sum_{k=0}^j\binom{j}kx^k-\sum_{k\geq0}f_kx^k \\ &=\sum_{k\geq0}x^k\sum_{j\geq k}\binom{j}kf_j-\sum_{k\geq0}x^kf_k=\sum_{k\geq0}x^kg_k. \end{align} Equating coefficients, you find $$g_k=\sum_{j>k}\binom{j}kf_j.$$ When can be inverted to solve for the $f_j$'s? This is possible, for instance, if $g(x)$ is a polynomial.

The matrix involved is upper diagonal $$M_{k,j}=\binom{j}k \qquad k\geq0, \,\,\,j\geq1.$$

• Thank you! But can it really be inverted? I mean, is $f(x)$ unique for a given $g(x)$? – Sasha Dec 14 '16 at 16:04
• As pointed out by Pietro, this computation does not make sense at a formal level ! It may happen that the sum giving $g_k$ is divergent, hence it may not make sense to "invert" these relations. – Loïc Teyssier Dec 14 '16 at 16:12
• Of course, provided that the series involved are convergent. – T. Amdeberhan Dec 14 '16 at 16:14
• But this is exactly what I want to know. What are the restrictions on the coefficients of $g$ for which the coefficients of $f$ do exist. – Sasha Dec 14 '16 at 16:16
• As to the first comment about uniqueness: note that you can add to f(x) any 1-periodic function (which could be an entire function, like $\sin(2\pi x)$). So you do not have uniqueness, unless within a suitable space: for instance, functions vanishing at $+\infty$ . – Pietro Majer Dec 14 '16 at 18:03

Look at Ramanujan Summation, also called indefinite summation. Ramanujan extended The Euler Mclaurin summation method using Bernoulli numbers and a whole stack of ideas. This is a well studied subject. In general, if your $g$ is defined in the right half plane and satisfies for $z = x + iy$ $$|g(z)| < C e^{\rho|x| + \kappa|y|}$$

where $\kappa < \pi$ and $\rho$ is arbitrary, then a unique solution exists, where $f(0) = 0$ and $f(z+1) - f(z) = g(z)$. Ramanujan's formula is rather simple

$$f(z) = C + \int_0^zg(t)\,dt + \frac{1}{2}g(z) + \sum_{n=1}^\infty \dfrac{B_{2k}}{2k!}g^{(2k-1)}(z)$$

where $C$ is a constant making $f(0) =0$ and $B_{2k}$ are the bernoulli numbers. Since this is a linear operator on $g$ it is common to write

$$\sum_z g = f$$ $$\sum_{j=1}^z g(j) = f(z)$$ $$\sum_1^z g(p)\Delta p = f(z)$$

where each draws the similarity between it and the integral.

I can give you a formula for the more restrictive case $\kappa < \pi/2$, which is a modification of Ramanujan's method.

$$f(z) = \frac{1}{\Gamma(1-z)}\Big{(}\sum_{n=0}^\infty \sum_{j=1}^{n+1}g(j)\frac{(-1)^n}{n!(n+1-z)} + \int_1^\infty\big{(}\sum_{n=0}^\infty \sum_{j=1}^{n+1}g(j)\frac{(-w)^n}{n!}\big{)}w^{-z}\,dw\Big{)}$$

which follows by Ramanujan's master theorem. All in all the subject has four names: Indefinite summation, continuum sums, Ramanujan summation, Euler-Mclaurin summation. I can't remember the names of the books, but there are some books on the calculus of finite differences that deal with this subject.

The idea goes hand in hand with Newton series as well, where in such a case it is rather trivial to produce an indefinite sum if the function is expanded in a Newton series. I.e: if $$g(z) = \sum_{n=0}^\infty a_n\dbinom{z}{n}$$ In this case it's much easier to work with $g$ bounded in the right half plane, so it's more restrictive.

Also, if $g(z)$ has nice decay properties we can always take the wondrous classical equation

$$f(z) = \sum_{k=0}^\infty g(z-k) - g(-k)$$ or

$$f(z) = \sum_{k=0}^\infty g(z+k) - g(k)$$

which was Ramanujan's motivation, but these are more volatile.

• Thank you! Ramanujan's formula is really transparent - just an action of the operator $\frac{1}{e^{\frac{d}{dz}}-1}$. But the restriction "defined in the right half plane" is too strong - I guess, there should be some formal series $g$, which are not defined in the right half plane, but give the solution. – Sasha Dec 14 '16 at 21:19
• I have read formal power series solutions, these are a little tougher to get through--these are just actions on the power series of $g$ about zero, but then you're bogged down by loads of convergence problems. Necessarily the only way it makes sense is if the power series converges in a disk of radius > 1. Personally, I still believe it is a solution, just that the functional equation cannot be evaluated, but it still satisfies the equation $f(z+1) = g(z) + f(z)$ (analytically continuing f). However, if you take the newton series, you get a really simple formula for the indefinite sum. – user78249 Dec 14 '16 at 21:28
• $f$ should be the power series convergent in a disk of radius at least 1, that's fine, but what can we say about $g$? – Sasha Dec 14 '16 at 21:42
• The best formal power series solution is almost trivial from Ramanujan's formula. Simply formally solve for the Taylor coefficients about zero. You'll get a very ugly mess of infinite series, but it's valid. But then you're stuck proving that its convergent which is where I haven't a clue what to do. You would need a restriction on $g$ which proves its convergent. I can't imagine what that would be though, other than Ramanujan's criterion. – user78249 Dec 14 '16 at 23:26
• Nevermind that above comment. I just realized. a big trouble with Ramanujan's expression is that if the infinite series converges then $g$'s derivatives have nice decay at zero, which in turn forces $g$ to be entire, or defined on a much larger area. I think that this method will fail necessarily, and if it converges, you probably have a good chance that $g$ is defined on a much larger domain. – user78249 Dec 15 '16 at 0:07