$x_{n+13}=x_{n+4}+2x_{n}$, $x_{143}=...$

Question

Given $x_1=x_2=\dotsc=x_{12}=0$, $x_{13}=2$, and $x_{n+13}=x_{n+4}+2x_{n}$ for every natural number $n$. Find $x_{143}$.

I tried to find some pattern for some of the first term but did not notice any pattern that did not require some brute force to calculate $x_{143}$. So I decided to read and understand the solution :

Consider the equation $9p+13q=143$ where $p,q$ are nonnegative integers. Using euclid's algorithm, we have $(p_1,q_1)=(13,2)$ and $(p_2,q_2)=(0,11)$.

And after that, the solution claims that for $n=9p+13q$ where $p,q$ are nonnegative integers, we have $$x_n=\sum\limits_{i=1}^{k}2^{q_i}\cdot\binom{p_i+q_i-1}{p_i}$$ where $k$ is the number of solution for $(p,q)$ and $(p_i,q_i)$ is the $i$-th solution for $n=9p+13q$ for positive integer $i\leq k$.

I do not understand where the general form comes from. I tried using induction method to prove the general form, but did not done well. One of the things that prevent my induction proofing is that if $n+13$ has $k$ solution for $(p,q)$, it does not assure that $n+4$ and $n$ has exactly $k$ solution for $(p,q)$.

Comments and answer is appreciated.

Answer 1

Here is an attempt to explain the general form with a picture. It was easier to use the equivalent initial condition $x_0=1$ instead of $x_{13}=2$.

This picture shows the calculation of $x_{40}$. By the recursion, $x_{40}=x_{40-9}+2x_{40-13}$. So you get $x_{40}$ by following the upper and lower arcs to the right (to the integers $31$ and $27$), then combining (by adding, indicated by the small $+$) the $x_i$ values for those numbers, multiplying along the upper arc by $2$ and along the lower arc by $1$.

Of course, we don't know $x_{31}$ and $x_{27}$ from the initial given values, so we compute those by moving to the right $13$ and $9$ units from each of $31$ and $27$ and combining the $x_i$ we reach similarly. Eventually, every path reaches the range between $i=0$ and $i=12$, where the $x_i$ are known (red numbers in the picture), and the path stops there.

The final value of $x_{40}$ is a sum over all the resulting paths. Each path contributes something to $x_{40}$ if its right-hand endpoint is $0$ (and not something between $1$ and $12$). What it contributes is the value $2^u$, where $u$ is the number of upper arcs (corresponding to summands that equal $13$) in the path (sum).

It turns out that there is only one path from $0$ to $40$ in this particular case, corresponding to the ordered sum $13+9+9+9$. (The other sums of three $9$s and a $13$, such as $40=9+13+9+9$, don’t yield a contribution, because the path down from $40$ hits $9$ and stops before going on to $0$. Also, had I thought through this more, I would have reversed left with right in the picture so a path and its corresponding sum were ordered in the same way, not reversed.) The path corresponding to $13+9+9+9$ contains one upper arc and contributes $2^1\cdot1$, so $x_{40}=2$. (Note for later that the only way any path from $n$ ends in $0$ is if it arrives there from $13$, since a path getting to $9$ would stop before following another lower arc, so only sums beginning with $13$ contribute to $x_n$.)

In the general form, $k=1$ when $n=40$, and the one solution is $40=3\cdot9+1\cdot13$. Thus from the general form, $x_{40}=2^1{3+1-1\choose3}=2\cdot1=2$.

Note that ${p_i+q_i-1\choose p_i}$ is the number of ways to place the $p_i$ $9$s in an ordered sum of $p_i+q_i$ terms ($p_i$ $9$s and $q_i$ $13$s that add to $n$) in any but the first position, hence among $p_i+q_i-1$ possible positions. As noted earlier, the first summand (final arc of the path) cannot be $9$ (a lower arc), because if it were, the arcwise path from $n$ down would have ended at $9$ and not continued on to $0$.

Answer 2

Let $x_0=1$ for convenience, and use the formal $z$-transform:

$$f(z)=\sum_{n=0}^{\infty}x_n z^n\text{.}$$

Then the transform of the given recurrence is $$\frac{f(z)-1}{z^{13}}=\frac{f(z)-1}{z^4}+2f(z)$$

whence $$f(z)=\frac{1-z^9}{1-z^9-2 z^{13}}\text{.}$$ Expanding the denominator in some neighborhood of $0$,

$$\begin{split}f(z)&=\sum_{n=0}^{\infty}(1-z^9)(z^9+2z^{13})^n\\ &=\sum_{p,q=0}^{\infty} \binom{p+q}{q}2^q(1-z^9)z^{9p+13q}\\ &=\sum_{p,q=0}^{\infty} \left(\binom{p+q}{q}-\binom{p+q-1}{q}\right)2^qz^{9p+13q}\\ &=\sum_{p,q=0}^{\infty}\binom{p+q-1}{q-1}2^qz^{9p+13q}\text{.} \end{split}$$

Taking the coefficient of $z^n$, we find

$$\boxed{x_n=\sum_{\substack{p,q\in\mathbb{Z}^{\geq 0}\\ 9p+13q=n}}\binom{p+q-1}{q-1}2^q}\text{.}$$

Answer 3

We can phrase a combinatorial counting problem as follows:

Let there will be an event and you are going to buy a ticket. The ticket vendors are following a rule to give you a ticket with a number on it. They ask you to pick any non-negative integer and tell them. Let that integer be $m$. If $m$ can't be represented in the form $9p+13q$ with non-negative integers $p,q$, they will not give you an entrance pass. If $m\in\{9p+13q:p,q\in\mathbb{Z}_{\geq0}\}$, they pick one such representation $9p+13q$ and give you a card with a double decker sequence written on it. The double decker sequence has length $q$ and is of the following form: $$((x_1,y_1);(x_2,y_2);\ldots;(x_q,y_q))$$ with $x_i\in\{0,1\}$ and $y_i$'s are non-negative integers with $\sum_{j=1}^{q}y_j=p$

Let $x_n$ denotes the number of possible different such double-decker sequence(s) for given $n$. Find recursion and general closed-form formula for $x_n$

Let $n\in\{9p+13q:p,q\in\mathbb{Z}_{\geq0}\}$. We see that the equation $\sum_{j=1}^{q}y_j=p$ has $\binom{p+q-1}{p}$ solutions in non-negative integers and for each $x_i$ there are two choices. So by multiplication principle for a fixed representation $n=9p+13q$ there are total $2^q\binom{p+q-1}{p}$ such double decker sequences. So summing over all representations we get, $$x_n=\sum_{i=1}^{k}2^{q_i}\binom{p_i+q_i-1}{p_i}$$

If $n\notin\{9p+13q:p,q\in\mathbb{Z}_{\geq0}\}$ then $x_n=0$.

Try to find recursion to prove the identity for $n$ of the form $9p+13q$ with $p,q$ non-negative integers.