Generating functions and recursions smelling from 1000 km
Source: IMC 2022 Day 1 Problem 3
August 5, 2022
functioncounting techniquescollege contestsgenerating functionsIMC 2022
Problem Statement
Let be a prime number. A flea is staying at point of the real line. At each minute,
the flea has three possibilities: to stay at its position, or to move by to the left or to the right.
After minutes, it wants to be at again. Denote by the number of its strategies to do this
(for example, : it may either stay at for the entire time, or go to the left and then to the
right, or go to the right and then to the left). Find modulo .