Citat:
Ursprungligen postat av arvid.norstrom
Aha t ex 1*2^3 + 1*2^3 = 2*2^3 = 1*2^4, eller? Förklara gärna vidare

Ja, i det fallet blir "ett styck etta + ett styck etta = ett styck etta". Men om talen inte har någon etta i samma position så kommer gälla att "antal ettor i första talet + antal ettor i andra talet = antal ettor i summan".
Skall försöka förklara 1.8.
Först sätter man a(n) = e_2(n!) = antal faktor 2 i n! och b(n) = antal ettor i binära representationen av n. Enligt 1.7 gäller a(n) + b(n) = n.
Eftersom C(n, k) = n!/(k!(n-k)!) gäller att
e_2(C(n, k)) = e_2(n!/(k!(n-k)!)) = e_2(n!) - e_2(k!) - e_2((n-k)!)
= a(n) - a(k) - a(n-k) = (n - b(n)) - (k - b(k)) - ((n-k) - b(n-k))
= b(k) + b(n-k) - b(n).
Den "svåra" biten (som dessutom egentligen skulle behöva mer motivering än boken ger):
Sista ledet ovan är 0 om och endast om k och n-k inte har någon etta i samma position i sina binära representationer, dvs omm B(k) ∩ B(n-k) = ∅, vilket är ekvivalent med B(k) ⊆ B(k+(n-k)) = B(n).
Om b(k) + b(n-k) - b(n) = 0 så innehåller C(n, k) ingen faktor 2 och är därmed udda. Annars är C(n, k) jämnt och alltså b(k) + b(n-k) - b(n) ≥ 0.
Vi har alltså visat att C(n, k) är udda omm b(k) + b(n-k) - b(n) = 0 omm B(k) ⊆ B(n).