Recurrence relation

• Oct 3rd 2010, 10:55 AM
aa2010
Recurrence relation
Hello,

I cannot solve the following problem:
What can we say about the asymptotic behavior, depending on the initial conditions, of a recurrence relation that has a inhomogeneous part (log n)^(log n) and has roots 1,2,3 ?
• Mar 29th 2011, 10:44 PM
bkarpuz
Hi aa2010,

I am assuming that you are asking about the asymptotic nature of the difference equation
$\displaystyle (\mathcal{L}y)(n):=\Delta^{3}y(n)-3\Delta^{2}y(n)+2\Delta y(n)-6y(n)=\big(\ln(n)\big)^{\ln(n)}$ for $\displaystyle n\geq n_{0}(\geq2)$
under the initial conditions
$\displaystyle \Delta^{2}y(n_{0})=a$, $\displaystyle \Delta y(n_{0})=b$ and $\displaystyle y(n_{0})=c$.
Here, $\displaystyle \Delta$ is the forward difference operator, i.e., $\displaystyle \Delta y(n):=y(n+1)-y(n)$ and $\displaystyle \Delta^{k}y(n):=\Delta^{k-1}\Delta y(n)$.
For such problems, you need to compute the fundamental solutions, i.e.,
the solutions of the following initial value problems
$\displaystyle \mathcal{Y}_{1}(n,m)$: $\displaystyle (\mathcal{L}y)(n)=0$ for $\displaystyle n\geq m\geq n_{0}$ with $\displaystyle \Delta^{2}y(m)=1$, $\displaystyle \Delta y(m)=0$ and $\displaystyle y(m)=0$
$\displaystyle \mathcal{Y}_{2}(n,m)$: $\displaystyle (\mathcal{L}y)(n)=0$ for $\displaystyle n\geq m\geq n_{0}$ with $\displaystyle \Delta^{2}y(m)=0$, $\displaystyle \Delta y(m)=1$ and $\displaystyle y(m)=0$
$\displaystyle \mathcal{Y}_{3}(n,m)$: $\displaystyle (\mathcal{L}y)(n)=0$ for $\displaystyle n\geq m\geq n_{0}$ with $\displaystyle \Delta^{2}y(m)=0$, $\displaystyle \Delta y(m)=0$ and $\displaystyle y(m)=1$.
Then, by the variation of constants formula, we can write the solution as follows
$\displaystyle y(n):=a\mathcal{Y}_{1}(n,n_{0})+b\mathcal{Y}_{2}(n ,n_{0})+c\mathcal{Y}_{3}(n,n_{0})+\displaystyle\su m_{k=n_{0}}^{n-1}\mathcal{Y}_{1}(n,k+1)\big(\ln(k)\big)^{\ln(k)}$ for $\displaystyle n\geq n_{0}$.
Here, we have
$\displaystyle \mathcal{Y}_{1}(n,m)=\dfrac{1}{2}3^{n-m}-2^{n-m}+\dfrac{1}{2}$ for $\displaystyle n\geq m\geq n_{0}$
$\displaystyle \mathcal{Y}_{2}(n,m)=-\dfrac{1}{2}3^{n-m}+22^{n-m}-\dfrac{1}{3}$ for $\displaystyle n\geq m\geq n_{0}$
and
$\displaystyle \mathcal{Y}_{3}(n,m)\equiv1$ for $\displaystyle n\geq m\geq n_{0}$.
Assume that $\displaystyle n_{0}:=9$, then $\displaystyle \big(\ln(n)\big)^{\ln(n)}\geq n$ for $\displaystyle n\geq9$, which yields
$\displaystyle y(n)\geq a\mathcal{Y}_{1}(n,9)+b\mathcal{Y}_{2}(n,9)+c\math cal{Y}_{3}(n,9)+\displaystyle\sum_{k=n_{0}}^{n-1}\mathcal{Y}_{1}(n,k+1)k$
.........$\displaystyle =a\mathcal{Y}_{1}(n,9)+b\mathcal{Y}_{2}(n,9)+c\mat hcal{Y}_{3}(n,9)+\dfrac{19}{8}3^{n-9}-\dfrac{5}{2}2^{n-9}+\dfrac{1}{8}\big(2n^{2}+4n-137\big)$
for all $\displaystyle n\geq9$.
Thus, if $\displaystyle a/2-b/2+19/8>0$ (the coefficients of the dominant term $\displaystyle 3^{n-9}$), then $\displaystyle y(n)\to\infty$ as $\displaystyle n\to\infty$.
Obtaining a complete result for your problem requires a deep inspection since the forcing term is not a nice one. (Itwasntme)
• Mar 29th 2011, 11:24 PM
bkarpuz
As I said, better inequalities will give you better results.
Note that for $\displaystyle n\geq 2$, we have $\displaystyle \big(\ln(n)\big)^{\ln(n)}\geq\dfrac{1}{n^{4}}3^{n+ 1}$,
then the contribution of the forcing term to the solution can not be less than
$\displaystyle \displaystyle\sum_{k=2}^{n-1}\mathcal{Y}_{1}(n,k+1)\frac{1}{k^{4}}3^{k+1}$ for all $\displaystyle n\geq 2$.
As $\displaystyle n\to\infty$,
$\displaystyle \dfrac{1}{3^{n-2}}\displaystyle\sum_{k=2}^{n-1}\mathcal{Y}_{1}(n,k+1)\frac{1}{k^{4}}3^{k+1}\to\ dfrac{\pi^{4}}{10}-9\approx0.74$,
which implies that $\displaystyle a/2-b/2+\pi^{4}/10-9>0$ yields $\displaystyle y(n)\to\infty$ as $\displaystyle n\to\infty$.