Product representation for second order linear recurrences

[lel0lel]

Пусть $\{W_k(A,B;P,-Q)\}$ линейная рекуррентная последовательность второго порядка: $W_0=A, W_1=B, W_k=P W_{k-1}-QW_{k-2}.$
Покажите что

$$W_k=B\prod\limits_{j=1}^{k-1}\left(P+2\sqrt{Q}\cos\frac{\pi j}{k}\right)-AQ\prod\limits_{j=1}^{k-2}\left(P+2\sqrt{Q}\cos\frac{\pi j}{k-1}\right),\,\,\, k\geq 2.$$

[nnosipov]

Так, навскидку, кажется, что произведения связаны с многочленами Чебышева 1-го рода. Ну а появление многочленов Чебышева в линейных рекурренциях 2-го порядка неудивительно.

[TOTAL]

План. При $A=0$ найти выражение для $W_k=ut_1^k+vt_2^k$, где $t_1, t_2$ - корни характеристического многочлена. Выражение для $W_k$ будет полиномом от $P$. Затем подстановкой убедиться, что корни этого полинома равны $-2\sqrt{Q}\cos\frac{\pi j}{k}$.

[ozheredov]

lel0lel

Затая дыхание, жду, когда Вы покажете доказательство.

P.S. У меня была мысль, что надо представить косинус в виде полусуммы комплексных экспонент. Тогда при перемножении в некоторых показателях оных экспонент будет арифметическая прогрессия и с божьей помощью накопится фаза $\pi n$, что переведет экспоненту на действительную ось. Но, по-видимому, помешают перекрестные члены, да?

[lel0lel]

ozheredov
Я немного позже выложу своё доказательство. Пока приведу ссылку на статью, в которой этот результат доказан. Там используется известный результат о нулях полиномов Чебышева, но можно обойтись и без него, получится даже проще. Factorizations_and_representations_of_second_order_linear_recurrences_with_indices_in_arithmetic_progressions Это не первая бумага, в которой получен этот результат.

[TOTAL]

$\displaystyle W_0=0, \;\; W_1=1. $
Тогда $\displaystyle W_k=\frac{t_2^k-t_1^k}{t_2-t_1},$ где $\displaystyle t_1=\frac{P-\sqrt{P^2-4Q}}{2}, \; t_2=\frac{P+\sqrt{P^2-4Q}}{2}$
При $\displaystyle P_j = -2\sqrt{Q}\cos\frac{\pi j}{k}$ получаем $\displaystyle t_{1j}=-\sqrt{Q}e^{\pi i j/k}, \; t_{2j}=-\sqrt{Q}e^{-\pi ij/k}$,
т.е. $\displaystyle P_j$ являются корнями многочлена $\displaystyle W_k(P)$.
Чем это не доказательство?

[lel0lel]

TOTAL
Всё так, лаконичней не придумать!

[ozheredov]

TOTAL
При $\displaystyle P^2 < 4Q$ значения $\displaystyle t_1$ и $\displaystyle t_2$ будут комплексными и таким же будет в общем случае $\displaystyle W_k=\frac{t_2^k-t_1^k}{t_2-t_1}$ (почему нет?)

TOTAL в сообщении #1527279 писал(а):

При $\displaystyle P_j = -2\sqrt{Q}\cos\frac{\pi j}{k}$

Откуда это?

P.S. Как я понял, основная идея состояла в представлении общего члена последовательности как полинома от одного из "рекуррентных" коэффициентов и факторизации этого полинома через его корни. Но ведь в формуле не одно произведение, а два.

[xagiwo]

ozheredov в частном случае ($A = 0$) одно из слагаемых обнуляется. А общий уже выводится из этого частного

-- 27.07.2021, 14:53 --

ozheredov в сообщении #1527330 писал(а):

При $\displaystyle P^2 < 4Q$ значения $\displaystyle t_1$ и $\displaystyle t_2$ будут комплексными и таким же будет в общем случае $\displaystyle W_k=\frac{t_2^k-t_1^k}{t_2-t_1}$

$t_2$ и $t_1$ будут комплексно сопряжёнными, а потому $\displaystyle W_k=\frac{t_2^k-t_1^k}{t_2-t_1}$ — вещественным

[ozheredov]

xagiwo в сообщении #1527331 писал(а):

$t_2$ и $t_1$ будут комплексно сопряжёнными, а потому $\displaystyle W_k=\frac{t_2^k-t_1^k}{t_2-t_1}$ — вещественным

блин, точно.

А тогда последний вопрос: косинус в

TOTAL в сообщении #1527279 писал(а):

$\displaystyle P_j = -2\sqrt{Q}\cos\frac{\pi j}{k}$

видимо возникает как полусумма комплексно сопряженных экспонент. А если все же $\displaystyle P^2 \geqslant 4Q$ и корни действительные?

[xagiwo]

ozheredov как я понял, в решении TOTAL $P_j$ возникает как штука, которая должна обнулять $W_k(P)$, чтобы оно было равно многочлену из условия (в 3-м сообщении темы ещё что-то такое было)

[TOTAL]

ozheredov в сообщении #1527335 писал(а):

А если все же $\displaystyle P^2 \geqslant 4Q$ и корни действительные?

$P$ - это переменный аргумент в рассуждениях, он любой действительный.