10
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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/… $\endgroup$ – Arnaud D. May 22 '17 at 14:36
  • $\begingroup$ @ArnaudD. There is always a closed form for a linear recurrence relation, not always for any recurrence ;) $\endgroup$ – B. Mehta May 22 '17 at 14:37
  • $\begingroup$ @B.Mehta Well this one looks linear to me ;) $\endgroup$ – Arnaud D. May 22 '17 at 14:38
  • $\begingroup$ 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}$? $\endgroup$ – Jack D'Aurizio May 22 '17 at 14:39
  • $\begingroup$ I am interested in $a_n$ as $n$ approaches $\infty$ $\endgroup$ – Peter May 22 '17 at 14:40
8
$\begingroup$

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

Limit of sequence in which each term is defined by the average of preceding two terms

$$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}$$

$\endgroup$
  • $\begingroup$ Thanks! But you just posted the complete solution. $\endgroup$ – Peter May 22 '17 at 14:43
  • $\begingroup$ @Peter: Oh, so sorry! $\endgroup$ – Arnaldo May 22 '17 at 14:44
  • 1
    $\begingroup$ 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). $\endgroup$ – Arnaud D. May 22 '17 at 14:45
  • $\begingroup$ @ArnaudD.: I'm pretty sure that it works. $\endgroup$ – Arnaldo May 22 '17 at 14:46
  • $\begingroup$ @Peter: You can use this question: math.stackexchange.com/questions/2276402/…. And then find out the way by yourself. $\endgroup$ – Arnaldo May 22 '17 at 14:47
10
$\begingroup$

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}.$$

$\endgroup$
  • $\begingroup$ Is it obvious all the other poles are inside $|z|<1$? $\endgroup$ – B. Mehta May 22 '17 at 15:42
  • 2
    $\begingroup$ This seems to be a more general approach. $\endgroup$ – Peter May 22 '17 at 15:55
  • $\begingroup$ @B. Mehta Probably not. I think Rouche' theorem could be useful en.wikipedia.org/wiki/Rouch%C3%A9%27s_theorem $\endgroup$ – Robert Z May 22 '17 at 16:31
  • $\begingroup$ $\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$ !!!. $\endgroup$ – Felix Marin May 22 '17 at 21:33
  • $\begingroup$ Sorry, I mean "outside the disc $|z|\leq 1$". $\endgroup$ – Robert Z May 23 '17 at 4:50
2
$\begingroup$

$\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}}$ !!!.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.