# How to find the limit of this recurrence relation

I am trying to solve a question which requires me to solve this problem.

Given that $$a_0=a_1=a_2=a_3=a_4=0$$ and $$a_5=1$$ and

$$a_{n+6}=\dfrac{a_{n+5}+a_{n+4}+a_{n+3}+a_{n+2}+a_{n+1}+a_{n}}{6}$$ find the limit of$$a_n$$ as $$n$$ approaches infinity.

I tried various approaches but they do not seem to work, such as finding the fixed point of recurrence or finding the limit from the closed form of recurrence which do not exist. However, I calculated the values of $$a_n$$ up to $$10000$$ and the answer seems to extremely close to $$2/7$$

I am not looking for complete solution, I would rather appreciate if someone could point me in the right direction, just a hint would suffice.

• A linear homogenous recurrence relation with constant coefficients always has a closed form, but it might be hard to find for a degree $6$ relation. You can try to see if there is anything helpful in the answers to this question : math.stackexchange.com/questions/2276402/… May 22 '17 at 14:36
• @ArnaudD. There is always a closed form for a linear recurrence relation, not always for any recurrence ;) May 22 '17 at 14:37
• @B.Mehta Well this one looks linear to me ;) May 22 '17 at 14:38
• Are you really interested in $\lim_{n\to +\infty}a_n$ or you meant to ask about $\lim_{n\to +\infty}\frac{a_{n+1}}{a_n}$, that depends on the roots of the characteristic polynomial $x^6-\frac{x^5+x^4+x^3+x^2+x+1}{6}$? May 22 '17 at 14:39
• I am interested in $a_n$ as $n$ approaches $\infty$ May 22 '17 at 14:40

I'm going to use the same idea as in this question:

$$6a_{n+6}=a_{n+5}+a_{n+4}+a_{n+3}+a_{n+2}+a_{n+1}+a_{n}$$

Now calculate some cases:

$$6a_{6}=a_{5}+a_{4}+a_{3}+a_{2}+a_{1}+a_{0}$$ $$6a_{7}=a_{6}+a_{5}+a_{4}+a_{3}+a_{2}+a_{1}$$ $$6a_{8}=a_{7}+a_{6}+a_{5}+a_{4}+a_{3}+a_{2}$$ $$6a_{9}=a_{8}+a_{7}+a_{6}+a_{5}+a_{4}+a_{3}$$ $$6a_{10}=a_{9}+a_{8}+a_{7}+a_{6}+a_{5}+a_{4}$$ $$6a_{11}=a_{10}+a_{9}+a_{8}+a_{7}+a_{6}+a_{5}$$ $$...$$

when we keep writing and sum every equation we see that all terms $a_i$ for $6\le i\le n-6$ will be canceled on both sides.

We then will get:

$$6a_{n}+5a_{n-1}+4a_{n-2}+3a_{n-3}+2a_{n-4}+a_{n-5}=6a_{5}+5a_{4}+4a_{3}+3a_{2}+2a_{1}+a_{0}=6$$

and if $a_n\to L$ then

$$6L+5L+4L+3L+2L+L=6\to L=\frac{2}{7}$$

