# Recurrence relations on a continuous domain

While attempting to read Shannon's paper I came across the following (p. 3): suppose $N\colon \mathbb{R} \to \mathbb{R}$ is a function, which for some fixed (given) set of values $t_1, t_2, \dots, t_n$ satisfies $$N(t) = N(t-t_1) + N(t-t_2) + \dots + N(t-t_n). \quad \quad \quad (1)$$

Then, he says, "according to a well-known result in finite differences", $N(t)$ is asymptotic for large $t$ to $X_0^t$ where $X_0$ is the largest real solution of the characteristic equation $$X^{-t_1} + X^{-t_2} + \dots + X^{-t_n} = 1. \quad \quad \quad (2)$$

My question: what is this well-known theory, and where can I read about it? (If the proof is short enough to outline here in the space of a math.SE answer that would be great too, of course!) What sort of an equation is $(2)$, anyway?

[Some fuzzy attempts follow.]

I could not prove this, but I can non-rigorously find the result plausible: for instance, if we guess that $N(t)$ is of the form $X^t$ (or even $c X^t$) for some $X$, then plugging in $N(t) = c X^t$ into the equation $(1)$ gives $$cX^{t} = cX^{t-t_1} + cX^{t-t_2} + \dots + cX^{t-t_n}$$ so dividing by $cX^t$ we get equation $(2)$, $$1 = X^{-t_1} + X^{-t_2} + \dots + X^{-t_n}$$ And of course for any solution $X$ of the above equation and for any constant $c$, we can take $N(t) = cX^t$. Also linear combinations of solutions to $(1)$ are also solutions, so $N(t)$ could even be of the form $$N(t) = c_0X_0^t + c_1X_1^t + \dots$$ in which asymptotically only the largest solution $X_0$ matters. That is, $$\lim_{t\to\infty}\frac{N(t)}{X_0^t} = \lim_{t\to\infty}\left(c_0 + \frac{c_1X_1^t}{X_0^t} + \dots \right)= c_0.$$

Now if were working with recurrence relations over the integers — $N\colon \mathbb{Z}\to\mathbb{R}$, say, with all the $t_i$ being integers, especially if they are integers $1$ to $n$ — then I guess we could further say that we have found an $n$-dimensional space of solutions (here $n$ being the number of solutions to equation $(2)$), and the solution space also is of dimension $n$ (it has $n$ "degrees of freedom" because the first $n$ values determine the sequence — all this needs to be made more rigorous and to consider more general $t_i$), and therefore these must be all the solutions. That would complete the "proof".

But in this real-number case I'm completely clueless how one would prove a thing like this, and everything I wrote above may be entirely the wrong tack to pursue.

• Immediately after clicking on "Ask question", the phrase "generating functions" pops into my head, but because they don't directly apply here and because nothing else pops along with it, I'm still clueless. :-) – ShreevatsaR Mar 15 '12 at 19:57
• It's not clear what you mean. Are you talking about difference equations, and their well-understood analog with differential equations? I mean, for that you can Google 'recurrence relation' and most sources will point you towards the mathematical theory. I would say that generating functions definitely apply to this field of study. – ely Mar 15 '12 at 20:23
• @EMS: Your Google-searching skills may be better than mine, but when I searched for either "difference equations" or "recurrence relations", all the references I got were for the discrete case (i.e., where $N\colon \mathbb{Z} \to \mathbb{R}$) — I couldn't find any references that would apply to equations like, say, $N(t) = N(t-1.23456) + N(t-\sqrt{2}) + N(t-\pi)$. Hence my question about "continuous domain" — if you know or can find applicable references I'd be most grateful! This looks like something that must be studied and be easy to find, but I have failed so far. :-( – ShreevatsaR Mar 16 '12 at 1:58

This assertion is certainly false as stated. For one thing, you certainly need some "regularity" assumptions, otherwise e.g. there are solutions of $N(t) = N(t+1)$ that are unbounded on each interval of length 1, and so don't satisfy any asymptotics. But even "nice" solutions might involve non-real solutions of the characteristic equation. For example, $N(t) = c^t \sin(\pi t)$ satisfies $N(t) = N(t-1) + N(t+2)$ where $c$ is the real root of $c^3 - c - 1$, approximately $1.324717957$, and this is certainly not asymptotic to any $X^t$.

• Thanks for this observation (+1). The natural follow-up question of course, and which I should have asked in the first place, is what unstated regularity assumptions make it true — if at all it is true. For instance in the setting of the paper, it can be argued that $N(t)$ is positive and increasing, which rules out the above examples. (By reading too much one may even say $N(t)$ only takes integer inputs and has integer values, which would make this the same old familiar recurrence relation setting and the question pointless, but that would be disappointing. :-) ) – ShreevatsaR Mar 16 '12 at 2:10
• On looking again at the paper, I'm beginning to suspect that he only meant integer t, so the entire premise of my question is flawed. I'm accepting this answer; I'll eventually delete the question. – ShreevatsaR Mar 18 '12 at 5:26

Let's suppose without losing generality that $0 < t_1 < \dots < t_n$. Also I think Shannon supposes $n \geqslant 2$.

If $t_1, \dots, t_n$ are integer or rational numbers then as was stated this is indeed "a well-known result in finite differences". Even if we're looking for functions $N: \Bbb R \to \Bbb R$ on a continous domain, all difference is in the boundary conditions. When we're looking for such a function we must suppose unknown constants depend on $t$ too ($c_i = c_i (t)$). We're finding them from boundary condition $N(t) = N_0(t)$ on segment $0 \leqslant t < t_n$, where $N_0(t)$ is a given function. I think Shannon supposes $N_0(t) = const$ or even $N_0(t) = 0$. That's why all solutions will be bounded on finite segments.

Also, I want to mention that 1) equation (2) may have complex root $X_j$ that corresponds to partial solution of the form $|X_j|^t (a_j \cos(\varphi t) + b_j \sin (\varphi t))$ where $\varphi = \arg X_j$ and 2) equation (2) may have multiple root $X_j$ with multiplicity $m$, $m > 1$ that will correspond to a solution $P^{(m)}_j(t) X_j^t$ where $P^{(m)}_j(t)$ is an unknown polynom of the degree lower than $m$ (or $|X_j|^t (P^{(m)}_j(t) \cos(\varphi t) + Q^{(m)}_j \sin (\varphi t))$ in case of complex multiple root).

Good news equation (2) has a simple real root $X_0$, $X_0 > 1$ that is greater than the absolute value of it's any other root and hence $N(t)$ is really asymptotic to $X_0^t$.

The most interesting case is when $t_1, \dots, t_n$ are arbitrary real numbers. Even if we're looking for function $N: \Bbb Z \to \Bbb R$ on an integer domain the characteristic equation becomes a transcendental equation that in my humble opinion might have infinite number of complex roots and hence the general solution must be represented as an infinite series or an entire function. The same reasoning should hold in this case but unfortunatelly I don't know how to make it all rigid and can't find almost anything on this topic on my own. This isn't looking as "a well-known result in finite differences" at all in this case.

All I have found on the topic is the book "Calculus of finite differences" by A.O.Gelfond where in the paragraph 7, part V the author discusses the problem of solving linear differential equations with fixed coefficients of the infinite order that in all likelihood has some relationship to the described problem.