0

How do I go about proving the uniqueness of an existing solution to a recurrence equation of the form

$$ a_{n+1} - f(n)a_n = 0 $$ ?

Is there a theorem related to questions of uniqueness and existence for recurrence relations of a certain type as is the case for ordinary differential equations?

Nicola
  • 89
  • 6
  • 1
    Solving a recurrence relation is very similar (if not equivalent) to solving a differential equation. I would also tag differential equations and see if anyone can help you there. – Jared Apr 03 '14 at 06:15
  • What is the uniqueness proof for ordinary differential equations? I think it should be applicable to recurrence relations (as per my previous comment). – Jared Apr 03 '14 at 06:17
  • This is a (very simple) homogeneous linear recurrence of the first order, just not with constant coefficients. – vonbrand Apr 06 '14 at 01:31

1 Answers1

3

Hint

If the recurrence equation is of the form $$a_{n+1} - f(n)a_n = 0$$ you could easily show that the solution is simply given by $$a_n=c \prod _{i=1}^{n-1} f(i)$$

Claude Leibovici
  • 260,315
  • Oh! Well that's simple enough to make me feel kind of sheepish :P. Thank you! How, then, now, do I prove that that is the ONLY solution? – Nicola Apr 03 '14 at 06:33
  • Just write the first terms and substitute. This is how I arrived to this formula. I do not see how, from the definition itself, another solution could exist. – Claude Leibovici Apr 03 '14 at 06:38