# How can I prove this relation between the probability generating functions of a markov chain?

For $$|x|<1$$, and states $$i,j\in S$$ define: $$P_{ji} (x)=\sum_{n=0}^{\infty} p_n(j|i) x^n$$ $$F_{ji} (x)=\sum_{n=1}^{\infty} f_n(j|i) x^n$$ Where $$f_n (j|i)=P(\xi_n=j,\xi_k\neq j,k=1..n-1|\xi_0=i)$$ (i.e. that the state j first occurs at step n) and $$p_n(j|i)=P(\xi_n=j|\xi_0=i)$$. Prove the following relations: $$P_{ji} (x)=F_{ji} (x)P_{jj} (x), j\neq i$$ $$P_{ii} (x)=1+F_{ii} (x)P_{ii} (x)$$ This is problem 5.17 of the book Basic Stochastic Processes by Brzezniak & Zastawniak. The solutions for this question contains the proof that $$p_n(j|i)= \sum_{k=1}^{n} f_k(j|i) p_{m-k}(j|j)$$ and claims this is sufficient to prove the above relations. I can derive from that the following: $$P_{ji} (x)=\sum_{n=0}^{\infty} p_n(j|i) x^n =\sum_{n=0}^{\infty} \left(\sum_{k=1}^{n} f_k(j|i) p_{n-k}(j|j)\right) x^n$$ $$=\sum_{n=0}^{\infty} \sum_{k=1}^{n} f_k(j|i) p_{n-k}(j|j) x^n$$ but I'm at a loss for where to go from here. How can I get from this to the sum for $$F_{ji} (x)P_{jj} (x)$$?