Dresden Algorithmics Channel: Module 18

In [1] is shown:
The linear difference equation [2,3,4,5,6]

(1)

where

(2)

(3)

and the starting terms are

(4)

approaches for a solution, which turns out to be a fraction

(5)

where A and B are determined by
(6)

thus
(7)

(8)

The numerator is a linear function of the starting terms , but also of the coefficients ;
The denominator is independend of the starting values and a linear function of the coefficients .
Since the coefficients form a complete system (eq. (2)) of reciprocals of powers of two (eq. (3)), the linear difference equation (1) can be rewritten as a Huffman-nested mean expression [1].

As an example, the term
(9)

can be rewritten as a mean expression
(10)

where
(11)

Thus the computation of can be considered as an iterated structured process of mean value computations (for details see [1]).

For our current example, we find that
(12)

In contrast to this, the difference equation
(1)

with the coefficients
(13)

and the starting terms

(see [7]) (4)

exhibits a completely different behaviour. Here we find that
(14)

However, for the difference quotient of approaches an irrational number:

(15)

independent of the starting terms in eq. (4) (excluding the trivial case ).

This computation of a root can be extended to arbitrary numbers :
For , the difference equation
(16)

yields in analogy to eq. (15)
(17)

Task 18.1

Give a derivation of the equations (5) and (6).

Task 18.2

Develop a simple algorithm (A1) to rearrange the right side of the difference equation (1) into a Huffman-nested mean expression under the conditions given by eq. (2) and eq. (3) (ref. to the transformation of eq. (9) into eq. (10), and [8,9]).

Task 18.3

By the use of experiments, investigate the convergence behaviour of the difference equation (9) for a range of representative starting terms, and discuss the results.