The city has decided to plant apple trees on its main thoroughfares of First Avenue, Second Avenue, Third Avenue and Fourth Avenue. To add character to the plan, city council has decided that the number of trees that are planted on $i$th Avenue must be congruent to $i$ modulo $2$ (for each $i$). Let $a_r$ denote the number of ways of planting $r$ trees subject to these criteria.
(a) Find a generating function for $a_r$.
(b) Find $a_9$.
HINT: I’ll get you started. The number of trees planted on Second Avenue must be even, so the generating function for the number of ways of planting $n$ trees on Second Avenue must be
$$g_2(x)=1+x^2+x^4+x^6+\ldots=\sum_{n\ge 0}x^{2n}=\frac1{1-x^2}\;.$$
Clearly this is also the generating function $g_4(x)$ for the number of ways of planting $n$ trees on Fourth Avenue. The generating function for the number of ways of planting $n$ trees total on Second and Fourth Avenues is therefore $$g_2(x)g_4(x)=\left(\frac1{1-x^2}\right)^2\;.$$