I would like to know if there is a general method to prove the uniqueness of a solution to a recurrence relation, if yes can you provide an example?
I have a simple recurrence relation in mind, the following $$a_n=2a_{n-1} -1$$ with $a_1=3$ whose solution is $$a_n=2^n +1$$ now this is a linear recurrence relation and techniques from linear algebra could be used to prove the uniqueness, but I am not looking for a way to prove uniqueness by using the linearity of the relation but rather a more general method that would apply to nonlinear relations as well.
So how can I show that $a_n=2^n +1$ is the only solution?