# Recurrence relation

• Oct 3rd 2010, 11: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, 11:44 PM
bkarpuz
Hi aa2010,

I am assuming that you are asking about the asymptotic nature of the difference equation
$(\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 $n\geq n_{0}(\geq2)$
under the initial conditions
$\Delta^{2}y(n_{0})=a$, $\Delta y(n_{0})=b$ and $y(n_{0})=c$.
Here, $\Delta$ is the forward difference operator, i.e., $\Delta y(n):=y(n+1)-y(n)$ and $\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
$\mathcal{Y}_{1}(n,m)$: $(\mathcal{L}y)(n)=0$ for $n\geq m\geq n_{0}$ with $\Delta^{2}y(m)=1$, $\Delta y(m)=0$ and $y(m)=0$
$\mathcal{Y}_{2}(n,m)$: $(\mathcal{L}y)(n)=0$ for $n\geq m\geq n_{0}$ with $\Delta^{2}y(m)=0$, $\Delta y(m)=1$ and $y(m)=0$
$\mathcal{Y}_{3}(n,m)$: $(\mathcal{L}y)(n)=0$ for $n\geq m\geq n_{0}$ with $\Delta^{2}y(m)=0$, $\Delta y(m)=0$ and $y(m)=1$.
Then, by the variation of constants formula, we can write the solution as follows
$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 $n\geq n_{0}$.
Here, we have
$\mathcal{Y}_{1}(n,m)=\dfrac{1}{2}3^{n-m}-2^{n-m}+\dfrac{1}{2}$ for $n\geq m\geq n_{0}$
$\mathcal{Y}_{2}(n,m)=-\dfrac{1}{2}3^{n-m}+22^{n-m}-\dfrac{1}{3}$ for $n\geq m\geq n_{0}$
and
$\mathcal{Y}_{3}(n,m)\equiv1$ for $n\geq m\geq n_{0}$.
Assume that $n_{0}:=9$, then $\big(\ln(n)\big)^{\ln(n)}\geq n$ for $n\geq9$, which yields
$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$
......... $=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 $n\geq9$.
Thus, if $a/2-b/2+19/8>0$ (the coefficients of the dominant term $3^{n-9}$), then $y(n)\to\infty$ as $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 30th 2011, 12:24 AM
bkarpuz
As I said, better inequalities will give you better results.
Note that for $n\geq 2$, we have $\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\sum_{k=2}^{n-1}\mathcal{Y}_{1}(n,k+1)\frac{1}{k^{4}}3^{k+1}$ for all $n\geq 2$.
As $n\to\infty$,
$\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 $a/2-b/2+\pi^{4}/10-9>0$ yields $y(n)\to\infty$ as $n\to\infty$.