IMO 1973 — Shortlisted problems Question 8

(ROM 1) Prove that there are exactly $\binom{k}{[k/2]}$ arrays $a_1,a_2,\ldots,a_{k+1}$ of nonnegative integers such that $a_1=0$ and $|a_i-a_{i+1}|=1$ for $i=1,2,\ldots,k$.