Sumy a indukcia

[Martin Sleziak]

Napíšem niečo iba k úlohám na matematickú indukciu - ako som už spomínal, komentáre k úlohám na injekcie/surjekcie a skladanie sa dajú nájsť tu: viewtopic.php?t=493 a viewtopic.php?t=735

Zadania

Skupina A

Dokážte, že pre $n\in\mathbb N$ platí: $$\sum\limits_{k=0}^n 2^k=2^{n+1}-1.$$
(T.j. $1+2+\dots+2^n=2^{n+1}-1$.)

Skupina B

Dokážte, že pre $n\in\mathbb N$ platí: $$\sum\limits_{k=0}^n k!k=(n+1)!-1.$$
(T.j. $1!\cdot1+2!\cdot2+\dots+n!\cdot n=(n+1)!-1$.)

Ak ste zvedaví na písomky z minulých rokov, tak sa môžete pozrieť sem:
viewtopic.php?t=484
viewtopic.php?t=493
viewtopic.php?t=735

[Martin Sleziak]

Riešenia

Môžeme použiť postup, na ktorí sme zvyknutí pri indukcii - t.j. overíme pre $n=1$ a potom urobíme indukčný krok.

Skupina A:
$1^\circ$ Pre $n=1$ dostávame $2^0+2^1=1+2=3$ a $2^2-1=3$, čiže tvrdenie platí $n=1$.

$2^\circ$ Indukčný krok: Predpokladáme, že tvrdenie platí pre $n$ a upravíme
\begin{align*}
\sum\limits_{k=0}^{n+1} 2^k
&= \left(\sum\limits_{k=0}^n 2^k\right) + 2^{n+1}\\
&\overset{IP}= (2^{n+1}-1)+2^{n+1} \\
&=2^{n+1}+2^{n+1}-1 \\
&= 2\cdot2^{n+1}-1 \\
&= 2^{n+2}-1
\end{align*}
Zistili sme, že tvrdenie platí aj pre $n+1$.

Skupina B:
$1^\circ$ Pre $n=1$ dostávame $0\cdot0!+1\cdot1!=0+1=1$ a $2!-1=2-1=1$, teda tvrdenie platí pre $n=1$.

$2^\circ$ Indukčný krok: Predpokladáme, že tvrdenie platí pre $n$ a upravíme
\begin{align*}
\sum\limits_{k=0}^{n+1} k!k
&= \left(\sum\limits_{k=0}^{n} k!k\right) + (n+1)!(n+1) \\
&\overset{IP}= ((n+1)!-1)+(n+1)!(n+1) \\
&= (n+1)!(1+n+1)-1 \\
&= (n+1)!(n+2)-1 \\
&= (n+2)!-1
\end{align*}
Zistili sme, že tvrdenie platí aj pre $n+1$.

Keď už som vám hovoril niečo o teleskopických sumách, tak si všimnime, že by sme to mohli zapísať aj pomocou nich. (Dostaneme zhruba tie isté úpravy, ako vyššie. Vďaka tomu, že máme zadanú pravú stranu, tak vlastne nemusíme "hádať", akým spôsobom prepísať $k$-ty sčítanec ako rozdiel.)
Znovu zopakujem, že to je vlastne tiež dôkaz indukciou, len inak zapísaný.

Skupina A:
Ak využijeme tento vzťah (ktorý nie je ťažké overiť)
$$2^k=2^{k+1}-2^k$$
tak môžeme túto sumu prepísať ako
$$\sum\limits_{k=0}^n 2^k= 1+2+2^2+\dots+2^n = (2-1)+(2^2-2)+(2^3-2^2)+\dots+(2^{n+1}-2^n) = 2^{n+1}-1.$$
(Všetky členy okrem prvého a posledného vypadnú.)

Skupina B:
Ak využijeme túto rovnosť (ktorú nie je ťažké overiť) pre $k\ge1$:
$$k!k=(k+1)!-k!$$
tak môžeme túto sumu prepísať ako
$$\sum\limits_{k=0}^{n} k!k = 1!\cdot1+2!\cdot2+3!\cdot3+\dots+n!n = (2!-1!)+(3!-2!)+(4!-3!)+\dots+((n+1)!-n!)=(n+1)!-1.$$
(V prvej rovnosti sme vynechali člen $0!\cdot0$, ktorý je rovný nule. Navyše tento člen nevieme uvedeným spôsobom prepísať - resp. museli by sme si rozmyslieť, či vieme rozumne dodefinovať $(-1)!$. Opäť sa skoro všetky členy vykrátia.)

