Find Closed-form expression of a integer sequence.

Question

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

Answer 1

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 $$