• Thanks! But you just posted the complete solution. May 22 '17 at 14:43
• @Peter: Oh, so sorry! May 22 '17 at 14:44
• Interesting. It seems to work for any number of initial terms (assuming the limit exists, but that doesn't seem too big of an issue). May 22 '17 at 14:45
• @ArnaudD.: I'm pretty sure that it works. May 22 '17 at 14:46
• @Peter: You can use this question: math.stackexchange.com/questions/2276402/…. And then find out the way by yourself. May 22 '17 at 14:47

The generating function of the sequence is $$f(z)=\sum_{n=0}^{\infty}a_nz^n=\frac{6z^5}{6-z-z^2-z^3-z^4-z^5-z^6}.$$ Note that one of the poles is $1$ and the others are all complex numbers outside the disc $|z|\leq 1$. Hence $$\lim_{n\to\infty}a_n=-\mbox{Res}(f,1)=\frac{6}{1+2+3+4+5+6}=\frac{2}{7}.$$ If we replace $6$ by $N$, by using the same approach, we find that the limit is $$\frac{N}{1+2+\dots+N}=\frac{2}{N+1}.$$

• Is it obvious all the other poles are inside $|z|<1$? May 22 '17 at 15:42
• This seems to be a more general approach. May 22 '17 at 15:55
• @B. Mehta Probably not. I think Rouche' theorem could be useful en.wikipedia.org/wiki/Rouch%C3%A9%27s_theorem May 22 '17 at 16:31
• $\left\vert\,6 - z - \cdots - z^{6}\,\right\vert =\left\vert\, -\prod_{k = 1}^{6}\left(\,z - \texttt{pole}_{k}\,\right)\,\right\vert \implies \prod_{k = 1}^{6}\left\vert\,\texttt{pole}_{k}\,\right\vert = 6$ !!!. May 22 '17 at 21:33
• Sorry, I mean "outside the disc $|z|\leq 1$". May 23 '17 at 4:50

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

Following $\texttt{@Robert Z}$$\,\,\,$ answer:

\begin{align} \mc{F}\pars{z} & \equiv {6z^{5} \over 6 - z - z^{2} - z^{3} - z^{4} - z^{5} - z^{6}} = {6z^{5} \over 6 - z\pars{1 - z^{6}}/\pars{1 - z}} \\[5mm] & = 6\,{z^{5} - z^{6} \over z^{7} - 7z + 6} = \sum_{p}r_{p}\pars{{1 \over z - p} + {1 \over p}} \\[5mm] \mbox{where}\qquad & \left\{\begin{array}{l} \ds{p^{7} -7p + 6 = 0} \\[2mm] \ds{\left.r_{p}\right\vert_{\ p\ \not=\ 1} \equiv {6 \over 7}\,{p^{5}\pars{1 - p} \over p^{6} - 1}\,,\qquad r_{1} \equiv -\,{2 \over 7}} \\[2mm] \ds{r_{p}}\ \mbox{is the}\ residue\ \mbox{at pole}\ p. \end{array}\right. \\[5mm] \mbox{Note that}\quad & \left.r_{p}\right\vert_{\ p\ \not=\ 1} = {1 \over 7}\,{p^{6}\pars{1 - p} \over p^{7} - p} = {6 \over 7}\,{p^{6}\pars{1 - p} \over \pars{7p - 6} - p} = {1 \over 7}\,{p^{6}\pars{1 - p} \over p - 1} = -\,{p^{6} \over 7} \end{align}

With $\ds{0 < a < \min\braces{\verts{p}}}$:

\begin{align} a_{n} & = \oint_{\verts{z} = a}{\mc{F}\pars{z} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} = {1 \over n!}\,\lim_{z \to 0}\,\totald[n]{\mc{F}\pars{z}}{z} = {1 \over n!}\,\lim_{z \to 0} {\sum_{p}r_{p}\,{\pars{-1}^{n}n! \over \pars{z - p}^{n + 1}}} = -\sum_{p}{r_{p} \over p^{n + 1}} \\[5mm] & = - r_{1} + {1 \over 7}\sum_{p \not= 1}{1 \over p^{n - 5}} = {2 \over 7} + {1 \over 7}\sum_{p \not= 1}{1 \over p^{n - 5}} \implies \bbx{\lim_{n \to \infty}a_{n} = {2 \over 7}} \end{align}

The $\ds{\,\mc{F}\pars{z}}$ poles, which are different of one, have magnitude greater than $\ds{\color{#f00}{one}}$ !!!.

Hint: Compute the next few terms of the recurrence, which will give you a pretty clear clue as to what the closed form should be. You can prove this by induction, and then the limit should become clear.