Citat:
Ursprungligen postat av
Stagflation
Jag förstår.
Hur många binära tal mindre än 256 börjar och/eller slutar med 2 ettor?
Börja med att notera att 256 = 2^8, detta innebär att det är som mest 8 siffriga binära tal vi söker. Låt A_n vara mängden av de tal som uppfyller att de slutar eller börjar med två ettor. Vi kan börja med att notera att
A_1 = Ø, A_2 = {11}, A_3 = {110, 111}, A_4 = {1011, 1100, 1101, 1110, 1111}
Nu kan vi skapa mängden A_5 genom att för varje tal i A_4 placera en nolla och etta på tredje positionen från höger. Så man får alltså 2 tal från varje tal i A_4. Därför är alltså |A_5| = 2|A_4|.
Samma resonemang leder till att |A_{n + 1}| = 2|A_n|, n ≥ 4. Så nu söker vi alltså
|A_1| + |A_2| + |A_3| + |A_4| + |A_5| + |A_6| + |A_7| + |A_8| = 0 + 1 + 2 + 5 + 10 + 20 + 40 + 80 = 158.