[Martin Sleziak]

Poznámka k ekvivalentným úpravám
Zápisy podobné ako tieto sa vyskytli vo viacerých písomkách (s tým, že tam bolo okomentované, čo ste robili alebo kde ste použili indukčný predpoklad):

\begin{align*}
1+2+\dots+2^n+2^{n+1} &= 2^{n+2}-1\\
2^{n+1}-1+2^{n+1} &= 2^{n+2}-1\\
2^{n+1}+2^{n+1} &= 2^{n+2}\\
2\cdot2^{n+1}&= 2\cdot2^{n+1}\\
0 &= 0
\end{align*}

Alebo

\begin{align*}
\sum\limits_{k=0}^{n+1} k!k &= (n+2)!-1\\
(n+1)!-1+(n+1)!(n+1) &= (n+2)!-1\\
(n+1)!+(n+1)!(n+1) &= (n+2)!\\
(n+1)!(n+2) &= (n+2)!
\end{align*}

Prísne vzaté, bez akéhokoľvek ďalšieho komentára to, čo je tu napísané, nie je správny dôkaz. (Nestrhával som vám body, chcem však, aby ste si uvedomili v čom je tu problém.)
Vlastne ste začali s tým, čo chcete dokázať a niečo z toho odvodili. Pri dôkaze naopak chceme nejako odvodiť práve tú rovnosť, ktorú ste napísali ako prvú.
Nemal by som žiadne námietky, ak by sa na konci objavilo napísané niečo ako: "Všetky použíté úpravy sú ekvivalentné, celý postup možno obrátiť." (Alebo ak by ste toto odvodenie napísali ešte raz - teraz v opačnom poradí. To čo je vyššie vám poslúžilo na objavenie odvodenia, keď to čítam odspodu nahor, tak to už vlastne je odvodenie rovnosti, ktorú sa snažíme dokázať.)
Treba si samozrejme aj rozmyslieť, či sú úpravy skutočne ekvivalentné. (Ak by ste použili úpravy, ktoré nie sú ekvivalentné, tak by ste takto mohli "dokázať" aj tvrdenia, ktoré neplatia.)

Mohlo sa začať pre $n=0$?
Aj keď v zadaní bolo napísané, že máme zadanie dokázať pre prirodzené čísla, bolo by úplne v poriadku, ak by ste začali tým, že overíte tvrdenie pre $n=0$ a potom pokračovali indukčný krok.
Vlastne by ste tak dokázali o máličko viac, než som sa pýtal v zadaní: Overili by ste, že to platí nielen pre prirodzené čísla, ale navyše aj pre nulu.

Rozdiel medzi $n$ a $k$

Podľa toho, čo ste sa pýtali po písomke, možno robilo trochu problém niečo takéto. Opäť citát z písomky:

Je tu trochu spor so zadaním, lebo sa píše, že $n\in\mathbb N$, ale vo vzorci v zadaní sa namiesto $n$ dosadila nula.

Skúsme si uvedomiť, že vo výraze $\sum\limits_{k=0}^n 2^k$ majú $k$ a $n$ rozličné úlohy.
Hodnota tohoto výrazu závisí iba od $n$. Premenná $k$ je premenná, cez ktorú sčitujeme. T.j. mám dosadiť za $k$ postupne hodnoty $0,1,\dots,n$ a výsledky sčítať. Čiže sa tam niekde vyskytne dosadenie nuly, ale dosadzujeme ju za $k$ a nie za $n$.

Možno trochu pomôže aj pohľad na inú úlohu - tzv. Bernouilliho nerovnosť:
Dokážte, že pre ľubovoľné reálne číslo $x\ge-1$ a nezáporné celé číslo $n$ platí $$(1+x)^n \ge 1+nx.$$
Túto nerovnosť by sme tiež mohli dokazovať indukciou vzhľadom na $n$. (Môžete si to vyskúšať, alebo sa pozrieť napríklad sem alebo do článku na Wikipédii, na ktorý je linka vyššie.)
To, že tam vystupuje ešte iná premenná $x$, ktorá je reálne číslo nás priveľmi nemusí trápiť. (Musíme dať pozor, či úvahy, ktoré robíme, sú platné pre reálne čísla z daného rozsahu. Ale nemusíme sa obávať toho, že tam je reálne číslo a pre reálne čísla indukcia nefunguje - indukčná premenná je $n$ a nie $x$.)

