## Friday, January 28, 2011

### Discrete connections (part IV)

Before dealing with the major results, let us consider the following:
Intermediate recurrence
[;\frac{n}{2}<k<\frac{2\cdot n}{3} \Rightarrow;]
[;\tau_1(n,k)=k+\tau_1(n-k,2\cdot k - n);]
Its proof consists in applying the outer row recurrence first for n and k and then for k and n-k.
The first major result consists, as the above one, from two formula iterations:
Asymptotic expansion
a)
[;\frac{F_{2 \cdot m}}{F_{2 \cdot m + 1}} \cdot n <k< \frac{F_{2 \cdot m - 1}}{F_{2 \cdot m}} \cdot n \Rightarrow;]
[;\tau_1(n,k) = (\sum_{i=1}^{2 \cdot m - 1}(-1)^{i+1} \cdot F_{i}) \cdot n + (\sum_{j=2}^{2\cdot m} (-1)^{j+1} \cdot F_{j}) \cdot k +;]
[;\tau_1(F_{2 \cdot m-1} \cdot k - F_{2\cdot m - 2} \cdot n, F_{2 \cdot m - 1} \cdot n - F_{2 \cdot m} \cdot k);]
b)
[;\frac{F_{2 \cdot m}}{F_{2 \cdot m + 1}} \cdot n <k< \frac{F_{2 \cdot m + 1}}{F_{2 \cdot m + 2}} \cdot n \Rightarrow;]
[;\tau_1(n,k) = (\sum_{i=1}^{2 \cdot m }(-1)^{i+1} \cdot F_{i}) \cdot n + (\sum_{j=2}^{2\cdot m + 1} (-1)^{j+1} \cdot F_{j}) \cdot k +;]
[;\tau_1(F_{2 \cdot m - 1} \cdot n - F_{2 \cdot m} \cdot k, F_{2 \cdot m+1} \cdot k - F_{2\cdot m } \cdot n);]
where
[;F_{1} = F_{2}=1;]
[;F_{m+2}=F_{m+1} + F_{m};]
stand for the terms of the Fibonacci sequence, and by natural convention:
[;F_{0} = 0;]
The proof follows by mathematical induction, the base case being ensured by the outer row recurrence  (for a)) and the intermediate recurrence (for b)). For the inductive step we will suppose that a) and b) hold for n arbitrarily fixed m. Through the outer row recurrence results that a) holds for m+1 as well and in a similar fashion b) holds for m+1 as well, thus concluding the inductive reasoning.
Since from the previous part we have that:
[;\frac{\tau_2(n)}{n} < 1;]
and for a conveniently chosen m, via the asymptotic expansion we have that:
[;\frac{\tau_2(n)}{n} > \frac{F_{2\cdot m + 1} - 1}{ F_{2 \cdot m + 1}};]
we can now state that:
[;(\frac{\tau_2(n)}{n})_{n \ge 1} \rightarrow 1;]
There is also another gain (from the asymptotic expansion), from the perspective of the positional peak: if we squeeze k such that the fraction n/k becomes closer and closer to the golden ratio we get values of the euclidean summation pretty close to n. Alas we can only conjecture for now that:
[;(\frac{\tau_3(n)}{n})_{n \ge 1} \rightarrow \phi;]
where:
[;\phi = \frac{1}{\varphi} \approx 0.618;]
is called the golden ratio conjugate.

Next: Fractal candidate building blocks