Районная олимпиада, 2006-2007 учебный год, 10 класс

Дана последовательность целых чисел $a_1, a_2, \ldots ,a_{2007}$, для которой справедливо $a_1=1$, $a_2=3$ и при любых натуральных $2\leq n \leq 2006$ выполняется равенство $a_{n+1}=3a_n-2a_{n-1}$. Найдите $a_{2007}$.

Комментарий/решение

$$ 1\cdot a_1 = 1$$

$$ z \cdot a_2 =3z$$

$$ z^n\cdot a_{n+1}=(3a_n-2a_{n-1})\cdot z^n$$

$$ \sum_{n=2}^{\infty}a_{n+1}\cdot z^n= \sum_{n=2}^{\infty}(3a_n-2a_{n-1})\cdot z^n$$

$$ f(z)=a_1+a_2z+\sum_{n=2}^{\infty}a_{n+1}\cdot z^n=1+3z +\sum_{n=2}^{\infty}(3a_n-2a_{n-1})\cdot z^n$$

$$ f(z)=1+3z+3\sum_{n=2}^{\infty}a_nz^n-2\sum_{n=2}^{\infty}a_{n-1}z^n$$

$$ 3\sum_{n=2}^{\infty}a_nz^n=3z\sum_{n=2}^{\infty}a_nz^{n-1}=3z(a_2z+a_3z^2+...)=3z(-a_1+\underbrace{a_1+a_2z+...}_{f(z)})=3zf(z)-3z$$

$$\sum_{n=2}^{\infty}a_{n-1}z^n=z^2\sum_{n=2}^{\infty}a_{n-1}z^{n-2}=z^2(\underbrace{a_1+a_2z+...}_{f(z)})=z^2f(z)$$

$$ f(z)=1+3z+3zf(z)-3z-2z^2f(z)\Rightarrow f(z)=\frac{1}{2z^2-3z+1}$$

$$ f(z)=\frac{1}{2z^2-3z+1}= \frac{-1}{1-z}+\frac{2}{1-2z}$$

$$ \frac{1}{1-z}=\sum_{n=0}^{\infty} z^n \Rightarrow \frac{1}{1-2z}=\sum_{n=0}^{\infty}2^n z^n $$

$$f(z)=\sum_{n=0}^{\infty}(2^{n+1}-1)z^n=\sum_{n=1}^{\infty}(2^{n}-1)z^n=\sum_{n=1}^{\infty}a_nz^n$$

$$ a_n=2^n-1\Rightarrow a_{2007}=2^{2007}-1$$

$$\color{red}{\underline{\textbf{Определение 1.1.}}}\color{blue}{\text{Характеристическим многочленом ЛОРУ}}$$

$$x_{n+k}+p_{k-1}x_{n+k-1}+...+p_1x_{n-1}+p_0x_n=0$$

$$\color{blue}{\text{называется многочлен комплексной переменной}}$$

$$ Q(\lambda)=\lambda^k+p_{k-1}\lambda^{k-1}+...+p_1x+p_0$$

$$ \color{red}{\underline{\textbf{Лемма 1.1.}}}\color{blue}{\text{Пусть $\color {black}{\lambda}$ – корень характеристического многочлена $\color {black}{Q(\lambda)}$ . Тогда последовательность $\color {black}{\left\{\lambda^n\right\}}$ является частным решением этого ЛОРУ.}}$$

$$ \color{red}{\underline{\textbf{Теорема 1.1.}}}\color{blue}{\text{Пусть $\color {black}{\lambda_1,\lambda_2,...,\lambda_k}$– корни характеристического многочлена $\color {black}{Q(\lambda)}$ . Тогда общее решение этого уравнения имеет вид}}$$

$$ \left\{C_1\lambda^n_1+C_2\lambda^n_2+...+C_k\lambda^n_k\right\}$$

$$ \color{blue}{\text{где $\color {black}{С_1,С_2,...,С_k}$- комплексные числа}}$$

\\

$$a_{n+1}-3a_n+2a_{n-1}=0$$

$$ a_{(n-1)+2}-3a_{(n-1)+1}+2a_{n-1}=0, \quad n\geq2$$

$$Q(\lambda)=\lambda^2-3\lambda+2=0$$

$$ \lambda_1=2 \quad \lambda_2=1$$

$$ a_{n-1}=C_1 2^n+C_2 1^n=C_1 2^n+C_2$$

$$ \begin{cases} a_1=a_{2-1}=4C_1+C_2=1 \\ a_2=a_{3-1}=8C_1+C_2=3 \end{cases}\Rightarrow $$

$$\Rightarrow C_1=\frac{1}{2} ,\quad C_2=-1$$

$$ a_{n-1}=\frac{1}{2}\cdot 2^n-1=2^{n-1}-1$$

$$ a_n=2^n-1\Rightarrow a_{2007}=2^{2007}-1$$