Wednesday, January 26, 2011

Discrete connections (part III)


For the positional peak, its boundaries are straightforward (definition, inner row  recurrence and lower boundary):
[; \frac{n}{2}<\tau_3(n)<n \; \forall \; n \ge n_{\tau_3};]

For the peak, it's a two step argument. For the lower bound we consider two cases: n odd and respectively n even. For every such case we take a conveniently chosen pair, compute the euclidean summation and truncate it up to a suitable value:
 [; n = 2 \cdot k + 1 \Rightarrow ;]
[; \tau_1(n,k+2) = n-(k+2) + \tau_1(k+2, k-1) \Rightarrow ;]
[; \tau_1(n,k+2) \ge k-1 + 3= k+2 > k + \frac{1}{2} = \frac{n}{2} ;]
[; n=2\cdot k \Rightarrow ;]
[;\tau_1(n,k+1) = n-(k+1) + \tau_1(k+1, k-1) \Rightarrow ;]
[; \tau_1(n,k+1) \ge k-1 + 2= k+1 > k = \frac{n}{2};]

Here also the inequality holds from a rank on, due to the approximations used.
For the upper bound, our reasoning will follow the rules of the mathematical induction:
 base case
[;\tau_1(1,0)=0<1;]
inductive step (n arbitrarily fixed)
[;\tau_1(k,r)<r \; \forall \; k,r \; such \; that \; n>k>r \Rightarrow ;]
[;\forall \; k<n \Rightarrow \exists \; q,r \; such \; that \;q \ge 1, k>r, n=q\cdot k + r  \Rightarrow ;]
[;\tau_1(n,k) = r + \tau_1(k,r) < r + k \le r + q \cdot k = n;]
thus concluding our reasoning.
We get in conclusion:
[; \frac{n}{2}<\tau_2(n)<n \; \forall \; n \ge n_{\tau_2};]

Next: Asymptotic behaviors of peak and positional peak.


No comments:

Post a Comment