UNIVERZITA PALACKÉHO V OLOMOUCI PEDAGOGICKÁ FAKULTA Katedra matematiky
Bakalářská práce Romana Olejníčková
DŮKAZY MATEMATICKOU INDUKCÍ
Olomouc 2015
Vedoucí práce: doc. RNDr. Jitka Laitochová, CSc.
Prohlašuji, že jsem bakalářskou práci s názvem Důkazy matematickou indukcí vypracovala samostatně a výhradně s využitím citované literatury a zdrojů. Souhlasím se zapůjčováním práce a s jejím zveřejněním.
V Prostějově dne 11. 4. 2015
………………………….. Romana Olejníčková
Poděkování Mé poděkování patří doc. RNDr. Jitce Laitochové, CSc. za její odborné vedení, cenné rady, vstřícnost a laskavost při vzniku této bakalářské práce.
Obsah Abstrakt ...................................................................................................................................... 5 Úvod ........................................................................................................................................... 6 Kapitola 1 ................................................................................................................................... 7 Matematické důkazy ............................................................................................................... 7 1.1 Historie matematických důkazů...................................................................................... 7 1.2 Druhy matematických důkazů ........................................................................................ 9 1.2.1 Přímý důkaz.............................................................................................................. 9 1.2.2 Nepřímý důkaz ....................................................................................................... 10 1.2.3 Důkaz sporem ......................................................................................................... 11 1.2.4 Důkazy existence, neexistence a jednoznačnosti ................................................... 11 1.2.5 Důkaz matematickou indukcí ................................................................................. 12 Kapitola 2 ................................................................................................................................. 14 Matematická indukce ............................................................................................................ 14 2.1 Úplná a neúplná indukce............................................................................................... 14 2.2 Matematická indukce .................................................................................................... 15 2.3 Úlohy s využitím matematické indukce ........................................................................ 17 2.4 Úlohy k procvičování matematické indukce................................................................. 29 Kapitola 3 ................................................................................................................................. 32 Posloupnosti a řady ............................................................................................................... 32 3.1 Posloupnosti a řady ....................................................................................................... 32 3.2 Využití matematické indukce při řešení úloh o posloupnostech a řadách .................... 34 3.3 Neřešené úlohy o posloupnostech a řadách s využitím matematické indukce ............. 39 Závěr ......................................................................................................................................... 41 Seznam symbolů ....................................................................................................................... 42 Použitá literatura ....................................................................................................................... 43
4
Abstrakt V bakalářské práci se zabývám tématem Důkazy matematickou indukcí. Důvodem jejího napsání bylo vytvoření sbírky příkladů s využitím matematické indukce. Měla by sloužit nejen k vysvětlení tématu matematické indukce, ale také k jeho procvičení. Práce je členěna do tří hlavních kapitol. V první kapitole se zabýváme matematickými důkazy, jejich historií a dělením. Druhá kapitola se skládá z teorie o matematické indukci a z řešených i neřešených úloh s využitím matematické indukce. V poslední kapitole se věnujeme posloupnostem a řadám, kde je často matematické indukce při jejich řešení využíváno.
Klíčová slova: matematický důkaz, induktivní postup, úplná indukce, neúplná indukce, matematická indukce, přirozená čísla, posloupnosti, nekonečné číselné řady
Abstract In the bachelor work I deal with the topic Proofs by mathematical induction. The reason for writing it was to create a collection of problems by using mathematical induction. It not only should serve to explain the topic of mathematical induction, but also its practicing. The work is divided into three main chapters. In the first chapter we look at mathematical proofs, their history and division. The second chapter comprises theory about mathematical induction and both solved and unsolved problems by using mathematical induction. The last chapter focuses on sequences and series where mathematical induction is often used for solution.
Key words: mathematic proof, inductive steps, complete induction, incomplete induction, mathematical induction, natural numbers, sequences, infinite numerical series.
5
Úvod Cílem bakalářské práce bylo vytvoření sbírky úloh s využitím matematické indukce a vytvoření uceleného pohledu na dokazování matematickou indukcí. Nachází se zde i teorie o matematických důkazech, matematické indukci a posloupnostech a řadách, kde je matematická indukce často využívána. Měla by být pomůckou pro studenty při řešení úloh s použitím matematické indukce, ale i pro pedagogy jako inspirace při zadávání úloh. Práce je doplněna o základní pojmy v anglickém jazyce. Je rozdělena do tří kapitol. V Kapitole 1 se zabýváme matematickými důkazy, které mají v matematice velký význam, jelikož bez jejich pomoci nejsme schopni potvrdit platnost matematické věty. Dále se zde věnujeme historii matematických důkazů a jejich druhy jako je přímý důkaz, nepřímý důkaz, důkaz sporem, důkaz existence, neexistence a jednoznačnosti a důkaz matematickou indukcí. Kapitola 2 pojednává především o matematické indukci, ale také o induktivních postupech, kam spolu s úplnou a neúplnou indukcí patří. Zabýváme se zde také definováním přirozených čísel pomocí Peanových axiomů, jelikož jsou jedním ze základních pojmů matematické indukce. Na konci kapitoly najdeme řešené i neřešené úlohy s využitím matematické indukce. Kapitola 3 se věnuje posloupnostem a řadám. Na začátku kapitoly jsou posloupnosti a řady definovány. Dále se v kapitole nachází řešené i neřešené úlohy o posloupnostech a řadách, kde je dokazování matematickou indukcí využito.
6
Kapitola 1 Matematické důkazy V úvodní kapitole se budeme zabývat matematickými důkazy, vysvětlením pojmů, které jsou potřeba k tomu, abychom si matematické důkazy mohli definovat. Dále se budeme věnovat historii matematických důkazů a jejich rozdělení. Matematické důkazy (mathematical proofs) mají velký význam, jelikož bez jejich pomoci nejsme schopni potvrdit či vyvrátit jakoukoliv myšlenku či hypotézu. Obecně si matematický důkaz můžeme definovat jako úvahu, která zdůvodňuje platnost matematické věty. Důkaz matematické věty (proof of mathematical theorem) je logický proces, kterým ověřujeme platnost matematické věty pomocí axiomů, definic a dříve dokázaných vět. Axiómy (axioms) jsou matematické výroky, které jsou považovány za pravdivé a nedokazují se. Za výrok (verdict) se považuje každé tvrzení, u kterého můžeme určit jeho pravdivostní hodnotu. Definice (definition) využívá základní pojmy (nebo pojmy dříve zavedené) k určení názvu a charakteristických vlastností nového pojmu. Matematická věta (mathematical theorem) je pravdivý matematický výrok, který je odvozený na základě axiomů, definic a dříve dokázaných vět.11 Matematická věta se může vyskytovat v několika různých tvarech. První možností je tzv. obecná věta, která je ve tvaru věta ve tvaru „
. Další je tzv. existenční
“ nebo uvažujeme větu o jednoznačné existenci „
“. Velmi často je obecná věta ve tvaru implikace „
“, kde A se
nazývá předpoklad a B se nazývá tvrzení věty. Dále se A nazývá postačující podmínka pro B a B nutná podmínka pro A. Je-li věta ve tvaru ekvivalence „
“, tak pro ni platí
. Z toho důvodu ji můžeme dokazovat obdobně jako věty ve tvaru implikace.2
1.1 Historie matematických důkazů Historie matematických důkazů (history of mathematical proofs) sahá až do starého Egypta, ale matematické důkazy v dnešním slova smyslu nejsou dochovány. Dochovalo se pouze mnoho záznamů s řešením různých problémů a úloh. 1
JANUROVÁ, Eva a JANURA, Miroslav. Matematika: průvodce učivem základní a střední školy. 1. vyd. Olomouc: Rubico, 1999, s. 18 2
ŘEHÁK, Pavel. Základy matematiky. 2014. Dostupné z: http://users.math.cas.cz/~rehak/soubory/zaklady_matematiky.pdf, s.11
7
Deduktivní matematický důkaz má svůj původ ve starověkém Řecku, které vzniklo kolem roku 800 př. n. l. Z této doby pochází nejstarší dochované důkazy. Matematický důkaz podobný důkazu používaného v dnešní době má své počátky v řecké geometrii, která se rozvíjela pod vlivem Platónovy filosofie. Matematici, kteří byli Platónovou filozofií ovlivněni, museli vždy odkrývat svět geometrie a dívat se na pravdu, co v něm byla obsažena. Pokud nějaký matematik viděl, neboli evidoval platnost například Pythagorovy věty, viděl ji pouze v době, kdy se dokonale soustředil. Z toho důvodu nebyla Platónská filosofie dlouho udržitelná, jelikož šla využít pouze u jednoduchých typů důkazů a při rozvíjení geometrie nebylo možné se tak dlouho soustředit, aby matematik uviděl pravdu. Matematici začali odstupovat od platónské filozofie a přešli ke kroku, který udal směr matematice až do dnešní doby. Daným krokem bylo používání rozumu. Geometrické pravdy přestaly být evidovány, jelikož je stačilo pouze rozumově zdůvodnit, že by evidovány být mohly. Tímto způsobem začal vznikat matematický důkaz. Další významnou dobou pro matematický důkaz byla doba Aristotela, neboť v této době vznikl přímý a nepřímý důkaz. V době římské se o matematické důkazy vůbec nezajímali, zajímali se pouze o matematiku, která se hodila ve vojenství a stavitelství. V raném středověku si matematika prošla obdobím temna. Pouze Byzantská říše se zajímala o matematické dokazování ze Starověkého Řecka. V Byzantské říši se inspirovala říše Arabská, která byla ovlivněna i indickou matematikou. Arabská matematika se projevila především v díle s názvem Al-Choreziho, v kterém byly položeny základy algebry a vytvořen nový typ matematického důkazu – důkaz výpočtem. V 16. - 19. století byl pro matematické dokazování důležitý pojem obor, u něhož lze o každém prvku rozhodnout, zda do něj patří nebo nepatří. Oborem jsou například přirozená čísla. Aristotelův vliv měl v této době stále velký význam. Existenční tvrzení se v této době dokazovala pouze konstrukčním důkazem. Dále byl důležitý typ důkazu, který byl založen na geometrickém názoru. Tento typ důkazu byl využit například u Bolzanovy věty. Velkého významu pro matematické dokazování se dostalo českému matematikovi, filozofovi a knězi Eduardu Bolzanovi, který žil v letech 1781 – 1848. Mezi jeho významná díla patří Betrachtungen uber einigo Gegenstände der Elementargeometrie, Rein analytischer Beweid a Paradoxier des Unedlichen, které ovlivnilo zakladatele teorie množin Georga Cantora. Jeho matematické důkazy jsou založeny na nahrazení oborů trvale existujícím seskupením objektů, z kterých se později stal pojem množiny. Seskupení objektů bylo velmi důležité pro vznik nového typu dokazování, který se nazývá nekonstruktivní neboli ryze existenční. Příkladem tohoto typu důkazu je Cantonův důkaz existence transcendentních čísel. 8
Canton dokázal, že všech algebraických čísel je spočetně mnoho na rozdíl od čísel reálných, kterých je nespočetně mnoho. Bolzan zkoumal i takové matematické objekty, jejichž existence byla sice dokazatelná, ale nešlo ji zkonstruovat. Z toho důvodu se v druhé polovině 19. století axiomatizoval pojem matematický důkaz. Došlo k odstranění intuice a začaly se přesně formulovat pojmy. Přirozený jazyk se nahrazoval jazykem symbolickým. David Hilbert, Gottlob Freg a další matematici postupně vytvořili ve svých pracích bohatý symbolický jazyk, s nímž šly vyjádřit všechna matematická tvrzení. Vznikl formální důkaz a díky němu šly dokazovat formule s pomocí logických axiomů, než použití intuice či osobního názoru. V této době je důkaz definovatelným pojmem a později v době počítačů byla jeho správnost ověřena algoritmicky pracujícím počítačem. V dnešní době existují počítačové programy, které jsou schopny konstruovat důkazy matematických vět, ale stále nejsou schopny konkurovat lidskému dokazování.3
1.2 Druhy matematických důkazů 1.2.1 Přímý důkaz Přímý důkaz (direct proof) řadíme k základním typům důkazů. Využívá se při dokazování matematických vět, které jsou ve tvaru implikace
, kde A je předpoklad a
B je výrok, který chceme dokázat. Matematickou větu ve tvaru implikace
dokážeme
pomocí řetězce implikací. Je-li A axióm nebo platná věta (dříve dokázaná), pak z platností všech implikací ,
plyne platnost implikace
, tedy i výroku B. Často
máme zadaný jen výrok B, který chceme dokázat a výrok A si musíme vhodně zvolit.4 Úloha 1.2.1 Přímým důkazem dokažte větu
.
3
Matematický důkaz. Wikipedie [online]. 2010 [cit. 2015-04-15]. Dostupné z: http://cs.wikipedia.org/wiki/Matematick%C3%BD_d%C5%AFkaz 4
JANUROVÁ, Eva a JANURA, Miroslav. Matematika: průvodce učivem základní a střední školy. 1. vyd. Olomouc: Rubico, 1999, s. 18
9
Řešení: Abychom mohli zadanou větu dokázat, musíme si upravit pravou stranu, proto si nejprve vytkneme a a dále upravíme podle vzorce
.
Zjistili jsme, že zadaná věta platí a jedná se o tři po sobě jdoucí čísla (a - 1), a, (a+1). Z toho důvodu je jedno dělitelné dvěma a druhé třemi, a proto platí, že jejich součin je dělitelný šesti.
1.2.2 Nepřímý důkaz Nepřímý důkaz (proof by contraposition) se obdobně jako důkaz přímý používá k dokázání matematických vět ve tvaru implikace, ale původní větu nahradíme větou obměněnou, tj. místo dokazování
budeme dokazovat větu ve tvaru
Dokazování věty obměněné nám umožní tautologie ve tvaru
.5
Nepřímý důkaz je úzce propojen s důkazem sporem. Každý nepřímý důkaz můžeme převést na důkaz sporem. Úloha 1.2.2 Nepřímým důkazem dokažte větu: Řešení: Má se jednat o nepřímý důkaz, a proto budeme dokazovat větu obměněnou, která má tvar . Důkaz věty obměněné: Dokázali jsme větu obměněnou, a proto platí i věta původní
5
Co je to důkaz. Matematika.cz [online]. 2013 [cit. 2015-04-12]. Dostupné z: http://www.matematika.cz/dukazy
10
1.2.3 Důkaz sporem Důkaz sporem (proof by contradiction) patří k oblíbeným metodám dokazování. Je založen na zákonu o vyloučení třetího. Zákon o vyloučení třetího říká, že pro každé tvrzení P platí, že
je pravdivé. Z toho důvodu tento zákon můžeme použít pouze tam, kde toto
tvrzení platí. V důkazu sporem dokážeme, že předpoklad vede k nesmyslnému výsledku neboli ke sporu, což znamená, že je předpoklad nepravdivý, a proto je pravdivá jeho negace. Důkaz sporem provádíme ve třech krocích. Nejdříve provedeme negaci Aʾ původního výroku A. Poté vytvoříme řetězec implikací
, kde výrok Bn neplatí, což
je logický spor. Zjistíme, že negovaný výrok Aʾ neplatí, a proto platí původní výrok A.6 Úloha 1.2.3 Dokažte sporem větu, že
je iracionální číslo.
Řešení: Budeme dokazovat negaci věty původní: Je-li
je racionální číslo, proto můžeme psát
racionální číslo, pak
ě á čí
Zjistili jsme, že číslo p je dělitelné 3 i číslo q je dělitelné 3, a proto jsou to čísla soudělná. Nastává tedy spor s předpokladem, neboť předpoklad, že platí původní věta, že
je racionální číslo neplatí. Proto
je iracionální číslo.
1.2.4 Důkazy existence, neexistence a jednoznačnosti Důkazy existence, neexistence a jednoznačnosti se používají při dokazování existenčních vět a můžeme je sestrojit přímo nebo nepřímo. Přímý důkaz může být ryze existenční či konstrukční. U ryze existenčního existenci objektu přímo dokážeme bez jeho určení pomocí nějakého principu např. Dirichletova, jehož nejznámější znění je takové, že pokud umístíme m předmětů do n přihrádek, kde m a n jsou přirozená čísla, pak musí existovat alespoň jedna přihrádka, ve které budou dva předměty. 6
Co je to důkaz. Matematika.cz [online]. 2013 [cit. 2015-04-12]. Dostupné z: http://www.matematika.cz/dukazy
11
U konstrukčního dokazování musíme objekt sestrojit. Pro důkaz neexistence je typické dokazování sporem. Důkaz jednoznačnosti je založen na tom, že existuje alespoň jeden objekt a současně existuje nejvýše jeden objekt. U důkazu jednoznačnosti využíváme opět důkaz sporem, kde předpokládáme existenci dvou různých objektů, pro který výrok platí.7
1.2.5 Důkaz matematickou indukcí Důkazu matematickou indukcí se budeme věnovat zvlášť ve 2. kapitole s názvem Matematická indukce. Některé matematické věty lze dokazovat více způsoby. Jedná se například o Pythagorovu větu, která platí v pravoúhlém trojúhelníku a je ve tvaru
, kde a, b
jsou v pravoúhlém trojúhelníku odvěsny a c přepona. Pythagorova věta nám říká, že v pravoúhlém trojúhelníku se čtverec nad nejdelší stranou neboli přeponou rovná součtu čtverců nad odvěsnami. U Pythagorovy je známo několik stovek důkazů a my se podíváme na ty nejzajímavější. První důkaz je založen na tom, že obsah velkého čtverce se rovná součtu obsahu malého čtverce a čtyřech trojúhelníků (viz. Obrázek 1.1)
Obrázek 1.1: Důkaz Pythagorovy věty pomocí dvou čtverců (zdroj: POLSTER, Burkard. Q.E.D.: krása matematického důkazu. 1. vyd. v českém jazyce. Praha: Dokořán, 2014)
7
ŘEHÁK, Pavel. Základy matematiky. 2014. Dostupné z: http://users.math.cas.cz/~rehak/soubory/zaklady_matematiky.pdf, s.12
12
Podobný typ důkazu je znázorněn na diagramu na Obrázku 1.2.
Obrázek 1.2: Důkaz Pythagorovy věty pomocí dvou čtverců (zdroj: POLSTER, Burkard. Q.E.D.: krása matematického důkazu. 1. vyd. v českém jazyce. Praha: Dokořán, 2014)
Dále věta, vytvořena Klaudiem Ptolemaiem, která říká, že pro čtyřúhelník vepsaný do kružnice platí
. Tato věta je Pythagorovou, jestliže se jedná o čtyřúhelník
obdélník.
Obrázek 1.3: Ptolemaiův čtyřúhelník vepsaný v kružnici (zdroj: POLSTER, Burkard. Q.E.D.: krása matematického důkazu. 1. vyd. v českém jazyce. Praha: Dokořán, 2014)
13
Kapitola 2 Matematická indukce V následující kapitole si uvedeme rozdíl mezi úplnou a neúplnou indukcí, dále si vysvětlíme dokazování pomocí matematické indukce, vyřešíme úlohy s využitím matematické indukce a na závěr je uvedeno pár úloh k procvičování. Matematická indukce spolu s úplnou a neúplnou indukcí patří do induktivních postupů (inductive approachs). Logika nám vysvětluje, že indukce představuje postup od jednotlivého k obecnému. Z toho důvodu je cílem indukce dosáhnout obecného tvrzení o všech objektech určitého druhu (hledáme jejich společnou vlastnost nebo vztah, který spojuje skupinu objektů). Počátky filozofických úvah o induktivním myšlení spadají do dob Sokrata (469 – 322 před n. l.). Dalším filozofem, který se tímto tématem zabýval, byl Aristoteles (384 – 322 před n. l.). Po delší dobu se induktivním myšlením nikdo nezabýval až Francis Bacon (1561 – 1626) a dále John Stuart Mill (1806 – 1873). Od poloviny 19. století patří k induktivním metodám pojmy i z pravděpodobnosti a statistiky. Ve 20. století jsou induktivní metody považovány za zvláštní část logiky.8
2.1 Úplná a neúplná indukce U úplné indukce (complete induction) se zabýváme prvky konečné třídy T. Úplná indukce probíhá ve třech krocích. Nejprve zkoumáme objekty x konečné třídy T s cílem objevení společné vlastnosti V těchto prvků, dále ověříme, zda objekty konečné třídy T mají objevenou vlastnost V a nakonec vyslovíme obecný výrok jako závěr buď
nebo
. Pořadí kroků je velmi důležité, jinak by se nejednalo o indukci. Stejného postupu je využito při psychologických testech, kde například známe číselnou řadu a máme doplnit další čísla dle pravidla, které se vyskytuje u předchozích čísel. Takové typy úloh se aplikují již u žáků 5. třídy, ale čísel je zadaný menší počet. Žáci si tímto způsobem rozvíjí induktivní myšlení. V matematice však dominuje neúplná indukce, která se zabývá prvky nekonečných tříd. Neúplná indukce (incomplete induction) vede k obecným hypotézám. Hypotéza (hypothesis) je výrok, u kterého neznáme pravdivostní hodnotu. Proto v matematice musíme 8
ODVÁRKO, Oldřich. Metody řešení matematických úloh. Vyd. 2., přeprac. Praha, 1986.
14
používat deduktivní metody, které nám umožní obecnou hypotézu dokázat nebo vyvrátit. Z toho důvodu neúplná indukce spočívá v tom, že obecný výrok o všech prvcích třídy T vyslovujeme na základě výsledků zkoumání jen části třídy T. Obdobně, jako úplná indukce, probíhá ve třech krocích. Nejprve prozkoumáme několik objektů třídy T a objevíme společnou vlastnost pro tyto objekty V. Dále vyslovíme obecnou hypotézu o všech objektech . Nakonec ověříme námi vyslovenou obecnou hypotézu. Výsledek však
třídy T:
není jistý, jelikož při ověření obecné hypotézy můžou nastat tři případy: hypotézu dokážeme, hypotézu vyvrátíme, anebo nejsme schopni hypotézu ani dokázat, ani vyvrátit. Hypotézy, které nejsme schopni ani dokázat, ani vyvrátit řadíme do metateorie. Například tzv. Fermatova věta je nerozhodnutou hypotézou už přes 300 let. 9
2.2 Matematická indukce V matematice se často nacházejí výroky, které jsou závislé na přirozených číslech, proto má v matematice důležitou roli matematická indukce (mathematical induction) a je velmi často při dokazování matematických vět a řešení úloh využívána. Uvažujeme-li množinu M, která má tyto dvě vlastnosti: 1)
.
2) Pro každé přirozené číslo p platí: Jestliže
, potom také
. Množina M
obsahuje všechny přirozená čísla. Na tomto principu je dokazování matematických vět pomocí matematické indukce založeno. Máme-li větu ve tvaru „Pro každé přirozené číslo platí…“ (nebo dá-li se tak zformulovat), tak stačí dokázat dvě pomocné věty: 1. věta: Věta platí pro číslo 1. 2. věta: Pro každé přirozené číslo p platí: Pokud věta platí pro číslo p, pak platí i pro číslo
. Vidíme, že je to obdoba našeho principu. Místo množiny M vezmeme množinu
přirozených čísel, pro něž daná věta platí. 2. pomocná věta se skládá ze dvou částí: z indukčního předpokladu (induction assumption) a indukčního kroku (induction step).10 Schéma důkazu matematickou indukcí může mít mnoho různých podob. Například budeme-li nějaké tvrzení dokazovat pro
, tak budeme první krok matematické indukce
9
ODVÁRKO, Oldřich. Metody řešení matematických úloh. Vyd. 2., přeprac. Praha, 1986. VRBA, Antonín, ed. Kombinatorika, pravdepodobnosť, matematická indukcia: Pre 2. roč. gymnázia so zameraním na matem. Vyd. 4. Bratislava, 1989. s. 5 10
15
ověřovat pro
. Obdobně můžeme dokázat i obecnější varianty, které umožňují
dokazovat věty ve tvaru: „Pro každé celé číslo větší nebo rovno k platí…“. U obecnějších variant musíme opět dokázat dvě pomocné věty: 1. věta platí pro celé číslo k. 2. Pro každé celé číslo c ≥ k platí: Pokud věta platí pro číslo c, pak musí platit i pro číslo c + 1. Matematickou indukcí můžeme dokázat, že výroky jsou pravdivé, pro všechna přirozená čísla. Z toho důvodu jsou přirozená čísla jedním ze základních pojmů matematické indukce. Můžeme je vytvořit z jedničky opakovaným sčítáním.11 Přirozená čísla (integers) můžeme formulovat různě, ale nejznámější definice je pomocí tzv. soustavy Peanových axiomů (Peano axioms): P1: 1 je přirozené číslo. P2: Ke každému přirozenému číslu a existuje jediný jeho následovník a´ a ten je také přirozené číslo. P3: 1 není následovník žádného přirozeného čísla. P4: Různá přirozená čísla mají různé následovníky. P5: Nechť má množina M tyto dvě vlastnosti: a) Obsahuje číslo 1. b) S každým přirozeným číslem a obsahuje i jeho následovníka a´. Potom množina M obsahuje všechna přirozená čísla. Můžeme si všimnout, že u axiomu P5 je využita matematická indukce. Důkaz matematickou indukcí je velmi zajímavý, neboť jeho obdobu můžeme pozorovat u matematického domina. Když si do řady postavíme očíslované kostky domina ve správné vzdálenosti od sebe tak, aby platilo, že jestliže se převrátí kostka n, pak se převrátí i kostka následující
tak při převrácení máme zaručené, že se jednou převrátí i
kterákoliv jiná kostka. Na stejném principu je důkaz matematickou indukcí založen. Jediný rozdíl je v tom, že místo dominových kostek máme nekonečný počet tvrzení očíslovaných pomocí přirozených čísel. Zaručíme-li pravdivost prvního tvrzení a zároveň bude platit, že z pravdivosti n-tého tvrzení vyplývá pravdivost (
)-tého tvrzení, tak víme, že jsou
pravdivá všechna tvrzení.
11
ODVÁRKO, Oldřich. Metody řešení matematických úloh. Vyd. 2., přeprac. Praha, 1986.
16
S důkazem matematickou indukcí se žáci nesetkají na základní škole. Setkají se s ní až na škole střední a dále na škole vysoké.
2.3 Úlohy s využitím matematické indukce Úloha 2.3.1 Pomocí matematické indukce dokažte, že pro všechna přirozená čísla platí
Řešení Nejdříve danou rovnost dokážeme pro n = 1:
Danou rovnost pro n = 1 jsme dokázali. Dále budeme předpokládat, že daná rovnost platí pro n = k:
Protože jsme předpokládali, že daná rovnost platí pro n = k, tak dokážeme, že platí i pro :
17
Dokázali jsme, jestliže zadaná věta platí pro n = k, tak platí i pro n = k + 1. Použitím matematické indukce jsme dokázali, že zadaná rovnost platí.
Úloha 2.3.2 Dokažte, že pro každé přirozené číslo n platí vztah:
Řešení Nejdříve použijeme 1. krok matematické indukce a zadaný vztah dokážeme pro n = 1:
Pro
jsme daný vztah dokázali. Dále použijeme 2. krok matematické indukce a
předpokládáme, že daná věta platí pro n = k: Protože jsme předpokládali, že zadaný vztah platí pro n = k, tak ho musíme dokázat pro n = k+1.
Dokázali jsme i 2. krok matematické indukce, a proto zadaný vztah pro přirozené číslo n platí.
Úloha 2.3.3 Užitím matematické indukce dokažte, že pro každé přirozené číslo n platí
Řešení Nejprve danou rovnost dokážeme pro
: 18
Zjistili jsme, že pro n = 1 daná rovnost platí. Budeme předpokládat, že rovnost platí pro : Danou rovnost dokážeme pro
:
Zadanou větu jsme dokázali.
Úloha 2.3.4 Pomocí matematické indukce dokažte, že pro každé přirozené číslo n platí
Řešení Nejdříve zadanou rovnost dokážeme pro n = 1:
Na obou stranách nám vyšlo číslo 1 a tím je daná rovnost pro n = 1 dokázána. Dále budeme předpokládat, že zadaná rovnost platí pro n = k.
Potom dokážeme pro n = k + 1:
19
Dokázali jsme, že daná rovnost platí i pro
. Tím jsme zadanou rovnost pomocí
matematické indukce dokázali a úloha je vyřešena.
Úloha 2.3.5 Využitím matematické indukce dokažte, že pro každé přirozené číslo n platí:
Řešení Danou větu dokážeme pro n = 1:
Zadanou větu jsme pro n = 1 dokázali. Dále budeme předpokládat, že A danou větu dokážeme pro
:
:
Dokázali jsme indukční předpoklad a zjistili, že zadaná věta platí.
Úloha 2.3.6 Dokažte, že číslo
není dělitelné číslem 73 pro každé přirozené číslo.
20
Řešení Nejprve dokážeme pro první pomocnou větu, kde k = 1. 23 + 34 = 89 Zjistili jsme, že pro k = 1 věta platí, jelikož číslo 89 není dělitelné číslem 73. Dále dokážeme druhou pomocnou větu. Předpokládáme, že tvrzení platí
, dokážeme
. 23p + 3 + 34p + 4 = 23 · 23p + 34 · 34p = 8 · 23p + 81· 34p = 8 · (23p + 34p) + 73 · 34p Vidíme, že první ze sčítanců není dělitelný číslem 73, druhý naopak ano. Dokázali jsme, že jejich součet není dělitelná číslem 73. Pomocnou větu jsme nedokázali a tím zjistili, že číslo 23k + 34k není dělitelné číslem 73.
Úloha 2.3.7 Dokažte pomocí matematické indukce, že platí Bernoulliho nerovnost:
Řešení Použijeme 1. krok matematické indukce a danou větu dokážeme pro
:
1. krok matematické indukce jsme dokázali a dále dokážeme 2. krok. Předpokládáme, že zadaná věta platí pro
:
a dokážeme pro
:
Dokázali jsme i 2. krok matematické indukce. Zadaná věta je dokázána.
21
Úloha 2.3.8 Dokažte binomickou větu pomocí matematické indukce:
Řešení Binomickou větu dokážeme pro
Danou větu jsme pro
:
dokázali. Dále předpokládáme, že
Binomickou větu dokážeme pro
:
:
Použijeme-li vzorce: , , tak dostaneme:
Binomickou větu se nám podařilo pomocí matematické indukce dokázat.
Úloha 2.3.9 Pomocí matematické indukce dokažte, že součin dvou po sobě jdoucích přirozených čísel je dělitelný dvěma.
22
Řešení Dvě po sobě jdoucí přirozená čísla jsou n a n + 1. Máme dokázat větu
.
Nejdříve větu dokážeme pro n = 1: První krok matematické indukce jsme dokázali, jelikož 2 je dělitelné dvěma. Dále budeme předpokládat, že n = k: Dokážeme, že věta platí i pro n = k + 1: Vidíme, že se jedná o dvě po sobě jdoucí čísla, tak platí, že jedno z nich musí být sudé, a proto bude součin dělitelný dvěma. Zadanou větu jsme dokázali.
Úloha 2.3.10 Dokažte matematickou indukcí:
Řešení Zadanou větu dokážeme pro n = 1:
Danou větu jsme dokázali pro n = 1. Dále budeme předpokládat, že daná věta platí pro n = k: A dokážeme pro
:
Dle indukčního předpokladu je zřejmé, že výraz
je dělitelné šesti, 12 je dělitelné šesti a
je dělitelný třemi a jelikož se jedná o dvě po sobě jdoucí čísla, tak i dvěma.
Zadanou větu jsme dokázali.
23
Úloha 2.3.11 V rovině je dán konečný počet přímek a ty rovinu dělí na části. Dokažte, že tyto části je možno vybarvit dvěma barvami tak, aby každá část byla vybarvena jinou barvou a aby dvě sousední části nebyly vybarveny stejnou barvou. Řešení Jestliže nám jedna přímka rozděluje rovinu na dvě poloroviny, tak obě poloroviny lze vybarvit odlišnými barvami. Dokázali jsme, že 1. krok matematické indukce, kde n = 1. Dále budeme předpokládat, že věta platí pro jakýchkoliv k přímek. Budeme-li mít k + 1 přímek, tak si nejdřív jednu přímku odmyslíme. Dle indukčního předpokladu známe obarvení O pro zbylých k přímek. I nadále budeme uvažovat jednu přímku odmyšlenou a v jedné polorovině, na kterou dělí rovinu, přetočíme barvy o obarvení O (viz. Obrázek 2.1). Tím jsme získali obarvení pro k + 1 přímek, které splňuje zadání. Podařilo se nám dokázat i 2. krok matematické indukce a pomocí matematické indukce jsme dokázali větu zadanou.
Obrázek 2.1 Rozdělení roviny přímkami (zdroj: VRBA, Antonín, ed. Kombinatorika, pravdepodobnosť, matematická indukcia: Pre 2. roč. gymnázia so zameraním na matem. Vyd. 4. Bratislava, 1989.)
Úloha 2.3.12 Dokažte pomocí matematické indukce, že každou šachovnici tvaru
, na níž chybí
jedno políčko neboli poškozenou šachovnici, lze pokrýt kostkami tvaru L, které jsou složeny ze tří políček.
24
Řešení Nejprve větu dokážeme pro n = 1. Máme-li poškozenou šachovnici typu
, tak je sama ve
tvaru L (Obrázek 2.2) a lze ji pokrýt jednou kostkou. Danou větu jsme dokázali pro n = 1.
Obrázek 2.2: Poškozená šachovnice typu 2 x 2 (zdroj: VRBA, Antonín, ed. Princip matematické indukce. 1. vyd. Praha, 1977.)
Nyní budeme předpokládat, že daná věta platí pro číslo n a dokážeme pro n + 1. Vezmeme-li poškozenou šachovnici typu Získáme čtyři šachovnice typu
a šachovnici rozdělíme na čtvrtiny.
z nichž právě jedna šachovnice je poškozená.
Obrázek 2.3: Poškozená šachovnice typu 4 x 4 (zdroj: VRBA, Antonín, ed. Princip matematické indukce. 1. vyd. Praha, 1977.)
Ze zbývajících šachovnic odstraníme na každé jedno políčko, které je přilehlé ke středu původní šachovnice (Obrázek 2.3). Vzniknou nám čtyři poškozené šachovnice typu
.
Takový typ šachovnice umíme dle indukčního předpokladu pokrýt kostkami ve tvaru L. Zbyli nám tři políčka, které jsou však tvaru L a můžeme je také pokrýt kostkou ve tvaru L. Podařilo se nám pokrýt celou poškozenou šachovnici tvaru
Zadanou větu jsme dokázali.
Obrázek 2.4: Poškozená šachovnice 8 x 8 (zdroj: VRBA, Antonín, ed. Princip matematické indukce. 1. vyd. Praha, 1977.)
25
Úloha 2.3.13 Dokažte matematickou indukcí de Moivreovu větu: , kde i je imaginární jednotka a platí Řešení Nejprve de Moivreovu větu dokážeme pro n = 1:
Budeme předpokládat, že věta platí pro n = k: A dokážeme pro n = k + 1:
Podařilo se nám dokázat zadanou větu pro
. De Moivreovu větu jsme dokázali.
Úloha 2.3.14 Pomocí matematické indukce dokažte, že pro všechna přirozená čísla n platí:
Řešení Při řešení úlohy nejprve zadanou větu dokážeme pro n = 3:
Pro n = 3 jsme zadanou větu dokázali. Dále předpokládáme, že n = k: A dokážeme pro n = k + 1: 26
.
Za předpokladu, že
se znaménko nerovnosti nemění a
.
Úloha 2.3.15 Na čtverečkovaném bílém papíře máme n čtverečků začerněno. Čtverečky přebarvujeme najednou dle následujícího pravidla: Každý čtvereček bude mít takovou barvu, jakou měla většina z těchto tří čtverečků: uvažovaný čtvereček, čtvereček vedle něj vpravo a čtvereček bezprostředně nad ním. Dokažte matematickou indukcí, že nejvýše po n přebarveních budou všechny čtverečky bílé. Řešení Pro
zadaná věta zřejmě platí. Buď
čísla, která jsou menší než
a předpokládáme, že pro všechna přirozená
zadaná věta platí. Dokážeme, že zadaná věta platí i pro
. Nechť máme
čtverečků černých. Budeme uvažovat první svislou řadu čtverečků
zleva. V řadě se ještě nachází černé čtverečky. Ty nebudou mít žádný vliv na přebarvení čtverečků v ostatních svislých řadách, v kterých je nejvýše p černých čtverečků a dle indukčního předpokladu v nich po p přebarveních už žádný černý čtvereček nebude. Stejně dokážeme, že po p přebarveních nebude černý čtvereček ani ve vodorovných řadách kromě té, která byla nejníže a původně obsahovala černé čtverečky. Po p přebarveních může být černý pouze jediný čtvereček, v kterém se kříží uvažovaná levá svislá a dolní vodorovná řada. Po
-tém kroku bude přebarven na bílo i tento čtvereček. Tím jsme pomocí
matematické indukce zadanou větu dokázali.
27
Obrázek 2.5: Ukázka přebarvení čtverečků (zdroj: VRBA, Antonín, ed. Kombinatorika, pravdepodobnosť, matematická indukcia: Pre 2. roč. gymnázia so zameraním na matem. Vyd. 4. Bratislava, 1989.)
Úloha 2.3.16 Na poště prodávají známky z edice známek z roku 2014 s názvem Beskydy - kraj velkých šelem v hodnotě 13 Kč a 17 Kč. Dokažte pomocí matematické indukce, že známkami z této edice lze ofrankovat jakoukoliv zásilku, jejíž poštovné činí alespoň 204 Kč. Řešení U tohoto typu úlohy využijeme obecnější variantu matematické indukce. Při řešení úlohy musíme dokázat větu: Ke každému přirozenému číslu a ≥ 204 existují celá nezáporná čísla u, v takové, že platí Aby se nám podařilo větu dokázat, musíme dokázat obě pomocné věty pro celé číslo k = 204. 28
Podařilo se nám dokázat, že první pomocná věta platí. Dále budeme předpokládat, že máme celé číslo c ≥ 204 a že pro něj platí zadaná věta. Nyní musíme najít podobné vyjádření pro celé číslo c + 1. Můžeme si všimnout, že a Z toho nám plyne, máme-li u ≥ 4, tak a máme-li v ≥ 3, tak Dokázali jsme, jestliže je u ≥ 4 a v ≥ 3, tak platí i druhá pomocná věta. Jelikož jsme předpokládali, že c ≥ 204, tak jiný případ nemůže nastat, protože kdyby bylo současně u ≤ 3 a v ≤ 2, tak by Pomocí matematické indukce se nám podařilo dokázat, že lze známkami z edice známek z roku 2014 s názvem Beskydy kraj velkých šelem v hodnotách 13 Kč a 17 Kč ofrankovat zásilku, jejíž poštovné činí alespoň 204 Kč.
2.4 Úlohy k procvičování matematické indukce Úloha 2.4.1 Dokažte matematickou indukcí vztah
.
Úloha 2.4.2 Pomocí matematické indukce dokažte, že pro všechna přirozená čísla n platí .
29
Úloha 2.4.3 Dokažte, že pokud ke každému sudému číslu přičteme číslo dva, dostaneme opět sudé číslo. Úloha 2.4.4 Dokažte pomocí matematické indukce, že pro každé přirozené číslo n platí:
Úloha 2.4.5 Matematickou indukcí dokažte danou větu:
Úloha 2.4.6 Dokažte, že pro všechna přirozená čísla n platí, že devět dělí výraz .
Úloha 2.4.7 Dokažte, že pro všechna přirozená čísla je
dělitelné šesti.
Úloha 2.4.8 Pomocí matematické indukce dokažte, že pro každé přirozené číslo n platí:
Úloha 2.4.9 Ukažte, že pro všechna přirozená čísla n platí vztah . Úloha 2.4.10 Je dáno n čtverců. Dokažte, že je lze rozdělit na části tak, aby z nich bylo možné sestavit jediný čtverec.
30
Úloha 2.4.11 Pomocí matematické indukce dokažte větu:
Úloha 2.4.12 V rovině je dáno 7 přímek a ty danou rovinu rozdělují na části. Vybarvěte tyto části dvěma různými barvami tak, aby žádné dvě sousední neměly stejnou barvu. Úloha 2.4.13 Na čtverečkovaném bílém papíře máme n čtverečků začerněno. Každý čtvereček přebarvíme dle následujícího pravidla: Každý čtverec získá takovou barvu, jakou měla většina z těchto tří čtverečků: uvažovaný čtvereček, čtvereček vedle něj vpravo a čtvereček pod ním. Matematickou indukcí dokažte, že po nejvýše n přebarveních budou všechny čtverečky bílé. Úloha 2.4.14 Na poště prodávají známky z edice známek Praha – Evropské město kultury z roku 2000. Známky mají hodnotu 9 Kč a 11 Kč. Dokažte pomocí matematické indukce, že známkami z této edice lze ofrankovat jakoukoliv zásilku, jejíž poštovné je alespoň 80 Kč.
31
Kapitola 3 Posloupnosti a řady V poslední kapitole si nejprve posloupnost definujeme a rozdělíme si ji na aritmetickou a geometrickou posloupnost. Dále si řekneme, co je to posloupnost částečných součtů a vysvětlíme si pojem nekonečná číselná řada. Ukážeme si využití matematické indukce při řešení úloh o posloupnostech a řadách. Na závěr jsou uvedeny úlohy k procvičování. Matematickou indukcí se dokazují věty ve tvaru: „Pro všechna přirozená čísla n platí vztah V(n).“ Kde nám vztah V(n) udává vlastnost přirozených čísel, která je dána rovnicí či nerovnicí. Z toho důvodu se důkazy matematickou indukcí velmi často využívají při řešení některých typů úloh o posloupnostech a řadách především k vyjádření n-tého členu posloupnosti an, která je zadaná rekurentně, dále matematickou indukci můžeme také využít k částečnému součtu nekonečné číselné řady.12
3.1 Posloupnosti a řady Abychom si mohli posloupnosti definovat, musíme si nejprve definovat funkci jedné reálné proměnné. Definice 3. 1. 1: Nechť Df a Hf jsou dvě neprázdné množiny reálných čísel a nechť
a
. Každé zobrazení f množiny Df na množinu Hf se nazývá funkce jedné reálné proměnné x (functions of one variable x), která je definovaná na množině Df. Píšeme . Proměnnou x nazýváme nezávisle proměnnou neboli argument a proměnnou y nazýváme závisle proměnnou. Množinu Df nazýváme definiční obor funkce a množinu Hf nazýváme obor hodnot funkce. Definice 3.1.2: Nekonečnou číselnou posloupností (sequences) nazýváme reálnou funkci f (x) definovanou na množině všech přirozených čísel.
12
ODVÁRKO, Oldřich. Metody řešení matematických úloh. Vyd. 2., přeprac. Praha, 1986.
32
Vidíme, že rozdíl mezi funkcí a posloupností je pouze v tom, že u funkcí je definičním oborem množina reálných čísel nebo její část a grafem spojitá křivka. U posloupností je definičním oborem množina přirozených čísel nebo její část a graf tvoří pouze jednotlivé (izolované) body. K označení posloupnosti používáme počáteční písmena abecedy a index n značí proměnnou. Můžeme ji zapsat několika způsoby a to a1, a2, a3,… nebo a1, a2,…an,… nebo nebo stručně
. Hodnoty reálné funkce a1, a2, a3, …, an nazýváme první, druhý,
třetí, …, n-tý člen posloupnosti. n-tý člen posloupnosti nazýváme také obecný člen posloupnosti. Posloupnost můžeme mít zadanou několika způsoby. Může být zadána předpisem pro obecný člen posloupnosti, výčtem několika prvních členů posloupnosti nebo rekurentně. Rekurentní zadání posloupnosti znamená, že máme daný první člen posloupnosti nebo několik počátečních členů a dále předpis pro člen následující pomocí členu předchozího. Už na střední škole se studenti učí rozlišovat aritmetickou a geometrickou posloupnost. Definice 3.1.3: Posloupnost
nazýváme nekonečnou aritmetickou posloupností
(arithmetic sequence), právě tehdy když existuje takové číslo d, že pro každé přirozené číslo n platí . Číslo d nazýváme diference aritmetické posloupnosti. Definice 3.1.4: Posloupnost
nazýváme nekonečnou geometrickou posloupností
(geometric sequence), právě tehdy když existuje takové číslo q
, že pro každé přirozené
číslo n platí . Číslo q nazýváme kvocient geometrické posloupnosti. Definice 3.1.5: Označíme-li
nekonečnou posloupnost reálných čísel. Nekonečnou
číselnou řadou (infinite numerica series) rozumíme součet tvaru který také můžeme zapsat symbolem Definice 3.1.6: Posloupnost
,
.
nazýváme posloupností částečných součtů řady
Členy posloupnosti s1, s2,…, sn nazýváme první, druhý, n-tý částečný součet řady 33
. .
Definice 3.1.7: Říkáme, že řada konverguje (konverge) a má součet s, což píšeme nebo
, jestliže posloupnost částečných součtů
řady
má
vlastní limitu. Definice 3.1.8: Nemá-li posloupnost částečných součtů
limitu, říkáme, že řada
diverguje (diverge). Definice 3.1.9: Je-li ak
nebo
, říkáme, že řada
určitě diverguje k
.
Definice 3.1.10: Divergentní řady, které nejsou určitě divergentní, nazýváme oscilující. Z vlastností posloupností vyplývá, že u každé číselné řady nastane jedna z možností: řada konverguje, řada určitě diverguje
3.2
, řada určitě diverguje k
, nebo řada osciluje.
Využití matematické indukce při řešení úloh o posloupnostech a
řadách Úloha 3.2.1 Je dána posloupnost
, která je určena rekurentně a1 = 1,
je přirozené číslo. Najděte vzorec pro její n-tý člen.
34
, kde n
Řešení Nejdříve si určíme několik prvních členů posloupnosti: a1 = 1, a2 = Z určených členů můžeme určit, že pro n-tý člen platí
. Vztah musíme považovat za
hypotézu, jelikož přirozených čísel je nekonečně mnoho a z toho důvodu to pro všechna nemůžeme ověřit. Při dokazování hypotézy označíme
symbolem f (n) a využijeme matematickou indukci.
Nejprve musíme dokázat pro n = 1. Dostaneme
, tzn. že
. První krok
matematické indukce jsme dokázali. Dále musíme dokázat, platí-li rekurentní vztah pro libovolné číslo k, potom musí platit i pro přirozené číslo k + 1. Z toho důvodu předpokládáme, že platí
, pak dle rekurentního
vztahu musí platit:
Pomocí dokázaného tvrzení, že uvedený vztah platí pro každé přirozené číslo k, jsme zjistili, že platí i pro každé další přirozené číslo k + 1. Dokázali jsme, že vztah pro n-tý člen je
.
Úloha 3.2.2 Posloupnost
je dána rekurentně, kde
,
. Určete vztah pro její
n-tý člen. Řešení Nejprve si vypočítáme několik prvních členů posloupnosti:
,
,
,
.
Dále vyslovíme hypotézu, že pro n-tý člen platí
. Při dokazování hypotézy
označíme 2n – 1 symbolem f (n) a využijeme matematické indukce. Nejdříve musíme hypotézu dokázat pro n = 1. Dostaneme
, tzn. že
. První krok jsme dokázali. Dále musíme dokázat, platí-li rekurentní vztah pro libovolné číslo k, potom musí platit i pro přirozené číslo k + 1. Z toho důvodu předpokládáme, že platí vztahu musí platit:
35
a dle rekurentního
Pomocí matematické indukce jsme dokázali, že hledaný vztah pro n-tý člen je
.
Úloha 3.2.3 Najděte vzorec pro částečný součet sn řady
.
Řešení Budeme zkoumat posloupnost částečných součtů, které rekurentní zadání musíme vyčíst ze zadané číselné řady:
, kde n > 1. Dále si musíme určit několik prvních členů posloupnosti
Čitatelé členů posloupnosti částečných součtů
se rovnají n, kde
jmenovatelé členů posloupnosti částečných součtů s diferencí
:
tvoří aritmetickou posloupnost
.
Dále si určíme hypotézu: Hypotézu se budeme snažit dokázat pomocí matematické indukce. Nejdříve dokážeme pro n = 1: Dále si položíme n = k a n = k + 1: (1) (2) Jestliže
, potom
.
36
a
Dosadíme-li za sk a ak + 1 výrazy (1) a (2), dostaneme:
. Využitím matematické indukce se nám podařilo dokázat, že
platí a je hledaným
vzorcem. Spoustu matematických úloh, které mají obdobné zadání jako Úloha 3.2.3, lze velmi obtížně vyřešit, neboť se v nich nacházejí velmi složité výrazy, které není jednoduché upravit. Avšak matematickou indukci považujeme za nejjednodušší metodu při jejich řešení.
Úloha 3.2.4 Najděte vzorec pro částečný součet dané řady: Řešení Budeme se zabývat posloupností sn, jejíž rekurentní zadání nejdříve musíme vyčíst z dané řady. 1 Dále si vypočítáme několik prvních členů posloupnosti:
Vidíme, že členy posloupnosti se rovnají druhé mocnině n. Určíme si hypotézu:
.
Nejdříve hypotézu dokážeme pro n = 1: Dále si dáme n = k a n = k + 1: Jestliže
, potom
. Dosadíme-li za sk a ak+1 odpovídající
výrazy, tak dostaneme
37
Použili jsme matematickou indukci a podařilo se nám dokázat, že vzorec
platí a je
hledaným vzorcem.
Úloha 3.2.5 Ukažte, že součet geometrické řady
je pro
roven
.
Řešení Nejdříve použijeme indukční krok n = 1:
Indukční krok se nám nepovedlo dokázat, jelikož
. Zjistili jsme, že zadaná
geometrická řada nemá uvedený součet.
Úloha 3.2.6 Kruh máme rozdělený na
výsečí (Obrázek 3.1). Všech n-ciferných čísel, které mají ve
svém zápisu pouze číslice 1 a 2, je také
. Rozmístěte dané číslice po jednom do výsečí tak,
aby čísla v sousedních výsečích byla odlišná pouze v jedné číslici.
Obrázek 3.1: Rozdělení kruhu na
výsečí
(zdroj: VRBA, Antonín, ed. Princip matematické indukce. 1. vyd. Praha, 1977.)
38
Řešení Nejprve položíme
:
. Kruh je rozdělen na dvě výseče, kde do jedné výseče dáme
číslo 1 a do druhé výseče vložíme číslo 2. Dále budeme předpokládat, že platí
: do
výsečí rozmístíme k-ciferných čísel,
které jsou složeny z číslic 1 a 2. Každou z výsečí rozdělíme na dvě výseče. Do každé vzniklé výseče vložíme
-ciferné číslo, jehož prvních p číslic bude shodných s p-ciferným
číslem, které bylo ve výseči před rozdělením.
-tá číslice bude buď 1, anebo dle
Obrázku 3.2.
Obrázek 3.2: Rozdělení kruhu, kde je
-tá číslice 1 nebo 2
(zdroj: VRBA, Antonín, ed. Princip matematické indukce. 1. vyd. Praha, 1977.)
Každé vzniklé číslo se od sousedního liší od svého souseda z jedné strany v poslední číslici a z druhé strany v jedné z prvních p číslic. Pomocí matematické indukce se nám podařilo definovat pro každé přirozené číslo n dané rozdělení.
3.3 Neřešené úlohy o posloupnostech a řadách s využitím matematické indukce Úloha 3.3.1 Je dána posloupnost
, která je určena rekurentně
je přirozené číslo. Danou posloupnost
,
vyjádřete vzorcem pro n-tý člen. 39
, kde n
Úloha 3.3.2 Posloupnost
, která je dána rekurentně, vyjádřete vzorcem pro její n-tý člen.
Úloha 3.3.3 Najděte vzorec pro n-tý člen posloupnosti
, která je dána rekurentně .
Úloha 3.3.4 Najděte vzorec pro částečný součet
řady
Úloha 3.3.5 Najděte vzorec pro částečný součet
dané řady
40
Závěr V bakalářské práci jsme se seznámili s matematickými důkazy, jejich historií a druhy. Zaměřili jsme se na dokazování pomocí matematické indukce. Uvedli jsme si, že matematická indukce spolu s úplnou a neúplnou indukcí patří do induktivních postupů a vysvětlili jsme si, jaký je mezi nimi rozdíl. Dále jsme si uvedli princip matematické indukce. V poslední kapitole jsme se věnovali posloupnostem a řadám, kde je matematická indukce při dokazování využívána. Jelikož jsme chtěli vytvořit sbírku úloh s využitím matematické indukce, tak se v dané práci nachází spousta řešených i neřešených úloh. Úlohy jsou vhodné především pro studenty středních škol, ale spíše do hodin matematických seminářů, kde se nachází nadanější žáci na matematiku. Některé typy úloh jsou vhodné i pro vysokoškolské studenty a to především úlohy o posloupnostech a řadách, jelikož posloupnostem a řadám se věnuje matematická analýza. Dále Úloha 2.3.10 je z učiva diskrétní matematiky, která je také vyučována na vysoké škole. Bakalářská práce může sloužit středoškolským i vysokoškolským studentům jako opora při řešení úloh o matematické indukci. Při vytváření obrázků jsme použily programy Malování a MS Excel 2007.
41
Seznam symbolů +
operace sčítání
-
operace odčítání
·
operace násobení
=
rovná se
≠
nerovná se
≥
znaménko větší nebo rovno
≤
znaménko menší nebo rovno ě
é
nen dělitelné !
faktoriál platí pro vše existuje
ϵ
náleží
˄
konjunkce
=>
implikace
ekvivalence
N
přirozená čísla
42
Použitá literatura 1. BERAN, Ladislav. Prověřte si své matematické nadání. Vyd. 2. Praha, 1989. 2. Co je to důkaz. Matematika.cz [online]. 2013 [cit. 2015-04-12]. Dostupné z: http://www.matematika.cz/dukazy 3. JANUROVÁ, Eva a JANURA, Miroslav. Matematika: průvodce učivem základní a střední školy. 1. vyd. Olomouc: Rubico, 1999. 307 s. ISBN 80-85839-31-8. 4. LAITOCH, Miroslav. Posloupnosti a řady. 1/1. opr. vyd. Praha, 1966. 100 s. 5. LAITOCHOVÁ, Jitka. Matematická analýza I: diferenciální počet. 1. vyd. Olomouc: Univerzita Palackého, 2002- . sv. Skripta. ISBN 80-244-0591-1. 6. LAITOCHOVÁ, Jitka. Matematická analýza 1: diferenciální počet. 2., (upr.) vyd. Olomouc: Univerzita Palackého v Olomouci, 2007- . sv. Skripta. ISBN 978-80-2441739-4. 7. Matematický důkaz. Wikipedie [online]. 2010 [cit. 2015-04-15]. Dostupné z:http://cs.wikipedia.org/wiki/Matematick%C3%BD_d%C5%AFkaz
8. ODVÁRKO, Oldřich. Metody řešení matematických úloh. Vyd. 2., přeprac. Praha, 1986. 9. POLSTER, Burkard. Q.E.D.: krása matematického důkazu. 1. vyd. v českém jazyce. Praha: Dokořán, 2014. 58 s. Pergamen; sv. 12. ISBN 978-80-7363-532-9
10. ŘEHÁK, Pavel. Základy matematiky. 2014. Dostupné z: http://users.math.cas.cz/~rehak/soubory/zaklady_matematiky.pdf 11. THIELE, Rüdiger. Matematické důkazy. 2., nezm. vyd. Praha, 1986.
43
12. VRBA, Antonín, ed. Kombinatorika, pravdepodobnosť, matematická indukcia: Pre 2. roč. gymnázia so zameraním na matem. Vyd. 4. Bratislava, 1989. 13. VRBA, Antonín, ed. Princip matematické indukce. 1. vyd. Praha, 1977.
44
