Virkne \(\left(x_{n}\right)\) definēta rekurenti: \(x_{1}=1,\ x_{2}=-3,\ x_{3}=-29\) un \(x_{n+3}=9x_{n+2}-26x_{n+1}+24x_{n}\) visiem naturāliem \(n\). Pierādīt, ka \(x_{n}=2^{n}+3^{n}-4^{n}\) visiem naturāliem \(n\).
Izmantossim matemātiskās indukcijas metodi.
Indukcijas bāze. Ja \(n=1\), tad \(x_{1}=2^{1}+3^{1}-4^{1}=1\). Ja \(n=2\), tad \(x_{2}=2^{2}+3^{2}-4^{2}=-3\). Ja \(n=3\), tad \(x_{3}=2^{3}+3^{3}-4^{3}=-29\).
Induktīvais pieņēmums. Pieņemsim, ka formula ir spēkā, ja \(n=k, n=k+1\) un \(n=k+2\), tas ir,
\(x_{k}=2^{k}+3^{k}-4^{k}, \quad x_{k+1}=2^{k+1}+3^{k+1}-4^{k+1} \quad \) un \(\quad x_{k+2}=2^{k+2}+3^{k+2}-4^{k+2}\)
Induktīvā pāreja. Pierādīsim, ka formula ir spēkā arī tad, ja \(n=k+3\), tas ir, \(x_{k+3}=2^{k+3}+3^{k+3}-4^{k+3}\). Izmantojot induktīvo pieņēmumu, iegūstam
\[\begin{gathered} x_{k+3}=9x_{k+2}-26x_{k+1}+24x_{k}= \\ =9\left(2^{k+2}+3^{k+2}-4^{k+2}\right)-26\left(2^{k+1}+3^{k+1}-4^{k+1}\right)+24\left(2^{k}+3^{k}-4^{k}\right)= \\ =2^{k}(9 \cdot 4-26 \cdot 2+24)+3^{k}(9 \cdot 9-26 \cdot 3+24)-4^{k}(9 \cdot 16-26 \cdot 4+24)= \\ =2^{k} \cdot 8+3^{k} \cdot 27-4^{k} \cdot 64=2^{k+3}+3^{k+3}-4^{k+3} \end{gathered}\]
*Secinājums.* Tā kā formula ir patiesa, ja \(n=1, n=2\) un \(n=3\), un no tā, ka formula ir spēkā, ja \(n=k\), \(n=k+1\) un \(n=k+2\), izriet, ka formula ir spēkā arī \(n=k+3\), secinām, ka formula ir spēkā visām naturālām \(n\) vērtībām.