Tu je vzťah medzi $n$ a $x$ trochu iný ako vzťah medzi $n$ a $k$ v úlohe z písomky. Ale azda aj tento príklad mohol trochu objasniť veci, s ktorými ste tam (zdá sa) mali niektorí problém.

[Martin Sleziak]

Pokec k písomke pridám sem, keďže je veľmi podobná ako minule.

Zadania

Skupina A

Dokážte matematickou indukciou, že pre $n\in\mathbb N$ platí: $$\sum\limits_{k=0}^n k=\frac{n(n+1)}2.$$
(T.j. $0+1+2+\dots+n=\frac{n(n+1)}2$.)

Skupina B

Dokážte matematickou indukciou, že pre $n\in\mathbb N$ platí: $$\sum\limits_{k=0}^n (2k+1)=(n+1)^2.$$
(T.j. $1+3+5+\dots+(2n+1)=(n+1)^2$.)

Skupina C

Dokážte matematickou indukciou, že pre $n\in\mathbb N$ platí: $$\sum\limits_{k=0}^n 2k=n(n+1).$$
(T.j. $0+2+4+\dots+2n=n(n+1)$.)

Riešenia

Riešenia sú veľmi podobné na tie, ktoré sú uvedené vyššie.
Napíšem aspoň ako by vyzeral indukčný krok.

Skupina A:
$$\sum_{k=0}^{n+1} k = \sum_{k=0}^n k + (n+1) = \frac{n(n+1)}2 + (n+1) = (n+1)\left(\frac n2 + 1\right) = (n+1)\frac{n+2}2 = \frac{(n+1)(n+2)}2$$
Skupina B:
$$\sum_{k=0}^{n+1} (2k+1)=\sum_{k=0}^n (2k+1) + (2n+3)=(n+1)^2+(2n+3)=(n^2+2n+1)+(2n+3)=n^2+4n+4=(n+2)^2$$
Skupina C:
$$\sum_{k=0}^{n+1} 2k = \sum_{k=0}^n k + 2(n+1) = n(n+1) + 2(n+1) = (n+1)(n+2)$$

Alebo ak by sme indukčný krok robili tak, že dokazujeme: "ak rovnosť platí pre $(n-1)$, tak platí aj pre $n$".
Pri tejto zmene to vyzerá o čosi krajšie v skupine B - ale v podstate sú úpravy skoro rovnaké:
Skupina A:
$$\sum_{k=0}^n k = \sum_{k=0}^{n-1} k+n = \frac{(n-1)n}2 +n = n\left(\frac{n-1}2+1\right)=n\cdot\frac{n+1}2=\frac{n(n+1)}2$$
Skupina B:
$$\sum_{k=0}^n (2k+1) = \sum_{k=0}^{n-1} (2k+1) + (2n+1) = n^2+2n+1 = (n+1)^2 $$
Skupina C:
$$\sum_{k=0}^n 2k = \sum_{k=0}^{n-1} 2k + 2n= (n-1)n + 2n = n(n+1)$$


Chyby, ktoré sa vyskytovali v odovzdaných riešeniach
Väčšina riešení bola fajn.
Platí poznámka, ktorú som napísal k minuloročnej písomke - niekedy sa oplatí zdôrazniť, že použité úpravy boli ekvivalentné.
Azda sa v indukčnom kroku oplatilo pozrieť, či sa dá niečo vyňať - namiesto toho aby ste všetko roznásobovali. (Úpravy sa tým trochu zjednodušia.)

Zopakujem, že zápis $\sum\limits_{k=0}^n a_n$ označuje súčet $a_0+a_1+\dots+a_n$. Niektorí ste indukčný krok napísali tak, ako keby to bolo iba $a_n$.
Napríklad v skupine B ste v indukčnom kroku napísali rovnosť

$$2n+3=(n+2)^2.$$

Táto rovnosť vo všeobecnosti neplatí - takže sa vám ju samozrejme ani nepodarilo dokázať pre všetky kladné celé čísla $n$.

[Martin Sleziak]

Platí poznámka, ktorú som napísal k minuloročnej písomke - niekedy sa oplatí zdôrazniť, že použité úpravy boli ekvivalentné.
Azda sa v indukčnom kroku oplatilo pozrieť, či sa dá niečo vyňať - namiesto toho aby ste všetko roznásobovali. (Úpravy sa tým trochu zjednodušia.)

