Virkne uzdota rekurenti ar formulu \(x_{n+2}=3 x_{n+1}-2 x_{n}-1\), kur \(x_{1}=3\) un \(x_{2}=6\). Pierādīt, ka virkni var definēt ar formulu \(x_{n}=2^{n}+n\).
Izmantosim matemātiskās indukcijas metodi.
Indukcijas bāze. Ja \(n=1\), tad \(x_{1}=2^{1}+1=3\). Ja \(n=2\), tad \(x_{2}=2^{2}+2=6\).
Induktīvais pieņēmums. Pieṇemsim, ka vienādība izpildās, ja \(n=k\) un \(n=k+1\), tas ir,
\[\begin{gathered} x_{k}=2^{k}+k \\ x_{k+1}=2^{k+1}+k+1 \end{gathered}\]
*Induktīvā pāreja.* Pierādīsim, ka vienādība ir spēkā arī tad, ja \(n=k+2\), tas ir, \(x_{k+2}=2^{k+2}+k+2\). Pārveidojam doto rekurences formulu\[\begin{gathered} x_{k+2}=3 x_{n+1}-2 x_{n}-1=3\left(2^{k+1}+k+1\right)-2\left(2^{k}+k\right)-1= \\ =3 \cdot 2 \cdot 2^{k}+3 k+3-2 \cdot 2^{k}-2 k-1=4 \cdot 2^{k}+k+2=2^{k+2}+k+2 \end{gathered}\]
*Secinājums.* Tā kā vienādība ir patiesa, ja \(n=1\) un \(n=2\), un no tā, ka vienādība ir spēkā, ja \(n=k\) un \(n=k+1\), izriet, ka vienādība ir spēkā arī \(n=k+2\), secinām, ka formula ir spēkā visām naturālām \(n\) vērtībām.