Find Closed-form expression of a integer sequence. We have a integer sequence $u_{n+1}=2p.u_{n}-u_{n-1}$ (p is a positive integer, $n\geq 3$ )


*

*When $u_{1}=1; u_{2}=p$ then with a regular way I can find Closed-form expression of the sequence.


$u_{n+1}=((p+\sqrt{p^{2}-1})^{n}+(p-\sqrt{p^{2}-1})^{n}).\frac{1}{2}$


*

*But when $u_{1}=1; u_{2}=2p-1$, how much I try, I can not find out it's Closed-form expression.


So can someone show me how to find it or explain to me why we can not find it
 A: One way to find a general solution is to use generating functions. Define:
$$
U(z) = \sum_{n \ge 0} u_n z^n
$$
Rewrite the recurrence shifting indices:
$$
u_{n + 2} = 2 p u_{n + 1} - u_n
$$
Multiply the recurrence by $z^n$, sum over $n \ge 0$, recognize some sums:
$$
\frac{U(z) - u_0 - u_1 z}{z^2}
  = 2 p \frac{U(z) - u_0}{z} - U(z)
$$
Solve for $U(z)$, split into partial fractions:
$\begin{align}
U(z)
  &= \frac{u_0 + (u_1 - 2 p u_0) z}{1 - 2 p z + z^2} \\
  &= \frac{u_0 (\sqrt{p^2 - 1} - p) + u_1}
          {2 \sqrt{p^2 - 1} (1 - (\sqrt{p^2 - 1} + p) z)}
       + \frac{u_0 (\sqrt{p^2 - 1} - p) - u_1}
              {2 \sqrt{p^2 - 1} (1 + (\sqrt{p^2 - 1} - p) z)}
\end{align}$
This is just two geometric series:
$$
u_n
  = \frac{u_0 (\sqrt{p^2 - 1} - p) + u_1}{2 \sqrt{p^2 - 1}}
      \cdot \left( \sqrt{p^2 - 1} - p \right)^n
       + \frac{u_0 (\sqrt{p^2 - 1} - p) - u_1}{2 \sqrt{p^2 - 1}}
      \cdot \left( \sqrt{p^2 - 1} + p \right)^n
$$
Edit: The above is valid for $p \ne 1$ only. In case $p = 1$:
$\begin{align}
U(z)
  &= \frac{u_0 + (u_1 - 2 u_0) z}{1 - 2 z + z^2} \\
  &= \frac{u_0 + (u_1 - 2 u_0) z}{(1 - z)^2}
\end{align}$
Here we could got the partial fraction route too, but we have another option:
$\begin{align}
U(z) 
  &= (u_0 + (u_1 - 2 u_0) z) \sum_{n \ge 0} (-1)^n \binom{-2}{n} z^n \\
  &= (u_0 + (u_1 - 2 u_0) z) \sum_{n \ge 0} \binom{n + 2 - 1}{2 - 1} z^n \\
  &= (u_0 + (u_1 - 2 u_0) z) \sum_{n \ge 0} (n + 1) z^n \\
  &= \sum_{n \ge 0} u_0 (n + 1) z
       + \sum_{n \ge 0} (u_1 - 2 u_0) (n + 1) z^{n + 1}
\end{align}$
The coefficient of $z^n$ is now:
$$
u_n = u_0 + (n_1 - u_0) n
$$
