Число последовательностей.

Дана последовательность a₁,b₁,a₂,b₂,…,a_k,b_k, состоящая из 0 и 1. Пусть N – количество чисел i от 1 до k таких, что a_i=0 и b_i=1. Докажите, что число последовательностей указанного вида, для которых N нечетно, находится по формуле 2^(2k-1)-2^(k-1).

• Решение

Решение

Применим метод математической индукции по параметру k. При k=1 формула очевидна. Допустим формула верна для значения k-1. Искомое число равно числу последовательностей a₁,b₁,a₂,b₂,…,a_k-1,b_k-1, в которых количество i=1,2,…,k-1 таких, что a_i=0 и b_i=0 четно (в этом случае пара (a_k,b_k ) может быть только (0,1)) плюс количество последовательностей a₁,b₁,a₂,b₂,…,a_k-1,b_k-1, в которых количество чисел i=1,2,…,k-1 таких, что a_i=0 и b_i=1 нечетно, умноженному на 3 (так как пара (a_k,b_k ) может быть любой из пар (0,0),(1,0),(1,1)). В итоге по предположению индукции нужное число последовательностей будет удовлетворять равенству (2^2(k-1) -(2^(2(k-1)-1)-2^(k-2) ))+3(2^(2(k-1)-1)-2^(k-2) )=2^(2k-1)-2^k.