Задача
COM-B2-M09-P007 Строки с четным числом единиц
#7
★★★☆☆ Уровень 3 из 5
Докажите, что при \(n\ge 1\) число двоичных строк длины \(n\) с четным числом единиц равно \(2^{n-1}\).
Сумма четных биномиальных коэффициентов получается из \((1+1)^n\) и \((1-1)^n\).
Число строк с \(k\) единицами равно \(\binom{n}{k}\). Поэтому нужно найти сумму коэффициентов при четных степенях в \((1+x)^n\). Она равна \(\frac{(1+1)^n+(1-1)^n}{2}\). При \(n\ge 1\) получаем \(\frac{2^n+0}{2}=2^{n-1}\).
Первый аккуратный фильтр по четности.