Recurrence relations and limits, tough.

Solution 1:

Let us start with the solution of the homogeneous recurrence $$\phi_n = \phi_{n-1} + \frac{\phi_{n-4}}{2}$$ its characteristic equation is $$x^4 - x^3 - \frac{1}{2} = 0$$ this equations has $4$ solutions, two of them are complex and the other two are a negative and a positive real number. Their approximate values, as given by Mathematica, are: $$z_1=1.25372, \ \ z_2=-0.669107, \ \ z_3=0.207691 + 0.743573 i, \ \ z_4=0.207691 - 0.743573 i,$$ (in your answer you label $z$ the one labeled $z_1$ above). Notice that the positive real solution $z=z_1=1.25372$ is the one with the greatest magnitude among the $4$ solutions (actually, it is the only one whose magnitude exceeds $1$).

Now, the general solution to the homogeneous recurrence is: $$\phi_n=c_1z^n_1+c_2z^n_2+c_3z^n_3+c_4z^n_4$$ where $c_1, c_2, c_3, c_4$ are constants to be determined from the initial conditions posed in your question. Since $z=z_1=1.25372$ has the greatest magnitude among the roots of the characteristic equation, the above general solution asymptotically (for $n$ large enough) tends to $c_1z^n$ i.e. $$\phi_n\sim c_1z^n$$ Consequently, $$\frac{\phi_n}{z^n}\sim c_1 \ \ \textrm{ i.e. } \ \ \lim_{n\rightarrow\infty}\frac{\phi_n}{z^n}=c_1$$ where $c_1$ will be determined by the solution of the $4\times 4$ linear system of equations $$ \phi_i=c_1z^i_1+c_2z^i_2+c_3z^i_3+c_4z^i_4 $$ for $i=0,1,2,3$, $p_i$ given by the initial conditions posted in the question and $z_1=z,z_2,z_3,z_4$ the roots of the characteristic equation given above.

Let me now try to justify why the convergence of $\frac{\phi_n}{z^n}$ implies also the convergence of $\frac{p_n}{z^n}$. The recurrence $$p_n = p_{n-1} + \left\lfloor \frac{p_{n-4}}{2} \right\rfloor = p_{n-1} + \frac{p_{n-4}}{2} - \epsilon_n$$ differs from the homogeneous, by a bounded function $0\leq\epsilon_n< 1$ of $n$. Since we are dealing with linear recurrences, increasing sequences $p_n$, $\phi_n$ and we are interested in the asymptotic behaviour of the solutions, in the limit of large $n$, the two are essentially the same. The solutions $p_n$ and $\phi_n$ differ by a $O(1)$ special solution (of the posted, non-homogeneous recurrence): $$ p_n=\phi_n+O(1) \Rightarrow p_n\sim\phi_n\Rightarrow\frac{p_n}{z^n}\sim \frac{\phi_n}{z^n}\Rightarrow\lim_{n\rightarrow\infty}\frac{p_n}{z^n}=c_1 $$ We can also see that the bigger the value of $P\geq 2$ (given in the initial conditions), the quicker $\frac{p_n}{z^n}$ converges.

P.S. Regarding the estimation that the general solutions $p_n$ and $ϕ_n$ of the respective recurrences, differ by a $O(1)$ special solution of the non-homogeneous, my argument is the following: when dealing with non-homogeneous linear recurrences with constant coefficients i.e. $$ p_n+c_1p_{n−1}+...+c_dp_{n−d}=h(n) $$ and $h(n)=const$, then it is customary to seek for a special solution to be a constant. Since here, the non-homogeneous factor is the bounded function $0\leq\epsilon_n< 1$, I guess that it is reasonable to conjecture that the corresponding special solution is $O(1)$.

Solution 2:

Consider the vector $X_n = (p_n, p_{n-1}, p_{n-2}, p_{n-3})$. We have $$ \begin{eqnarray} X_{n+1} &=& (p_{n+1},p_n, p_{n-1},p_{n-2}) \\ &=& \left(p_n+\left\lfloor \frac{1}{2}p_{n-3}\right\rfloor, p_n, p_{n-1}, p_{n-2}\right) \\ &=& (p_n+ \frac{1}{2}p_{n-3}, p_n, p_{n-1}, p_{n-2}) - (\varepsilon_n, 0, 0, 0)\\ &=&\hat{M}\cdot X_{n} + \varepsilon_n E, \end{eqnarray} $$ where $|\varepsilon_n| < 1$, $E=(-1,0,0,0)$, and $$ \hat{M}=\left( \begin{matrix} 1 & 0 & 0 & \frac{1}{2} \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix}\right). $$ Let $\lambda_{i=1,2,3,4}$ and $u_i$ be the eigenvalues and normalized eigenvectors of $\hat{M}$. Only $\lambda_1 = z \approx 1.25372$ has magnitude greater than $1$; the other eigenvalues have magnitudes strictly less than $1$. We can write $E=\sum_i e_i u_i$ for some fixed coefficients $e_i$. Now, writing $X_n=z^n \sum_i c_{i,n} u_i$, we have $$ z^{n+1}\sum_i c_{i,n+1}u_i = X_{n+1}=\hat{M}\cdot X_n + \varepsilon_n E = z^n \sum_i c_{i,n} \lambda_i u_i + \varepsilon_n \sum_i e_i u_i; $$ or simply $$ c_{i,n+1} = \left(\frac{\lambda_i}{z}\right) c_{i,n} + \frac{\varepsilon_n e_i}{z^{n+1}}. $$ Because $|\varepsilon_n|$ is bounded, $\lim_{n\rightarrow \infty}c_{i,n}$ exists for each $i$ (and is zero for $i\neq 1$). Therefore $X_n / z^n=\sum_i c_{i,n}u_i$ has a limit, as does its first component, $p_n/z^n$.