Vtyjkyuk

I'm trying to solve the following problem: given $n, x, y$, count sequences of length $n$ with fixed first element - $x$ and last one - $y$, such that any two adjacent elements differ by one or minus one.

For example $n=3, x = 1, y = 1$, the answer is $2$, because there are two sequences of length $3$ which should be counted $[ 1,0,1], [1, 2,1]$.

I came up with function $f(i, x)$ which means sequences of length $i$ with $i-th$ element being $x$. We can express $f(i, x) = f(i-1, x-1) + f(i-1, x+1)$.

But this is hard to compute for large numbers, is there any solution that can solve this with combinatorics.

We can think of such a sequence $x=a_1,a_2,dots,a_n=y$ where $|a_i-a_i-1|=1$ instead as a sequence of $pm 1$ of length $n-1$: $b_1,dots,b_n-1$ where $b_i=a_i+1-a_i$. In order to start at $x$ and end at $y$, we need a certain number of $+1$'s and $-1$'s. In particular, if $xleq y$, then we need $y-x$ more $+1$'s than $-1$'s and if $xgeq y$, then we need $x-y$ more $+1$'s than $-1$'s. Now, these $pm 1$'s can be placed wherever you want in the sequence provided there's the correct excess, so, for instance, we can choose in which of the $n-1$ available positions to place the $+1$'s, which is $n-1choose k$ if we need to use $+1$ $k$ times. Hopefully you can finish it from here.