I have the following problem. Given is a sequence of bits $S=\{0,1\}^T$ and functions
$$A[t]=\sum_{k=1}^{t}S[k]$$ $$B[t]=\sum_{k=1}^{t}A[k]$$
Now for sequence $\{B[0], B[1], \dots, B[T]\}$ I would like to prove the following.
- It contains at most one element equal to $1$
- That the first occurrence of element $1$ (if it exists) has the same index as the first occurrence of element $1$ in $S$.
Thoughts:
For proof $1$ I imagine one could split the problem into two cases. Case 1. If $S$ contains no $1$ then $B$ contains no $1$; And case 2. Either proof by contradiction and assume that for $t_1$ and $t_2>t_1$ that $B[t_1]=B[t_2]$ or prove that $B$ is always increasing $B[t+1]>B[t]$. I am however struggling to formally write down these ideas.
For the second statement perhaps one could also use proof by contradiction?
Any help is greatly appreciated! Thanks
Reversing the order of summation yields $$B[t] =\sum_{k=1}^t \sum_{i=1}^k S[i] =\sum_{i=1}^t \sum_{k=i}^t S[i] =\sum_{i=1}^t S[i] \sum_{k=i}^t 1 =\sum_{i=1}^t S[i] (t-i+1), $$ so \begin{align} B[t+1] &=\sum_{i=1}^{t+1} S[i] (t+1-i+1) \\ &=\sum_{i=1}^t S[i] (t+1-i+1) + S[t+1] \\ &=\sum_{i=1}^t S[i] (t-i+1) + \sum_{i=1}^t S[i] + S[t+1] \\ &= B[t] + \sum_{i=1}^{t+1} S[i] \\ &> B[t] \quad\text{if $\sum_{i=1}^{t+1} S[i] > 0$} \\ \end{align} Also, if $S[1]=S[2]=\dots=S[\bar{t}-1]=0$ and $S[\bar{t}]=1$, then $$B[t]=\sum_{i=1}^t 0 (t-i+1) = 0 \quad \text{for $t < \bar{t}$}$$ and $$B[\bar{t}]=\sum_{i=1}^\bar{t} S[i] (\bar{t}-i+1) = S[\bar{t}] (\bar{t}-\bar{t}+1) = 1.$$