Задача про покраску полоски

Как можно к следующей функции привести явную формулу:
g(n) = \sum_{i=0}^{n-1}C_{2n}^{2i}2^{2n - (2i+1)}
Эта функция является ответом к следующей задаче:
Сколькими способами можно покрасить полоску 1x2n в красный, синий, зеленый так, чтобы количества красных и синих были нечетными, а количество зеленых четно (здесь я полагаю что зеленых может быть и 0)

Для начала, так как C_n^i=C_n^{n-i}, запишем изначальную сумму как \sum_{i=1}^{n}C_{2n}^{2i}2^{2i-1}
Воспользуемся следующим тождеством (упомянутым в этой теме, оно для самостоятельного доказательства):

C_{n}^k=C_{n-1}^k+C_{n-1}^{k-1}

Заменим все С-шки, кроме последней, тогда получится Бином Ньютона, но будет не доставать C_{2n-1}^0 2^0 и степеней двойки некоторым слагаемым:

C_{2n-1}^1 2+C_{2n-1}^2 2+C_{2n-1}^3 2^3 + ... + C_{2n-1}^{2n-3} 2^{2n-3} +C_{2n-1}^{2n-2}2^{2n-3}+C_{2n-1}^{2n-1}2^{2n-1}

Тогда надо добавить и отнять \sum_{i=1}^ {n-1} C_{2n-1}^{2i} 2^{2i-1}. Заметим, что похоже на нашу изначальную сумму. А новая сумма будет

3^{2n-1}-1-\sum_{i=1}^ {n-1} C_{2n-1}^{2i} 2^{2i-1}

Если проделать тот же процесс с этой недостающей суммой, получаем аналогичный результат, и функцию теперь можно записать как

3^{2n-1}-3^{2n-2}+\sum_{i=1}^ {n-1} C_{2n-2}^{2i} 2^{2i-1}

Используя эту рекурсию, можем записать всю сумму как

3^{2n-1}-3^{2n-2}+...+3-1=(3-1)(3^{2n-2}+3^{2n-4}+...+1)=
=2 \ (9^{n-1}+9^{n-2}+...+1)=2 \cdot \frac{9^n-1}{9-1} = \frac{9^n-1}{4}
4 симпатии