1
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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$. $\endgroup$ Aug 19, 2015 at 16:05
  • $\begingroup$ That is the regular way I said, but the rest is not easy $\endgroup$ Aug 19, 2015 at 16:09
  • 2
    $\begingroup$ $$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).$$ $\endgroup$ Aug 19, 2015 at 16:14

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.