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 $x\leq y$, then we need $y-x$ more $+1$'s than $-1$'s and if $x\geq 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-1\choose k}$ if we need to use $+1$ $k$ times. Hopefully you can finish it from here.