IZhO олимпиада по математике 2015 года | Казахстанские олимпиады

Обозначим через $A_n$ множество разбиений последовательности $1, 2, \dots, n$ на несколько подпоследовательностей, в каждой из которых любые два соседних члена имеют разную чётность, а через $B_n$ — множество разбиений последовательности $1, 2, \dots, n$ на несколько подпоследовательностей, в каждой из которых все члены имеют одинаковую чётность (например, разбиение $\{(1, 4, 5, 8), (2, 3), (6, 9), (7)\}$ является элементом $A_9$, а разбиение $\{(1, 3, 5), (2, 4), (6)\}$ является элементом $B_6$).
Докажите, что при каждом натуральном $n$ множества $A_n$ и $B_{n+1}$ содержат одинаковое количество элементов.