Proof:
Let T(k) be the number of 1's in the frontsegment of length k. Then f(k) = T(k) - T(k-1).Define T'(k) = [(k+1)/
] and f'(k) = T'(k) - T'(k-1).We will show that T = T' (and thus that f = f').
f'(k) = T'(k) - T'(k-1) = [(k+1)/
] - [k/].f'(k) = 1 only if [k/
] < [(k+1)/]or if there is an integer m so, that k/
< m < (k+1)/, i.e. if k < m < k+1,or if k can be represented as [m
].Now we will proof that T = T' (so that f = f'):
By induction. T(1) = 1 = [2/
] = T'(1), so T(k) = T'(k) for k≤F2, the second row.Suppose T(k) = T'(k) for k≤Fn, the n-th row (for certain n>1).
Now we will show that f(k) = f'(k) (and thus that T(k) = T'(k)) for k≤Fn+1, the n+1-st row.
Regard the k-th character in that n-th row. The k-1 characters from that row are transformed into k-1+T(k-1) characters in the n+1-st row.
Now regard the parents of the k-th character. f(k + T(k-1)) = 1 both if f(k) = 0 and if f(k) = 1, and f(k + 1 + T(k-1)) = 0 if f(k) = 1.
The induction is complete if we are able to show that f(k + T(k-1)) = f'(k + T(k-1)) and that, in case f(k) = 1,
f(k + 1 + T(k-1)) = f'(k + 1 + T(k-1)).
k + T(k-1) = k + T'(k-1) = k + [k/
] = k + [k( - 1)] = [k] (*)f'(k + T(k-1)) = f'([k
]) = 1 = f(k + T(k-1)).We still have to show that f(k + 1 + T(k-1)) = f'(k + 1 + T(k-1)) in case f(k) = 1.
When f(k) = 1, then 1 + T(k-1) = T(k) and so (see (*))
[k
] + 1 = k + 1 + T(k-1) = k + T(k) = k + T'(k) = k + [(k+1)/] = k + [(k+1)( - 1)] = [(k+1)] - 1.If f'(k + 1 + T(k-1)) = 1, then there is an integer m such, that [k
] + 1 = [m] = [(k+1)] - 1.So m > k and m < k+1. Impossible, thus f'(k + 1 + T(k-1)) = 0 = f(k + 1 + T(k-1)).
This completes the proof.