Given a fixed $x_0$ can a reccurence relation give rise to two distinct sequences? If two sequences have the same initial term and satisfy the same reccurence relation $f(a_{n+1}, a_n) = c$ for some constant $c$, are the sequences necesarily the same?
I was trying to make up with an example. My guess was to construct something involving $x_n^2$ or $|x|$, the idea being that I can find two sequences whose corresponding terms are equal in magintude, but whose signs differ for some terms. However, simple examples such as $x_{n+1} ^2 = x_n$ did not work.
For context, I was trying to solve this problem:

Let $\{x_n\}$ be a sequence f nonzero real numbers such that $x_n^2-x_{n-1}x_{n+1} = 1$ for $n \ge 1.$ Prove that there exists a real number $a$ such that $x_{n+1} = ax_n - x_{n-1}$ for all $n \ge 1$.

Assuming the conclusion, I found that we must have $x_{n} = x_0 + n$ for $n \ge 1$. Thus for an actual proof, I was thinking to say:
"For any $x_0 \in \mathbb{R}$, the sequence $x_{n+1} = x_0 + n$ with $n \ge 1$ satisfies the reccurence relation. Moreover, since any solution of the relation is uniquely determined by its initial term $x_0$ and the relation, these are all the solutions. And with the explicit solution, it is easy to check that there is a constant $a$ such that $x_{n+1} = ax_n - x_{n-1}$ for all $n \ge 1$.
 A: It depends on the recurrence relation.  If the recurrence only relates $x_{n+1}$ to $x_n$ and you can solve for $x_{n+1}$ then one term determines the whole series.  If it relates things two steps back, like the Fibonacci recurrence $x_{n+1}=x_n+x_{n-1}$ you need two starting terms to determine the relation.  The usual Fibonacci series has $x_0=0,x_1=1$, but if you start with $x_0=0,x_1=0$ all the terms are $0$.  If you can solve the relation for the latest term, you need as many starting terms as the earliest one on the right, so $x_{n+1}=x_n+x_{n-4}$ would need five starting terms.
A: If the recurrence
is of the form
$(x_{n+1})^2 = f(x_n)$
then there can be
an arbitrary number of solutions
for a given $x_0$
just by choosing
differently signed values
of $x_{n+1}$
at each value of $n$.
For example,
look at
$(x_{n+1})^2 
= (x_n+2)^2
$
and,
for any real $r$,
choose the sign
at $n+1$
of
$(-1)^{\lfloor 2(r2^n-\lfloor r2^n \rfloor) \rfloor}
$.
This gives an uncountable number
or solutions to the recurrence
for any initial condition.
