Дискретная математика

108 a+b=-\.a+l.b = C4a+C\b=i.Cy~'b'. ЫО Пусть равенство (4.6) истинно для п-к, к>1. Докажем, что тогда (4.6) истинно и для к+1. Имеем; (a+bf"'=(a+bf(a+b)=(a+bfa+(a+bfb= = j:Cla'-"b''-' + tc^a'b^^'-' ЫО i=0 + +b''*'= ЫО i=l +Ci)+b''^'=a'''-^+ZCl^ja'b^-''-' = Ы] ' ' Cl , k+} k+] . I , • = I C' „a-b'-'-'. i=0 Теорема доказана. Из равенства (4.6) легко следует: если а=1, 6=-1, то =0, если 1=0 а=1,Ь=1,то t c ' „ =2 " . i=0 Из последнего соотношения легко получить число всевозможных подмножеств конечного множества А. Действительно, пусть п(А)=п. Очевидно: - число одноэлементных подмножеств множества А равно числу C,j; - число двухэлементных подмножеств множества А равно числу С,'^; • '' > - число к элементных (\<к £ п) подмножеств множества А равно числу & Учитывая, что есть еще пустое подмножество (содержащее О элементов), получим, что число всевозможных подмножеств множества А равно: n p j ) - c l + c l + c l +...+С' =i ;c;. =2", /=о Итак, п(2')= 2".