By adding or subtracting a specific number multiple times, how many ways can you add up to a sum? This situation occurred today when I was introduced to this riddle.

There are 4 lilypads. There is a frog on the first lilypad that can hop 1 lilypad to the left or right every turn. After 19 turns, the frog must be on the fourth lilypad.
  How many ways can the frog do this?

So to clarify, X must equal 4 by incrementing or decrementing 19 times. X must stay within $[1,4]$.
Numbering the lilypads 1 2 3 and 4, an example solution could be
1 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 4

or
1 2 3 4 3 2 1 2 3 2 3 4 3 2 1 2 3 4 3 4

I understand that in reality, only 17 of the moves matter since the first move is guaranteed to be to the right, and so is the last, but I don't understand how to calculate every possible solution when lilypads 2 and 3 have 2 different possible branches while 1 and 4 only have one possible branch.
 A: For each lilypad $p$ let $p_n$ denote the number of ways to land on it after exactly $n$ jumps starting from pad 1 (so $1_n$, $2_n$, $3_n$ and $4_n$ from left to right).
Because of parity considerations, we can perform the first compulsory jump to pad 2 first and then consider the remaining 18 jumps in 9 pairs; the frog will always be on pads 2 and 4 in the process. In a pair of jumps:


*

*starting from pad 2, the frog can return to pad 2 in two ways and go to pad 4 in one way

*starting from pad 4, the frog can return to pad 4 in one way and go to pad 2 in one way


In equations these relations become
$$2_{2k+1}=2\cdot2_{2k-1}+4_{2k-1}$$
$$4_{2k+1}=2_{2k-1}+4_{2k-1}$$
$$2_1=1,\ 4_1=0$$
For working up to $4_{19}$ it's easier to work explicitly rather than solve a matrix:
n   2_n   4_n
1   1     0
3   2     1
5   5     3
7   13    8
9   34    21
11  89    55
13  233   144
15  610   377
17  1597  987
19  4181  2584

The Fibonacci numbers are generated, the sequence snaking between $2_n$ and $4_n$. The answer to the question is 2584.
