find the $a_{111}$ if $a_{n+11}=a_{n+5}+2a_{n}$

Question

Let sequence $\{a_{n}\}$ such $$a_{1}=a_{2}=\cdots=a_{10}=0,a_{11}=2$$,such $$a_{n+11}=a_{n+5}+2a_{n}$$

Find the $a_{111}$

I want show this sequence is Periodic series。following is some try

$$a_{n+11}=a_{n+5}+2a_{n}$$ $$a_{n+17}=a_{n+11}+2a_{n+6}=a_{n+5}+2a_{n}+2a_{n+6}$$

Answer 1

I just put it in a spreadsheet. The sequence is not periodic. I find $a_{111}=23880$ but don't see a neat way to get that.

Added: if I had to do it by hand I would just follow the recurrence backwards $$a_{111}=a_{105}+2a_{100}\\=a_{99}+4a_{94}+4a_{89}\\ =a_{93}+6a_{88}+12a_{83}+8a_{78}$$ It will take about $18$ such lines. After about $10$ lines terms will disappear off the end because of the known $0$ values. It is a fair amount of work this way.

Answer 2

We easily see that the generating function of this sequence is $$ A(x)=\sum_{k=1}^\infty a_kx^k=\frac{2x^{11}}{1-x^6-2x^{11}}. $$ By the sum formula of a geometric series $1/(1-q)=\sum_{k=0}^\infty q^k$ at $q=x^6+2x^{11}$ we arrive at the following identity of formal power series $$ A(x)=2x^{11}\sum_{k=0}^\infty(x^6+2x^{11})^k. $$ By the binomial formula the $k$th term contributes terms like $\binom{a+b}{a}x^{6a}(2^bx^{11b})$ where $a+b=k$. This term has degree $6a+11b$, and we are only interested in terms of degree $100$.

The parameters $a$ and $b$ are non-negative integers. It is relatively easy to figure out that the only solutions of $$6a+11b=100\qquad(*)$$ are $(a,b)=(2,8)$ and $(a,b)=(13,2)$. A good way is to observe that $(*)$ implies the congruence $6a\equiv100\equiv1\pmod{11}$, whence $a\equiv2\pmod{11}$.

Hence $$ a_{111}=\binom{10}22^9+\binom{15}22^3=23880. $$

---

This method may be useful whenever we have a suitably sparse recurrence relation. I don't recall having seen a general description of this though (but my recollection is not what it once was). Its usefulness is somewhat limited, because with higher indices the number of terms begins to grow. The actual problem may have been carefully drafted not to make this approach too arduous. The index $111$ was in a range where the number of terms was quite manageable.