Claude Shannon, well-known result in finite differences

[jonw]

Searching google I found the exact question I wish to pose, David
Grieve earlier asked:

In his famous 1948 paper entitled "A Mathematical Theory of
Communication",
at the bottom of page 3, Shannon asserts...

Suppose all sequences of the symbols S1,...,Sn are allowed and these
symbols
have durations t1,...,tn. What is the channel capacity? If N(t)
represents
the number of sequences of duration t we have

N(t) = N(t - t1) + N(t-t2) + ... + N(t-tn)

The total number is equal to the sum of the numbers of sequences
ending in
S1,S2,...,Sn and these are N(t-t1), N(t-t2),...,N(t-tn),
respectively.
According to a well-known result in finite differences, N(t) is then
asymptotic for large t to (X0)^t where X0 is the largest real solution
of
the
characteristic equation:

X^-t1 + X^-t2 + ... + X^-tn = 1

My question is... can anyone point me to an explanation of the
supposedly
"well-known" result in finite differences that Shannon is making use
of
here????

I tried to understand the reply messages with no luck. Could someone
please simply explain what is the "well-known" result in finite
differences so that I could research this subject further?

[Larry Hammick]

"jonw"

He's got a function N satisfying a linear finite difference equation with
constant coefficients. The asymptotic growth of any solution is fairly well
known. In different notation, say we have this simple type:
a_k f(n+k) + a_(k-1) f(n+k-1) + ... + a_0 f(n) = 0
for all n. Say the roots of this equation
a_k x^k + ... + a_0 x^0
(called the characteristic equation of the given finite dif. equation) are
distinct b_1 ... b_k. Then the general solution f is
f(n) = c_1 (b_1)^n + ... + c_k (b_k)^n
where the c_i are constants. If the root b_i of greatest absolute value is a
real and positive, then the term c_i (b_i)^n swamps all the others for big
n.
The case of multiple zeros is also manageable. But if a complex or negative
root has the biggest absolute value, the solution cannot be monotic and
real, as it is by hypothesis in Shannon's case. Also, in his case, the
exponents in
a_k x^k + ... + a_0 x^0
are weighted by those t_i thingees, but it makes little difference.
I think you can figure it out from there.
LH