Докажите, что при n = 3002 сумма биномиальных коэффициентов с шагом 6, то есть дает остаток 1 при делении на 3. Где — количество способов выбрать из n предметов k, что составляет если и 0 в остальных случаях.
Решение.
Легко проверить, что
следовательно, даёт такой же остаток при делении на 3, что и Таким образом,
даёт такой же остаток при делении на 3, что и
(здесь отброшены два крайних слагаемых, равные 0). Обозначим эту сумму за Аналогично переходим к
Применив эту процедуру ещё 998 раз, получаем, что формула из условия даёт такой же остаток при делении на 3, что и
дает остаток 1 при делении на 3. Где 
— количество способов выбрать из n предметов k, что составляет 
если 
и 0 в остальных случаях.
даёт такой же остаток при делении на 3, что и 
Таким образом, 
Аналогично переходим к 
