RO-TST 1988 Problem 8

The positive integer $n$ is given and for all positive integers $k$ , $1\leq k\leq n$ , denote by $a_{kn}$ the number of all ordered sequences $(i_1,i_2,\ldots,i_k)$ of positive integers which verify the following two conditions:

a) $1\leq i_1<i_2< \cdots i_k \leq n$ ;

b) $i_{r+1}-i_r \equiv 1 \pmod 2$ , for all $r \in\{1,2,\ldots,k-1\}$ .

Compute the number $a(n) = \sum\limits_{k=1}^n a_{kn}$ .

Ioan Tomescu