рекуррентная функция

[tetricka12]

Увидел на одной олимпиаде задание.

Данная функция$ f:R ->R$ такая что для любого $ x\in R$

$f(x+2) + \alpha f(x) = f(x+1)$ ,где $\alpha = \frac{3+\sqrt{5}}{2}$, а $f(3) =2013$

Если бы было известно 2 значения а не одно, то можно было бы сделать таким образом:
$f(n) = C_1r_1^n + C_2r_2^n $ , где $r_1 , r_2 $
корни уравнения $ r^2 -r +\alpha = 0 $
$f(0) = C_1 + C_2 $
$f(1) = C_1r_1 + C_2r_2$
и найти константы.
А тут известно только $f(3) = 2013$, не знаю, как найти константы.
в этом задании корни получились комплексные, и в общем виде получилось:
$f(n) = C_1r^n\cos(\frac{-2\pi n}{5}) + C_2r^n\sin(\frac{-2\pi n}{5}) $
где $r = \sqrt{ \frac{\sqrt{5} +3}{2}}$
Как надо действовать дальше? Может быть необязательно надо было решать и можно было бы сделать хитрее?

P.S. ответ не интересует, интересует только решение.

[svv]

tetricka12 в сообщении #1476339 писал(а):

Данная функция $f:R\to R$ такая что для любого $x \in R$
$f(x+2) + \alpha f(x) = f(x+1)$ ,где $\alpha = \frac{3+\sqrt{5}}{2}$, а $f(3) =2013$

Понятно. А в чём задание? что надо найти, или что доказать, или на какой вопрос ответить?

[tetricka12]

svv в сообщении #1476342 писал(а):

tetricka12 в сообщении #1476339 писал(а):

Данная функция $f:R\to R$ такая что для любого $x \in R$
$f(x+2) + \alpha f(x) = f(x+1)$ ,где $\alpha = \frac{3+\sqrt{5}}{2}$, а $f(3) =2013$

Понятно. А в чём задание? что надо найти, или что доказать, или на какой вопрос ответить?

Прошу прощения за этот недочёт.
Надо найти f(2013)

[svv]

tetricka12 в сообщении #1476339 писал(а):

$f(n) = C_1r^n\cos(\frac{-2\pi n}{5}) + C_2r^n\sin(\frac{-2\pi n}{5}) $

Минусы можно убрать — просто убрать из-под косинуса и включить в $C_2$ в случае синуса.

Посмотрите, а что такое будет $f(n+5)$ ?

[Евгений Машеров]

Поскольку вспомогательное уравнение действительное - корни комплексно сопряжённые. Как и их степени.
Поскольку рекуррентное уравнение принимает действительные значения, то $C_1$ и $C_2$...

[tetricka12]

svv в сообщении #1476344 писал(а):

tetricka12 в сообщении #1476339 писал(а):

$f(n) = C_1r^n\cos(\frac{-2\pi n}{5}) + C_2r^n\sin(\frac{-2\pi n}{5}) $

Минусы можно убрать — просто убрать из-под косинуса и включить в $C_2$ в случае синуса.

Посмотрите, а что такое будет $f(n+5)$ ?

Ну это понятно, просто написал более в общем виде.

Была идея найти константы таким образом:
для n=5k ,
мы получаем:
$f(n) = C_1r^n$
и выразить $a_{10}$ через $a_3$ и $ a_5$
$a_{10} = a_9 -\alpha a_8 = a_5(f_1(\alpha)) + a_3(f_2(\alpha))$
$a_{10} = C_1r^{10}$
$a_{5} = C_1r^5$
$a_{3} = 2013$
и отсюда найти константу.
И далее как-то ... не знаю, еще не придумал

-- 28.07.2020, 11:27 --

Евгений Машеров в сообщении #1476365 писал(а):

Поскольку вспомогательное уравнение действительное - корни комплексно сопряжённые. Как и их степени.
Поскольку рекуррентное уравнение принимает действительные значения, то $C_1$ и $C_2$...

