# 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. –  EMS 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