MathDB

number sections of a number with only 0s and 1s, total sum wanted

Source: Czech and Slovak Olympiad 2017, National Round, III A p4

February 2, 2020

combinatoricsSumProbabilistic Method

Problem Statement

For each sequence of

n

zeros and

n

units, we assign a number that is a number sections of the same digits in it. (For example, sequence

00111001

has

4

such sections

00, 111,00, 1

.) For a given

n

we sum up all the numbers assigned to each such sequence. Prove that the sum total is equal to

(n+1){2n \choose n}