Dota virkne \(x_1=19,\;x_2=95,\;x_{n+2}=\mbox{LKD}(x_{n+1},x_n)+x_n\), ja \(n \geq 1\). Atrast skaitļu \(x_{1995}\) un \(x_{1996}\) lielāko kopīgo dalītāju.
Ar indukciju pierādīsim, ka \(\operatorname{LKD}\left(x_{k-1}, x_{k}\right)=19\). Ja \(k=3, \operatorname{tad} \operatorname{LKD}\left(x_{k-1}, x_{k}\right)=\operatorname{LKD}(95,114)=19\).
Pien̦emsim, ka apgalvojums izpildās, ja \(k=n\); pierādīsim, ka apgalvojums izpildās, ja \(k=n+1\). Tātad \(x_{n-1}=19a\), \(x_{n}=19b\), \((a, b)=1\). No šejienes seko
\[\left(x_{n}, x_{n+1}\right)=(19 b, 19(b+1))=19.\]
Apgalvojums pierādīts. ## Skaitļa n daudzkārtņu skaits intervālā **Teorēma (par daudzkārtņu skaitu intervālā):** Starp pirmajiem \(m\) naturālajiem skaitļiem ir tieši \(\left\lfloor \frac{m}{n}\right\rfloor\) skaitla \(n\) daudzkārtņu. *Pierādījums.* Skaiț̣a \(n\) daudzkārtņi, kas nepārsniedz \(m\) ir uzrakstāmi formā \(1 \cdot n, 2 \cdot n, \ldots, k \cdot n\), turklāt \(kn \leq m\) un \((k+1)n > m\). Šādu daudzkārtṇu skaits ir \(k\). Pārveidojot nevienādības, iegūstam \(k \leq \frac{m}{n}<k+1\). Tātad \(k=\left\lfloor \frac{m}{n} \right\rfloor\).