Príklady na indukciu

[Martin Sleziak]

V oboch skupinách bol príklad na indukciu taký úplne štandardný - vlastne sa dá mechanicky použiť postup, ktorý sme už veľakrát videli; dosadím to čo mám z indukčného predpokladu a upravujem.

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

Riešenie.
Báza indukcie. Overíme, že to platí pre $n=0$ (vtedy máme $0=0$). Prípadne pre $n=1$ (vtedy máme $1=2!-1$.)

Spoiler:

Samozrejme môžeme to prekontrolovať aj pre viac hodnôt.
$$
\begin{array}{c|c|c|c}
n & n\cdot n! & \sum\limits_{k=0}^n k\cdot k! & (n+1)!-1 \\\hline
0 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 \\
2 & 4 & 5 & 5 \\
3 &18 &23 &23 \\
4 &96 &119&120
\end{array}
$$

Indukčný krok. Predpokladáme, že $\sum\limits_{k=0}^n k\cdot k!=(n+1)!-1$. Potom dostaneme
\begin{align*}
\sum\limits_{k=0}^{n+1} k\cdot k! &= \left(\sum\limits_{k=0}^n k\cdot k!\right) + (n+1)!(n+1) \\
&\overset{IP}=(n+1)!-1+(n+1)!(n+1) \\
&=(n+1)!(n+2)-1\\
&=(n+2)!-1
\end{align*}

Tým je overený indukčný krok a vlastne aj celé tvrdenie. $\square$

Dokážte, že pre celé číslo $n\ge1$ 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)!}$.)

Riešenie.
Báza indukcie. Overíme, že to platí pre $n=0$ (vtedy máme $0=1-1$). Prípadne pre $n=1$ (vtedy máme $\frac12=1-\frac12$.)

Spoiler:

Samozrejme môžeme to prekontrolovať aj pre viac hodnôt.
$$
\begin{array}{c|c|c|c}
n & \frac{n}{(n+1)!} & \sum\limits_{k=0}^n \frac k{(k+1)!} & 1-\frac1{(k+1)!} \\\hline
0 & 0 & 0 & 0 \\
1 & \frac12 & \frac12 & \frac12 \\
2 & \frac13 & \frac56 & \frac56 \\
3 & \frac18 & \frac{23}{24} & \frac{23}{24} \\
4 & \frac1{30} & \frac{119}{120} & \frac{119}{120} \\
\end{array}
$$

Indukčný krok. Predpokladáme, že $\sum\limits_{i=1}^n \frac{i}{(i+1)!}=1- \frac{1}{(n+1)!}$. Potom dostaneme
\begin{align*}
\sum_{i=1}^{n+1} \frac{i}{(i+1)!} &= \left(\sum_{i=1}^n \frac{i}{(i+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{(n+2)-(n+1)}{(n+2)!}\\
&=1-\frac1{(n+2)!}
\end{align*}

[Martin Sleziak]

Chyby, ktoré sa vyskytovali v riešeniach

Často ste napísali riešenie tak, že ste najprv napísali to, čo ste chceli ukázať, a potom ste pokračovali niekoľkými riadkami, až kým ste sa nedostali k nejakej rovnosti, ktorá platí.
Takýto postup je úplne v poriadku, ak sú uvedené úpravy ekvivalentné. Patrilo by sa však do riešenia napísať, že použité úpravy naozaj boli ekvivalentné alebo že postup treba čítať zdola nahor (a rozmyslieť si, čo to tak je).

Body som za to nestŕhal, píšem to sem najmä preto, aby ste si to uvedomili. Malo by byť jasné, že ak chcem nejaké tvrdenie odvodiť, tak nemôžem začať tým, že používam to, čo sa vlastne snažím dokázať.

Nesprávny sčítanec

Ak robíme indukčný krok tak ako som napísal v riešení vyššie, t.j. od $n$ k $n+1$, tak treba pripočítavať člen v sume, ktorý dostaneme pre $k=n+1$.
(Indukčný krok môžeme robiť aj od $(n-1)$ k $n$, čo by znamenalo, že suma končí pri $n-1$ a pripočítavame člen pre $k=n$.)

V písomkách sa vyskytli rôzne veci, napríklad v skupine B niekto pripočítaval k doterajšej sume $\frac1{(n+1)!}$.

Treba robiť aj indukčný krok
Našli sa aj ľudia, ktorí v písomke overili, že tvrdenie platí pre niekoľko malých čísel. (Napríklad pre $n=1,2,3,4,5$.)
A potom už iba prehlásili, že to potom platí pre všetky prirodzené čísla.

Problémy s úpravami výrazov

Zdá sa, že sa občas vyskytnú problémy s obyčajnými úpravami zlomkov.$\require{cancel}$

Napríklad sa vyskytlo:

$1-\frac1{\cancel{(n+1)!}}+\frac{\cancel{(n+1)}}{(n+2)!}=1-\frac1{(n+2)!}$

V prvom rade to vyzerá, ako keby ste krátili rôzne výrazy, $(n+1)$ a $(n+1)!$. Navyše takto môžeme krátiť pri násobení, nie pri sčitovaní.

Iný nesprávny typ úpravy, ktorý sa vyskytol bol takýto:

$(k+1)\cdot(k+1)!=((k+1)^2)!$

Faktoriál sa nedá takto "roznásobiť". Vo všeobecnosti neplatí $a(n!)=(an)!$.