# 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.

• You can plot it as a graph. 1-2, 2-3, 3-4. From there you can check, starting from 1, in how many ways you can move as long as you finish at 4. Oct 13 '16 at 0:36
• – user57159
Oct 13 '16 at 0:38

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:

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.