1
$\begingroup$

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?

$\endgroup$
3
  • 4
    $\begingroup$ By induction.$\,$ $\endgroup$
    – user436658
    Nov 21, 2020 at 12:19
  • $\begingroup$ Recursions are perfectly set up for induction. Say there were two such sequence, $a_n$ and $b_n$. We are told that $a_1=b_1$. Now use the recursion to show that $a_{n-1}=b_{n-1}\implies a_n=b_n$. $\endgroup$
    – lulu
    Nov 21, 2020 at 12:44
  • $\begingroup$ @Kthamil- You would set up the induction as follows: Suppose $a_n$ and $b_n$ are two sequences that both satisfy your recurrence. Then $P(n)$, the statement you want to prove is true for all $n$, is "$a_n = b_n$". Why don't you show us how you would use induction to prove it? (Note: I've left out one assumption you would need to complete the proof by induction. As you do the proof it should become clear what it is, and hopefully you will see why it is necessary.) $\endgroup$
    – JonathanZ
    Nov 21, 2020 at 12:47

1 Answer 1

1
$\begingroup$

Let $g\colon X\to X$ be any function and $x_1\in X$. Also assume that $f_1,f_2\colon \Bbb N\to X$ are functions with $f_1(1)=f_2(1)=x_1$ and with $f_1(n+1)=g(f_1(n))$ for all a $n$ and $f_2(n+1)=g(f_2(n))$ for all a $n$, respectively. Then $f_1=f_2$. Indeed, assume otherwise and let $m\in\Bbb N$ be minimal with $f_1(m)\ne f_2(m)$. Then certainly $m\ne 1$ as we know $f_1(1)=f_2(1)$. Hence $m=k+1$ for some $k\in\Bbb N$, and by minimality $f_1(k)=f_2(k)$. But then $$f_1(m)=f_1(k+1)=g(f_1(k))=g(f_2(k))=f_2(k+1)=f_2(m), $$ contradiction.

$\endgroup$

You must log in to answer this question.