(a) Note that $f_0(x)=1=x^0f_0(x^{-1})$. Assume that $ f_n(x)=x^nf_n\left(x^{-1}\right) $ for $k=n$. Then, \[f_{n+1}(x)=xf_n(x)+f_n(ax)=x^{n+1}f_n(x^{-1})+x^{n+1}f_n(ax^{-1})=x^{n+1}f_{n+1}(x^{-1}).\] Thus, by induction, $ f_n(x)=x^nf_n\left(x^{-1}\right) $ for all non-negative integers $n$.

Let $\{c_{ij}\}_{j=0}^i$ denote the coefficients of $f_n(x)$, so that \[ f_i(x) = \sum_{j=0}^i c_{ij}x^j. \] The recursion $f_{i+1}(x) = xf_i(x)+f_i(ax)$ gives the following recursion on the coefficients $c_{ij}$: \begin{align*} c_{i,0} = c_{i,i} &= 1 \quad \forall\ i\ge 0\\ c_{i+1,j+1} &= c_{i,j} + a^{j+1}c_{i,j+1} \quad \forall\ 0 \le j < i. \\ \end{align*} Lets find a combinatorial model for this recursion. Consider the lattice $\{(i,j)|0\le j\le i\}$. Join $(i,j)$ to $(i+1,j+1)$ with one path (type 1); join $(i,j)$ to $(i+1,j)$ with $a^j$ paths (type 2). Now $c_{ij}$ becomes the number of ways to walk from $(0,0)$ to $(i,j)$ along these paths. How may we represent such a path? There is a bijection between paths to $(i,j)$ and pairs $(\mathbf{s},\pi)$. Here $\mathbf{s}$ is a string of length $l$ ($0\le l\le j(i-j)$) with character set $\{1, \ldots , a\}$, and $\pi$ is a partition of $l$ into at most $i-j$ parts, each with size at most $j$. To get $(\mathbf{s},\pi)$: Clearly we may assign a length-$j$ string to each path from $(i,j)$ to $(i+1,j)$, as there are $a^j$ such paths. Given any path to $(i,j)$, we obtain $i-j$ codes, one for each type 2 edge traversed. As each code has length at most $j$, concatenating these codes gives a string $\mathbf{s}$ of length at most $j(i-j)$. The $i-j$ codes, in sequence, have nonstrictly increasing lengths, which make a partition $\pi$ of the total length $l$ of $\mathbf{s}$. The partition $\pi$ tells us how to recover the codes from $\mathbf{s}$. To get a path to $(i,j)$: Given $\mathbf{s}$ and $\pi$, break $\mathbf{s}$ into pieces whose lengths are the blocks of $\pi$, arranged in increasing order. Now read $\mathbf{s}$ starting from the last and largest block. From $(i,j)$, traverse type 1 paths until a bundle of type 2 paths with the right code-length is reached. Then travel along the path encoded by the last block of $\mathbf{s}$. Repeat until $\mathbf{s}$ is depleted. Then travel along type 1 edges to the $x$-axis, and walk to $(0,0)$. It is straightforward to check that these two operations are inverses of each other, so our bijection is valid. We denote by $p(l,n,m)$ the number of partitions $\pi$ of $l$ with at most $n$ parts, each with size at most $m$. Part (a) To show that $f_i (x) = x^i f_i(x^{-1})$ it suffices to prove that $c_{i,j} = c_{i,i-j}$ for all $i,j\ge 0$. But the above bijection, combined with the well-known fact that $p(l,i-j,j) = p(l,j,i-j)$, establishes this equality. We have in fact given a purely combinatorial proof of this identity! Part (b) Since \[ c_{i,j} = \sum_{l=0}^{j(i-j)} a^l p(l,i-j,j), \] if \[ P_{i-j,j}(x) = \sum_{l=0}^{j(i-j)} x^l p(l,i-j,j) \] denotes the generating function of such restricted partitions, then \[ f_i(x) = \sum_{j=1}^i P_{i-j,j}(a)x^j. \] This is an explicit expression, but it is unfortunately not closed. I'm not aware of a closed form for $P_{a,b}(x)$.

Let the coefficient of x^j in f_n(x) be c(n,j). Induct on n to show that c(n,j) = n?/(j?(n-j)?) where m? = (a-1)(a^2-1)...(a^m-1).