Решение
Применим метод математической индукции по параметру k. При k=1 формула очевидна. Допустим формула верна для значения k-1. Искомое число равно числу последовательностей a1,b1,a2,b2,…,ak-1,bk-1, в которых количество i=1,2,…,k-1 таких, что ai=0 и bi=0 четно (в этом случае пара (ak,bk ) может быть только (0,1)) плюс количество последовательностей a1,b1,a2,b2,…,ak-1,bk-1, в которых количество чисел i=1,2,…,k-1 таких, что ai=0 и bi=1 нечетно, умноженному на 3 (так как пара (ak,bk ) может быть любой из пар (0,0),(1,0),(1,1)). В итоге по предположению индукции нужное число последовательностей будет удовлетворять равенству (22(k-1) -(2(2(k-1)-1)-2(k-2) ))+3(2(2(k-1)-1)-2(k-2) )=2(2k-1)-2k.