Zopakujem, že zápis $\sum\limits_{k=0}^n a_n$ označuje súčet $a_0+a_1+\dots+a_n$. Niektorí ste indukčný krok napísali tak, ako keby to bolo iba $a_n$.
Napríklad v skupine B ste v indukčnom kroku napísali rovnosť

$$2n+3=(n+2)^2.$$

Táto rovnosť vo všeobecnosti neplatí - takže sa vám ju samozrejme ani nepodarilo dokázať pre všetky kladné celé čísla $n$.

Tieto veci, ktoré som písal minule, môžem zopakovať aj v súvislosti s niektorými riešeniami, ktoré sa objavili teraz.

Ešte spomeniem, že niektorí ste napísali, že v indukčnom kroku dokazujete: "Ak tvrdenie platí pre $(n+1)$, tak platí pre $n$."
Je to presne naopak - v indukčnom kroku sa z platnosti tvrdenia pre $n$ snažíme odvodiť platnosť tvrdenia pre $(n+1)$. (Samozrejme, dá sa použiť aj to, že od $(n-1)$ ideme k $n$.)
Nestŕhal som ale žiadne body ľuďom, ktorí napísali niečo takéto - keďže zvyšok riešenia bol vo všetkých písomkách, kde sa to vyskytlo správny. (T.j. aj postup bol taký, že ste z rovnosti pre $n$ odvodzovali rovnosť pre $(n+1)$; akurát ste k indukčnému kroku napísali komentár, ktorý tvrdil že to robíte opačným smerom.)

[Martin Sleziak]

K riešeniam, ktoré som dostal, som nikde nemal žiadne podstatné výhrady. Zopakujem dve veci, ktoré sú napísané aj vyššie:
* Je úplne legitímne začať s $n=0$. (Prinajmenšom v prípade, že dokazované tvrdenie má zmysel pre $n=0$.)
* Častom som videl postupnosť rovností takú, že sa dostaneme od dokazovanej rovnosti k niečomu, čo určite platí. Vtedy je dôležité aj to, či sú úpravy ekvivalentné, resp. či sa dajú otočiť.

Napíšem teda aspoň stručne riešenia.

Dokážte matematickou indukciou, že pre $n\in\mathbb N$ platí: $$\sum\limits_{k=1}^n \frac1{2^k}=1-\frac1{2^n}.$$
(T.j. $\frac12+\frac1{2^2}+\dots+\frac1{2^n}=1-\frac1{2^n}$.)

$1^\circ$ Pre $n=1$ máme $\frac12=1-\frac12$, čo skutočne platí.

$2^\circ$ Predpokladáme, že tvrdenie platí pre $n$ pomocou toho pre $n+1$ vieme dostať
\begin{align*}
\sum\limits_{k=1}^{n+1} \frac1{2^k}
&=\sum\limits_{k=1}^n \frac1{2^k} + \frac1{2^{n+1}}\\
&\overset{IP}=1-\frac1{2^n}+\frac1{2^{n+1}}\\
&=1-\frac1{2^{n+1}}
\end{align*}

Samozrejme, pri tejto úlohe vidno, že to je špeciálny prípad vzorca pre súčet prvých $n$ členov geometrickej postupnosti, ktorý by sme mali poznať. (A ktorý sa tiež odvodí matematickou indukciou.)

Dokážte matematickou indukciou, že pre $n\in\mathbb N$ platí: $$\sum_{i=1}^n \frac{i}{(i+1)!}=1- \frac{1}{(n+1)!}.$$
(T.j. $\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\cdots+\frac{n}{\left(n+1\right)!} = 1-\frac{1}{\left(n+1\right)!}$.)

Ak to náhodou pomôže tým, ktorí nie sú zvyknutí na zápis pomocou $\sum$, tak tu indukčný krok rozpíšem inak.

$1^\circ$ Pre $n=1$ dostávame rovnosť $\frac1{2!}=1-\frac1{2!}$, ktorá skutočne platí.

$2^\circ$ Ak predpokladáme, že táto rovnosť platí pre $n$, tak pre $n+1$ dostaneme
\begin{align*}
\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\cdots+\frac{n}{(n+1)!}+\frac{n+1}{(n+2)!}
&=\left(\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\cdots+\frac{n}{(n+1)!} \right)+\frac{n+1}{(n+2)!}\\
&\overset{IP}= 1-\frac{1}{n+1)!}+\frac{n+1}{(n+2)!}\\
&= 1-\frac{n+2}{(n+2)!}+\frac{n+1}{(n+2)!}\\
&= 1-\frac{1}{n+2)!}
\end{align*}