Count number of ways kangaroo can jump all points in interval and finish at last point

Question

There is the problem from Flajolet and Sedgewick book "Analytical Combinatorics":

"In how many ways can a kangaroo jump through all points of the integer interval $[1,n+1]$ starting at $1$ and ending at $n + 1$, while making hops that are restricted to $\{-1,1,2\}$?"

I'm trying to derive recurrence relation for that problem. Here's my reasoning.

Kangaroo can arrive at point $n + 1$ (i.e. finish his trip) only from points $n$ and $n - 1$. Let A(a, b) be the number of ways to start at point $1$, visit all $b$ points and arrive at point $a$. So the number of ways to jump all points from $1$ to $n + 1$ equals $A(n + 1, n + 1)$. Then the following recurrence can be formulated: $$ A(n + 1, n + 1) = A(n, n) + A(n - 1, n) $$
As described in mentioned book this function is Narayana's cows sequence (OEIS A000930) and its recurrence relation is $a(n) = a(n-1) + a(n-3)$. But how can I convert my recurrence with two variables into an ordinary linear recurrence? By using generating functions? Or maybe something's wrong with my reasoning and there is an easier way to come with linear recurrence?

Thanks!

Answer 1

To make sense as stated, the problem requires that each point only be visited a limited number of times. Probably, once only each.

Let's specify the recurrence $A$ more completely. In general:

$$A(p,c)=A(p+1,c-1)+A(p-1,c-1)+A(p-2,c-1)$$

where $p$ is the position at step $c$. It won't work for this problem because we forget which points have been visited and which haven't.

For example, consider $n=6$. Six steps are needed to pass through all points. But this recurrence would include the path $1\to3\to 5\to 6\to 5\to 6\to 7$, which is not valid.

So an insight is needed. The insight is this: any jump $+2$ must be followed by $-1+2$, and the $-1$ jump is not possible otherwise. This leads us to Narayana's cows sequence almost immediately.

Notice how much simpler this problem is than the other one!

Answer 2

Entering this into Wolfram gives a very complicated answer, but hopefully you'll be able to effectively use it. $$a(n)=a(n-1)+a(n-3)$$ The solution is $$a(n)=c_1{\left(\frac 3k\right)}^{-n}+c_2{(d)}^{n}+c_3{(e)}^{n}$$ where $c_1$ and $c_2$ are arbitrary constants $$k=1+{\left({29}-{3\sqrt{93}} \over 2 \right)}^{1/3}+{\left({29}+{3\sqrt{93}} \over 2 \right)}^{1/3}$$ $$d=\frac 13-{1-i\sqrt3\over 6}{\left({29}-{3\sqrt{93}} \over 2 \right)}^{1/3}-{1+i\sqrt3\over 6}{\left({29}+{3\sqrt{93}} \over 2 \right)}^{1/3}$$ and $$e=\frac 13-{1+i\sqrt3\over 6}{\left({29}-{3\sqrt{93}} \over 2 \right)}^{1/3}-{1-i\sqrt3\over 6}{\left({29}+{3\sqrt{93}} \over 2 \right)}^{1/3}$$