Issue about the generating function

Question

A rabbit initially stands at the position $0$, and repeatedly jumps on the real line. In each jump, the rabbit can jump to any position corresponds to an integer but it cannot stand still. Let $N(a)$ be the number of ways to jump with a total distance of $2019$ and stop at the position $a$. Determine all integers $a$ such that $N(a)$ is odd.

Solution Consider the quantity $$T = (x+x^2+x^3+...)+(y+y^2+y^3+...) = \frac{x}{1-x}+\frac{y}{1-y}$$and define generating functions $$F(x,y) = 1+T+T^2+...$$It's clear that the coefficient of $x^my^n$ in $F$ equals to the number of ways to jump with a total distance of $m+n$ and arrive at position $m-n$. (i.e. variable $x$ corresponds to positive jumps and variable $y$ corresponds to negative jumps).

Now we evaluate $F(x,y)$. To do this, we work in $\mathbb{Z}_2$, so $$F(x,y) = \frac{1}{1-T} = \frac{(1-x)(1-y)}{1-xy}$$ Thus, we have $$F(x,y) = (1-x-y+xy)(1+(xy)+(xy)^2+(xy)^3+...)$$ It's clear that all odd coefficients are in form $x^ny^{n+1}$ and $x^{n+1}y^n$, which corresponds to $N(1)$ and $N(-1)$. Thus the answer is $\boxed{\{1,-1\}}$.

Edit after Donald Splutterwit answer. Can someone please explain

• What is $1$ in $F$ since rabbit must jump at least once? >Shouldn't it start with $T$ and not with $1$?
• Why there is no $1$ in $T$ since the rabbit can jump on the >spot?
• How come they never actually use $2019$ and $a$?

Answer 1

Question: What is $1$ in $F$ since rabbit must jump at least once? Shouldn't it start with $T$ and not with $1$?

We are free to choose $F$ either starting with $1$ or starting with $T$. A value $1$ represents no jump at all and will simply be ignored when doing the analysis. Its benefit is to have a slightly simpler function. With \begin{align*} T(x,y)=\frac{x}{1-x}+\frac{y}{1-y} \end{align*} we have \begin{align*} \color{blue}{F(x,y)}&=\frac{1}{1-T(x,y)}=\frac{1}{1-\left(\frac{x}{1-x}+\frac{y}{1-y}\right)}\\ &=\frac{1-x-y+xy}{1-\left(2x+2y-3xy\right)}\\ &=\left(1-x-y+xy\right)\sum_{j=0}^\infty \left(2x+2y-3xy\right)^j\\ &\color{blue}{\equiv\left(1+x+y+xy\right)\sum_{j=0}^\infty\left(xy\right)^j\pmod{2}}\tag{1}\\ \end{align*}

On the other hand starting with $T$ we obtain \begin{align*} \color{blue}{G(x,y)}&=\frac{T(x,y)}{1-T(x,y)}=\frac{\frac{x}{1-x}+\frac{y}{1-y}}{1-\left(\frac{x}{1-x}+\frac{y}{1-y}\right)}\\ &=\frac{x+y-2xy}{1-\left(2x+2y-3xy\right)}\\ &=\left(x+y-2xy\right)\sum_{j=0}^\infty \left(2x+2y-3xy\right)^j\\ &\color{blue}{\equiv\left(x+y\right)\sum_{j=0}^\infty\left(xy\right)^j\pmod{2}}\tag{2}\\ \end{align*}

When answering the third question, we will see that (1) and (2) will lead to the same conclusion.

Question: Why there is no $1$ in $T$ since the rabbit can jump on the >spot?

The problem states the rabbit can jump to any position corresponding to an integer but it cannot stand still. This implies that each jump has length $>0$.

Question: How come they never actually use $2019$ and $a$?

The solution answers the prolem for any distance $d$, not only for the special case $d=2019$. We consider wlog the case $a>0$ which implies when looking at positive jumps $x^m$ and negative jumps $y^n$ we have \begin{align*} m+n&=d\tag{3}\\ m-n&=a \end{align*} We denote with $N(d,a)$ the number of ways to jump with a total distance of $d$ and stop at the position $a$.

We use the coefficient of operator $[x^m]$ to denote the coefficient of $x^m$ in a series. We obtain calculating in $\mathbb{Z}_2$ \begin{align*} \color{blue}{[x^my^n]}&\color{blue}{F(x,y)}\\ &=[x^my^n]\left(1+x+y+xy\right)\sum_{j=0}^{\infty}(xy)^j\\ &=\left([x^my^n]+[x^{m-1}y^n]+[x^my^{n-1}]+[x^{m-1}y^{m-1}]\right)\sum_{j=0}^\infty (xy)^j\\ &\color{blue}{=\begin{cases} 1&\qquad (m=n)\vee (m=n+1)\vee (m=n-1)\\ 0&\qquad\text{otherwise} \end{cases}}\tag{4} \end{align*}

An odd coefficient $N(d,a)$ is given if \begin{align*} [x^my^n]F(x,y)=1\qquad\qquad m+n=d, m-n=a \end{align*} We conclude from (4) that $m=n$ implies $a=0$ which is not admissible. The other left options are $m-n=a=1$ and $m-n=a=-1$, resulting in \begin{align*} \color{blue}{N(d,-1),N(d,1)} \end{align*} for any odd values $d$. No other value $a$ is possible.

This solution implicitly includes the value $d=2019$.

We also note that working with $G(x,y)$ results in (4) without the solution $m=n$ which is not admissible anyways.

Answer 2

I am interpreting your question of 'what is for' to be asking for their interpretation as generating functions. If you mean, why their names are needed, then maybe not necessarily needed. They are probably defined to make the definition of $F$ go through stages, such that the argument is better understood.

$T$ is a generating function of the double sequence $(a,b)\mapsto$ 'the number of ways to be at a point and jump with length $a$ to the right and $b$ to the left'. Since at each point the rabbit is only allowed to jump in only one direction, then for $(a,b)$ with both $a$ and $b$ non-zero, the coefficient is zero. When only one of the exponents is non-zero, then there is only one way to jump in the corresponding direction and with the length indicated by the non-zero exponent.

$F$ is the generating function of the double sequence $(a,b)\mapsto$ 'the number of ways to get a path that has jumped a total of $a$ to the right, and a total of $b$ to the left'. Well, in your text you already had an interpretation of $F$. Note that it is not verbatim this interpretation, but that they are equivalent, since $a+b$ and $a-b$ determine $a$ and $b$.

Answer 3

$T$ represents taking one leap ... any whole number of steps to the left or right.

$T^2$ represents taking $2$ leaps & so on ...

So $F$ represents taking any number of leaps.

They then consider these generating functions over the field modulo $2$ (or more exactly their coefficients) ... which is fine because we only want to know if an odd or even number of configurations are possible.

Answer 4

Can someone please explain what is 1 in F since rabbit must jump at least once? Shouldn't it start with T and not with 1?

Don't interpret "cannot stand still" as meaning the rabbit has to jump at least once. "Cannot stand still" means that standing still doesn't count as a jump, or in other words, every jump must move the rabbit to a new position.

How come they never actually use 2019 and a?

They computed $a \in \{1, -1\}$ regardless of what distance you use. They showed that the only odd coefficients are $x^ny^{n+1}$ and $x^{n + 1}y^n$. To "use $2019$" we would then require that the exponents sum to $2019$ so $2019 = 2n + 1$. Regardless of what $n$ is, however, $a$ is always the difference of the exponents. Meaning $a$ is always $n - (n + 1)$ or $(n + 1) - n$ so $a$ is always $\pm 1$.