0

The four theorems which tells us how to convert recursion relation into equation can be verified but induction. But do we derive them at the first place ?

pbsh
  • 166
  • 4
  • Could you be a little more specific about just which theorems you have in mind? – Brian M. Scott Oct 24 '16 at 18:01
  • I have not yet learned to use the formatting tools, so please spare me. Theorems i'm talking about are the ones whic thel that the relation f(n)=af(n-1)+bf(n-2), can be written as x^n + y^n where x and y are the roots of the equation p^2 = a*p + b. And other theorems that generalize this for multi termed relations. – pbsh Oct 24 '16 at 18:17

1 Answers1

0

The technique for Solving homogeneous linear recurrence relations with constant coefficients is old enough that I don't know that you'll find a definitive reference as to how it originated.

A plausible guess, however, is that someone noticed that the $1^{st}$ order homogeneous linear recurrence $f(n) = a \cdot f(n-1)$ has the geometric progression $f(n)=a^n \cdot f(0)$ as the solution.

When stepping up to $2^{nd}$ order recurrences $f(n) = a f(n-1) + b f(n-2)$ it is only natural to wonder if those might, by any chance, have solutions in terms of geometric progressions as well.

To check that, one would assume a $f(n)=x^n$ form, then replacing in the definition of the recurrence it follows that $x^n = a x^{n-1} + b x^{n-2}$ or, after simplifying, $x^2 = a x + b$. Therefore any root $x_{1,2}$ of the characteristic polynomial $x^2 - a x - b$ provides a solution to the recurrence and, since the recurrence is linear, any combination $f(n) = \lambda x_1^n + \mu x_2^n$ satisfies the recurrence as well, where the constants $\lambda, \mu$ remain to be determined by the initial conditions $f(0), f(1)$.

( Looking back at the $1^{st}$ order recurrence form as to reconcile the terms, it can be rewritten as $f(n)=\lambda x_1^n$ where $x_1$ is the root of the characteristic polynomial $x-a=0$, and $\lambda = f(0)$ is the constant determined by the initial condition $f(0)$. )

The above extends to homogeneous recurrences of higher orders in a straightforward way.

dxiv
  • 76,497
  • this is fine. But what I was expecting was a formal procedure to arrive at the assumption. – pbsh Oct 25 '16 at 06:42
  • @Segmentation_fault The formal process is described in more detail at the wikipedia link on the first line of my answer above. I thought you were rather asking about the intuition behind it which, again as posted, is anybody's guess after all the time that passed. – dxiv Oct 25 '16 at 06:54