Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky MB101 ­ 1. demonstrovaná cvičení Důkazy matematických tvrzení Masarykova univerzita Fakulta informatiky 17.9. 2007 Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Plán přednášky 1 Typy matematických důkazů Matematická indukce Důkaz sporem 2 Sumy 3 Počítání s procenty 4 Zlehka kombinatoriky Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Princip matematické indukce Mějme tvrzení T(n) závislé na přirozeném číslu n. Pokud dokážeme 1 Pro nějaké přirozené k0 platí tvrzení T(k0), 2 Pro libovolné přirozené k k0 platí implikace T(k) T(k + 1), pak tvrzení T(n) platí pro libovolné přirozené n k0. Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Princip matematické indukce Mějme tvrzení T(n) závislé na přirozeném číslu n. Pokud dokážeme 1 Pro nějaké přirozené k0 platí tvrzení T(k0), 2 Pro libovolné přirozené k k0 platí implikace T(k) T(k + 1), pak tvrzení T(n) platí pro libovolné přirozené n k0. Poznámka. V bodě dva můžeme dokazovat i ,,slabší implikaci (Tk0 Tk0+1 Tk) T(k + 1). Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Dokažte následující tvrzení: 1 n i=1 i3 = n2(n + 1)2 4 Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Dokažte následující tvrzení: 1 n i=1 i3 = n2(n + 1)2 4 2 Na kolik nejvíce částí dělí rovinu n přímek? Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Dokažte následující tvrzení: 1 n i=1 i3 = n2(n + 1)2 4 2 Na kolik nejvíce částí dělí rovinu n přímek? 3 Všechna přirozená čísla jsou si rovna. Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Dokažte, že existuje nekonečně mnoho prvočísel. Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Plán přednášky 1 Typy matematických důkazů Matematická indukce Důkaz sporem 2 Sumy 3 Počítání s procenty 4 Zlehka kombinatoriky Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Sumy Aritmetická řada n i=1 ik = k n(n + 1) 2 Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Sumy Aritmetická řada n i=1 ik = k n(n + 1) 2 Geometrická řada (q = 0, 1): n i=0 qn = qn+1 - 1 q - 1 Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky 1 Odvoďte přímo vztah n i=1 i3 = n2(n+1)2 4 . Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky 1 Odvoďte přímo vztah n i=1 i3 = n2(n+1)2 4 . Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Plán přednášky 1 Typy matematických důkazů Matematická indukce Důkaz sporem 2 Sumy 3 Počítání s procenty 4 Zlehka kombinatoriky Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Příklad Mirek si chce koupit nové auto. Auto stojí 300 000 Kč. Mirek by chtěl auto koupit na měsíční splátky. Prodávající společnost mu nabízí půjčku na koupi auta s ročním úrokovou mírou 6%. Mirek by chtěl auto splatit za tři roky. Jak vysoká bude měsíční splátka? (první splátku zaplatí po měsíci od koupě) Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Plán přednášky 1 Typy matematických důkazů Matematická indukce Důkaz sporem 2 Sumy 3 Počítání s procenty 4 Zlehka kombinatoriky Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Uvažujme slova složená pouze z písmen A a B. Kolik existuje slov délky n se sudým počtem písmen A? Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Příklad Kolika různými způsoby může vypadat pořadí týmů v tabulce hokejové extraligy? Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Příklad Kolika různými způsoby může vypadat pořadí týmů v tabulce hokejové extraligy? Příklad Kolika způsoby lze vybrat z osmi obyvatel domu tříčlenný domovní výbor, který se skládá z předsedy, místopředsedy a pokladníka? Typy matematických důkazů Sumy Počítání s procenty Zlehka kombinatoriky Příklad Kolika různými způsoby může vypadat pořadí týmů v tabulce hokejové extraligy? Příklad Kolika způsoby lze vybrat z osmi obyvatel domu tříčlenný domovní výbor, který se skládá z předsedy, místopředsedy a pokladníka? Příklad Kolika způsoby můžeme vytvořit čtyři smíšené páry z deseti chlapců a osmi dívek?