К сожалению, пока не понятно:)

[RIP]

tetricka12 в сообщении #1476370 писал(а):

Была идея найти константы

Найти константы невозможно: недостаточно данных. Но для ответа на вопрос это и не нужно. Как Вам намекают, попробуйте сравнить $f(n+5)$ и $f(n)$. Или можно действовать в лоб. У Вас есть условие $f(3)=2013$. С помощью него выразите $C_2$ через $C_1$ и подставьте в $f(2013)$.

[alisa-lebovski]

Цитата:

Была идея найти константы таким образом: для $n=5k$

Вам надо взять $n=5k+3$. Они отличаются множителем.

[tetricka12]

RIP в сообщении #1476372 писал(а):

tetricka12 в сообщении #1476370 писал(а):

Была идея найти константы

Найти константы невозможно: недостаточно данных. Но для ответа на вопрос это и не нужно. Как Вам намекают, попробуйте сравнить $f(n+5)$ и $f(n)$. Или можно действовать в лоб. У Вас есть условие $f(3)=2013$. С помощью него выразите $C_2$ через $C_1$ и подставьте в $f(2013)$.

Правильно ли я понимаю, что
$f(n+5) = r^5 f(n) $
и
$f(2013) = r^{2010}f(3)$
и отсюда сразу можно найти ответ?

Или где-то есть ошибка в рассуждениях?

[alisa-lebovski]

По-моему, правильно.

[tetricka12]

alisa-lebovski в сообщении #1476377 писал(а):

По-моему, правильно.

Да вроде тоже кажется что правильно. Но мало ли, не учел чего-то или опечатка или еще что.

[tetricka12]

СПАСИБО ВСЕМ!)

-- 28.07.2020, 17:01 --

СПАСИБО ВСЕМ!)

[svv]

tetricka12
Мне захотелось решить задачу без использования тригонометрических функций и даже, по возможности, обойтись без квадратных корней. Вот что получилось.

Из формулы для $\alpha$ видно, что эта величина удовлетворяет квадратному уравнению
$\alpha^2-3\alpha+1=0$
Рекуррентную формулу можно записать в матричном виде:
$\begin{bmatrix}f_{n+2}\\f_{n+1}\end{bmatrix}=\begin{bmatrix}1&-\alpha\\1&0\end{bmatrix}\begin{bmatrix}f_{n+1}\\f_n\end{bmatrix}$
Применяя эту формулу $k$ раз, получим
$\begin{bmatrix}f_{n+k+1}\\f_{n+k}\end{bmatrix}=\begin{bmatrix}1&-\alpha\\1&0\end{bmatrix}^k\begin{bmatrix}f_{n+1}\\f_n\end{bmatrix}$

С помощью Wolfram Alpha я нашёл вторую, третью и четвёртую степень матрицы. (Можно было уже сразу 2010-ю, но это как-то совсем нечестно.) Четвёртая степень оказалась равной
$\begin{bmatrix}\alpha^2-3\alpha+1&\alpha(2\alpha-1)\\\ldots&\ldots\end{bmatrix}$
Левый верхний элемент равен $0$, а это значит, что
$f_{n+5}=0f_{n+1}+\alpha(2\alpha-1) f_n$

[alisa-lebovski]

svv, но во-первых, это была олимпиадная задача, а не компьютерная, а во-вторых, Вы ее решили перебором, до 4-ой степени, а если бы понадобилось больше, ведь по $\alpha$ это не видно, а из тригонометрической записи нужный шаг 5 сразу виден.

Тут интереснее поставить вопрос, при каких еще $\alpha$ (например, вида $(a+b\sqrt{m})/c, где $a, b, c, m$ - целые) и соответственно величинах шага наблюдается подобный эффект?

[svv]

alisa-lebovski в сообщении #1476421 писал(а):

Вы ее решили перебором, до 4-ой степени, а если бы понадобилось больше, ведь по $\alpha$ это не видно

Да, это слабое место моего решения.