Solving a recurrence relation such that $\sum_{k=0}^\infty x_k = 1$

Question

Question

Let $x_0$ be arbitrary, $p \in (0,1)$ and assume the following holds: $$x_1=\frac{(1-p)^2(1+2p)}{p^3}x_0$$ $$x_2=\frac{(1-p)^3(1+3p-3p^3)}{p^6}x_0$$ and in general: $$ x_k(1-p)^3 + 3p(1-p)^2 x_{k+1} + (3p^2(1-p)-1) x_{k+2}+p^3 x_{k+3}=0 $$ I now seek the value of $x_0$ for which $\sum_{n=0}^{\infty} x_n = 1$.

Own attempt 1 : generating function

My first thought was to make use of the generating function. Let $f(z) = (1-p)^3 z^3 + 3 p (1-p)^2 z^2 + (3 p^2(1-p) - 1)z + p^3$, then one finds that: $$ f(z) \cdot \sum_{n=0}^\infty x_n z^n = A(p,z), $$ where $A(p)$ is some funtion of $p$ and $z$ which can be easily computed in an explicit way. The trick would now (I think) be to set $z=1$ which allows us to find: $$ f(1) \cdot \sum_{n=0}^\infty x_n = A(p,1), $$ using $\sum_{n=0}^\infty x_n =1$ this yields $f(1) = A(p,1)$, but unfortunately, one can verify that $f(1)=0=A(p,1)$, thus this gives us no extra information about $\pi_0$.

Own attempt 2 : characteristic polynomial

We may define the characteristic polynomial for this recurrence relation as: $$ f(z) = (1-p)^3 + 3 p (1-p)^2 z + (3 p^2(1-p) - 1)z^2 + p^3 z^3, $$ and one can check that its roots are given as: $$ R_{1,2,3} = 1, 1+ \frac{1 \pm \sqrt{(1-p)^3(1+3p)} -3p^2}{2p^3}, $$ we should therefore be able to find $\alpha, \beta$ and $\gamma$ such that: $$ x_0=\alpha+\beta+\gamma, x_1=\alpha R_1 + \beta R_2 + \gamma R_3, x_2= \alpha R_1^2 + \beta R_2^2 + \gamma R_3^2. $$ It however does not seem easy to me to appropriately choose this $\alpha, \beta, \gamma$.

Answer 1

The trick here would be to use $\sum \limits_{n=0}^{\infty}x_n z^n = \frac{A(P,z)}{f(z)}$, cancel the common factor(s) of $z-1$ on the top and bottom, and then substitute $z=1$ into the expression, thus avoiding a $\frac{0}{0}$ situation that you've detailed.

Note: Some issues about taking this value will have to be sorted; you may need to prove convergence of the series on an open set containing $1$ and then prove continuity. I'm not sure if dividing directly is allowed; I don't know enough about the differences between formal power series and ordinary power series in general.

Answer 2

The corresponding characteristic equation is $$ p^3 \lambda^3+\left(3 (1-p) p^2-1\right) \lambda^2+3 p (1-p)^2 \lambda+(1-p)^3=0$$ which has roots $$ \lambda_1=1, \lambda_{2,3}=\frac{1-3p^2+2p^3\pm\sqrt{(p-1)^3(3p+1)}}{2p^3}. $$ Thus the general solution of the recurrence is $$ x_k=c_1+c_2\lambda_2^k+c_3\lambda_3^k. $$ Since $\sum_{k=0}^\infty x_k=1$, one must have $c_1=0$ and $|\lambda_{2,3}|<1$. Under this assumption, $$ \sum_{k=0}^\infty x_k=\frac{c_2}{1-\lambda_2}+\frac{c_3}{1-\lambda_3}=1.$$ Note $$ (1-\lambda_2)(1-\lambda_3)=\frac{3p-2}{p^3}. $$ Solving $$ c_2\lambda_2+c_3\lambda_3=x_1,c_2\lambda_2^2+c_3\lambda_3^2=x_2$$ gives $$ c_2=\frac{x_2-\lambda _3 x_1}{\lambda _2^2-\lambda _2 \lambda _3},c_3= \frac{\lambda _2x_1-x_2}{\left(\lambda _2-\lambda _3\right) \lambda _3}. $$ Using $$x_1=\frac{(1-p)^2(1+2p)}{p^3}x_0, x_2=\frac{(1-p)^3(1+3p-3p^3)}{p^6}x_0. $$ So $$ \frac{c_2}{1-\lambda_2}+\frac{c_3}{1-\lambda_3}=\frac{p^3x_0}{3p-2}=1 $$ gives $$ x_0=\frac{3p-2}{p^3}. $$