MathDB

Number of terms of non-negative sequence

Source:

September 22, 2010

combinatoricscountingSequencesbinomial coefficientsIMO Shortlist

Problem Statement

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.