KMO 2016 Problem 4

For a positive integer $n$ , $S_n$ is the set of positive integer $n$ -tuples $(a_1,a_2, \cdots ,a_n)$ which satisfies the following.

(i). $a_1=1$ .

(ii). $a_{i+1} \le a_i+1$ .

For $k \le n$ , define $N_k$ as the number of $n$ -tuples $(a_1, a_2, \cdots a_n) \in S_n$ such that $a_k=1, a_{k+1}=2$ .

Find the sum $N_1 + N_2+ \cdots N_{k-1}$ .