Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
matematykadyskretna.niezbędnikdlainformatyków
Rozdział3
Dowódprzezindukcjęmatematyczną
Ilewynosisumanpierwszychpotęg2?
Jakzwykle,pierwszymkrokiemprowadzącymdorozwiązaniapo-
dobnegoproblemujestupewnieniesię,żerozumiesię,oczymmowa.
Czymjestpotęga2?Jesttoliczbatakajak23,czyli8,którajestrówna
dwójcepodniesionejdojakiejścałkowitejpotęgi.Nodobrze,wtakim
razieczymjestn?Otymniemaanisłowa!Wtakimrazienmoże
byćczymkolwiek,dlaczegoresztapytaniamasens.Wpytaniumowa
ododawaniudosiebierzeczy,anjestliczbąrzeczy,któredosiebie
dodajemy.Takwięcnn”musibyćzmiennąreprezentującąliczbęcał-
kowitą,jaknp.10.Nakońcumusimysięupewnić,żerozumiemy,co
toznaczynnpierwszych”potęg2.Czynpierwsza”potęga2jestrówna
2
0
,czy2
1
,amożejesttojeszczecoinnego?Winformatyceczęsto
liczeniezaczynasięod0.
Gdybyśmyznaliwartośćn,moglibyśmypoprostuobliczyćodpo-
wiedź.Naprzykładdlan=10pytamyowartość
20+21+22+23+24+25+26+27+28+29
=1+2+4+8+16+32+64+128+256+512,
która,jaksięokazuje,wynosi1023.
Aleniechcemytylkoiwyłącznieodpowiedzidlaprzypadkun=10.
Pytaniezostałozadanezużyciemzmiennejn,więcoczekiwanajest
odpowiedźodnoszącasięwjakiśsposóbdon.Adokładniej,poszu-
kujemywartościwyrażenia
20+21+22+...+2n11.
Każdyelementtakiejsumynazywamyskładnikiem(wyrazem)-
zatemwpowyższejsumieskładnikamisą20,21,…,2n-1.Zauważmy,
żeostatnimskładnikiemjest2n-1,nie2n.Zaczęliśmyliczyćod0,więc
pierwszenpotęg2to2topotęgi0,1,2,…in-1,aostatnim
znskładnikówjest2n-1.
28
