2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Помогите решить рекуррентное соотношение.
Сообщение04.12.2013, 22:57 
Помогите, пожалуйста, найти общую формулу для следующей рекуррентки.
$$a_k = \dfrac {a_{k-1} + 2^l(p-1)}{p}$$
Сам до этого с ними почти не встречался, не знаю, как подступиться.

 
 
 
 Re: Помогите решить рекуррентное соотношение.
Сообщение04.12.2013, 23:04 
Аватара пользователя
Попробуйте сделать замену $a_k=b_k+c$, причем $c$ подберите так, чтобы в уравнении исчез свободный член.

 
 
 
 Re: Помогите решить рекуррентное соотношение.
Сообщение05.12.2013, 00:14 
Я делаю замену следующим образом $b_k = a_k + c$, где $c = 2^l(p-1)$. Отсюда получаю: $b_k  -  c = \dfrac{b_{k-1}}{p}$.
Решая последнее, получаю \begin{multline}
b_k = \dfrac{b_1}{p^{k-1}} + (\dfrac{c}{p^{k-2}} + \dfrac{c}{p^{k-3}} + ... + \dfrac{c}{p} + c) =\\= \dfrac{b_1}{p^{k-1}}  + \dfrac{(p^{k-1} - 1)}{(p-1)(p^{k-2})} \cdot c =\\=  \dfrac{a_1+c}{p^{k-1}}  + \dfrac{(p^{k-1} - 1)}{(p-1)(p^{k-2})} \cdot c = \dfrac {p^kc + a_1(p-1) - c}{(p-1)(p^{k-1})}$
\end{multline}

Далее, т.к. $c = 2^l(p-1)$, имеем: $b_k = \dfrac {p^kc + a_1(p-1) - c}{(p-1)(p^{k-1})} = \dfrac {p^k \cdot 2^l +a_1 - 2^l}{p^{k-1}} = \dfrac {2^l (p^k-1)+a_1}{p^{k-1}}$

Cкажите, всё ли верно в моих рассуждениях?

 
 
 
 Re: Помогите решить рекуррентное соотношение.
Сообщение05.12.2013, 00:39 
rabbit_will_run
Это далеко не лучший способ выбрать c. Намного эффективнее $\[c = {2^l}\]$

 
 
 
 Re: Помогите решить рекуррентное соотношение.
Сообщение05.12.2013, 01:50 
Аватара пользователя
$a_k = \dfrac {a_{k-1} + 2^l(p-1)}{p}$
$a_k = \dfrac {a_{k-1} - 2^l}{p}+2^l$
$a_k-2^l = \dfrac 1 p (a_{k-1} - 2^l)$

 
 
 
 Re: Помогите решить рекуррентное соотношение.
Сообщение05.12.2013, 01:59 
Недопол.
rabbit_will_run в сообщении #796421 писал(а):
$$a_k = \dfrac {a_{k-1} + 2^l(p-1)}{p}$$
Вы ничего не забыли? У вас тут написано, по сути, $a_k=ba_{k-1}+c$, где $b, c$ — константы, я правильно понял? Тогда ж всё как-то слишком просто:
$\begin{cases}a_{k+1}=ba_k+c&a_{k+1}=ba_k+a_k-ba_{k-1}
\\a_k=ba_{k-1}+c&c=a_k-ba_{k-1}\end{cases}$
И мы имеем банальнейшую рекуррентную последовательность с постоянными коэффициентами.

-- 05.12.2013, 10:02 --

(Разумеется, для частных случаев констант можно бывает подобрать частный, более простой метод. Хотя при такой простоте общего — стоит ли?)

 
 
 
 Re: Помогите решить рекуррентное соотношение.
Сообщение05.12.2013, 08:57 
Аватара пользователя
А l здесь постоянное, которое в $2^l$?

 
 
 
 Re: Помогите решить рекуррентное соотношение.
Сообщение05.12.2013, 09:46 
Евгений Машеров
Вы правы, $l$ здесь не постоянное. Сам не сразу заметил, теперь исправляюсь. Стало понятно, почему при попытке свести к банальным рекуррентным соотношениям, выходили неверные ответы.
$l$ каждый раз увеличивается в $p$ раз. Я не знаю, как это лучше записать, но, возможно, так:
$a_n = \dfrac {a_{n-1} + 2^{lp^{k-n}}(p-1)}{p}$
При этом, найти всё ещё надо член последовательности $a_k$

 
 
 
 Re: Помогите решить рекуррентное соотношение.
Сообщение05.12.2013, 09:49 
Аватара пользователя
Если $l$ увеличивается, почему же у вас в показателе $n$ с минусом? Или оно увеличивается не при переходе к новому номеру? Каков смысл этого $k$? Вы не перепутали обозначения?

У вас что, задача была устно сформулирована?

 
 
 
 Re: Помогите решить рекуррентное соотношение.
Сообщение05.12.2013, 10:12 
provincialka
Нет, задача возникла в ходе решения исследовательской задачи. $l$ увеличивается при уменьшении $n$, т.е. по сути уменьшается.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group