Hi,
I'm not sure I entirely understand your example but generally recurrence relations can be proven using mathematical induction. Studying proof by mathematical induction will help. The same of method of proof that allows us to prove things like:
\sum_{i=1}^{n} i = \frac {n(n + 1)} {2}
Also...