# 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

• The general solution has almost the same form: $$u_{n+1}= C_1 \left( p+\sqrt{p^2-1} \right)^n + C_2 \left(p- \sqrt{p^2-1} \right)^n.$$ Now set $n=0,1$ and solve the resulting system of linear equations for $C_1,C_2$. Aug 19, 2015 at 16:05
• That is the regular way I said, but the rest is not easy Aug 19, 2015 at 16:09
• $$C_1=\frac12\left(1+\sqrt{\frac{p-1 }{p+1}}\right), \qquad C_2=\frac12\left(1-\sqrt{\frac{p-1 }{p+1}}\right).$$ Aug 19, 2015 at 16:14

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