1
$\begingroup$

I have the following recurrence relation: $$x_1=1, x_2=a, x_{n+2}=ax_{n+1}-x_n\hspace{1cm}(*)$$

If we assume that $x_n=r^n$ is a solution for the relation $x_{n+2}=ax_{n+1}-x_n$, then I can deduce that $r=\frac{a+\sqrt{a^2-4}}{2}$ or $r=\frac{a-\sqrt{a^2-4}}{2}$.

By using the initial values $x_1=1, x_2=a$, I found that $$x_n=\frac{1}{\sqrt{a^2-4}}\left(\frac{a+\sqrt{a^2-4}}{2}\right)^n-\frac{1}{\sqrt{a^2-4}}\left(\frac{a-\sqrt{a^2-4}}{2}\right)^n$$ is a solution for the recurrence relation (*).

Question: How do we know whether this is the only solution for the recurrence relation $(*)$? Notice that when I found the particular solution above I assumed that the solution was a linear combination of geometric series. But I do not know if all the solutions will have this form.

$\endgroup$
3
  • $\begingroup$ Use method of difference on the recursive definition $ x_{n+2}-x_{n+1}=(a-2)x_{n+1}+x_{n+1}-x_{n}$ and add these equations for all values of n. $\endgroup$
    – Pi_die_die
    Commented Jul 8, 2018 at 20:57
  • $\begingroup$ In other words, prove that it satisfies condition $(*)$. $\endgroup$
    – Steven Alexis Gregory
    Commented Jul 8, 2018 at 20:59
  • $\begingroup$ Yes you would get the sum which would be the type of sum you would expect from a gp $\endgroup$
    – Pi_die_die
    Commented Jul 8, 2018 at 21:01

2 Answers 2

Reset to default
4
$\begingroup$

You have specific initial values $x_0$ and $x_1$. The recurrence relation fully determines all other values. Thus, there's exactly one solution. If you've found it, that's it, there can't be any others, no matter what approach you took in order to find it.

If you want to show that all solutions of $x_{n+2}=ax_{n+1}-x_n$ are combinations of the geometric series you found, you can argue as follows:

This is a linear second-order recurrence. Its solutions form a two-dimensional vector space. (A vector space because of the linearity of the recurrence, and a two-dimensional one because the solution space is spanned by the two solutions for the initial conditions $x_1=1$, $x_2=0$ and $x_1=0$, $x_2=1$.) You've found two linearly independent solutions; hence they span the entire solution space.

$\endgroup$
5
  • $\begingroup$ Hi @joriki I would appreciate some clarifications before I accept your answer. I understand that the set of solutions is a subspace of the vector space of sequences $\{f:\mathbb{N}\to\mathbb{C}: f\mbox{ is a function}\}$. I also understand that I found two solutions that are linearly independent. I do not know why the dimension of the solution space is 2 and not greater than 2. Also, what do you mean by $a_0$ and $a_1$? $\endgroup$
    – Chilote
    Commented Jul 8, 2018 at 21:23
  • $\begingroup$ @Chilote: I'm sorry, I meant $x_1$ and $x_2$; I've fixed that. The solution for given initial conditions $x_1=\hat x_1$ and $x_2=\hat x_2$ is $\hat x_1s_1+\hat x_2 s_2$, where $s_1$ is the solution for $x_1=1$ and $x_2=0$ and $s_2$ is the solution for $x_1=0$ and $x_2=1$; so $s_1$ and $s_2$ span the solution space; hence it's at most two-dimensional (in fact exactly two-dimensional, since $s_1$ and $s_2$ are linearly independent). $\endgroup$
    – joriki
    Commented Jul 8, 2018 at 21:31
  • 1
    $\begingroup$ Got it, the solution space of $x_{n+2}=ax_{n+1}-x_n$ is $S=\{(x_n)_n:x_{n+2}=ax_{n+1}-x_n\}$ which is a vector space. Any vector in this space is of the form $x=(x_1,x_2,ax_2-x_1,a(ax_2-x_1)-x_2,\dots)=x_1 s_1+x_2 s_2$ where $s_1$ and $s_2$ are two particular solutions that are linearly independent. $\endgroup$
    – Chilote
    Commented Jul 8, 2018 at 21:49
  • 1
    $\begingroup$ You've found two linearly independent solutions Just to nitpick, that's iff $a \ne \pm 2$. $\endgroup$
    – dxiv
    Commented Jul 8, 2018 at 23:29
  • $\begingroup$ @Chilote: This was actually overkill, since you only asked about the uniqueness of one particular solution, not about all solutions being combinations of the geometric series. I edited the answer accordingly. $\endgroup$
    – joriki
    Commented Jul 9, 2018 at 5:22
2
$\begingroup$

A bit of culture. Any two consecutive numbers in your sequence, call them $x_n$ and $x_{n+1},$ satisfy $$ x_n^2 - a \, x_n \, x_{n+1} + x_{n+1}^2 = 1 $$

Try consecutive values in $$ 1, \; \; a, \; \; a^2 - 1, \; \; a^3 - 2a, \; \ldots $$

This comes from the matrix $$ \left( \begin{array}{cc} 0 & 1 \\ -1 & a \end{array} \right) $$ which has determinant $1$ and trace $a.$ It also gives an automorphism of the quadratic form $x^2 - a xy+y^2.$ An automorphism matrix $P$ for a quadratic form that has Hessian matrix $H$ satisfies $P^T HP = H$

In this case $$ \left( \begin{array}{cc} 0 & -1 \\ 1 & a \end{array} \right) \left( \begin{array}{cc} 2 & -a \\ -a & 2 \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ -1 & a \end{array} \right) = \left( \begin{array}{cc} 2 & -a \\ -a & 2 \end{array} \right) $$

The explicit relation with the sequence is

$$ \left( \begin{array}{cc} 0 & 1 \\ -1 & a \end{array} \right) \left( \begin{array}{c} x_n \\ x_{n+1} \end{array} \right) = \left( \begin{array}{c} x_{n+1} \\ x_{n+2} \end{array} \right) $$

$\endgroup$
4
  • $\begingroup$ How can I get the first equality? $\endgroup$
    – Chilote
    Commented Jul 8, 2018 at 21:52
  • 1
    $\begingroup$ @Chilote the automorphism group for an (indefinite) binary quadratic form, along with the Pell type equation $\tau^2 - \Delta \sigma^2 = 4,$ is discussed in many number theory and quadratic forms books. $\endgroup$
    – Will Jagy
    Commented Jul 8, 2018 at 23:24
  • $\begingroup$ I think the quadratic form corresponding to the matrix you wrote above is $ay^2$ $\endgroup$
    – Chilote
    Commented Jul 8, 2018 at 23:59
  • 1
    $\begingroup$ @Chilote I put in a little about the automorphism. The matrix that gives the quadratic form is the symmetric one; it is just the Hessian matrix of second partial derivatives $\endgroup$
    – Will Jagy
    Commented Jul 9, 2018 at 0:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .