0
$\begingroup$

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 ?

$\endgroup$
2
  • $\begingroup$ Could you be a little more specific about just which theorems you have in mind? $\endgroup$ Commented Oct 24, 2016 at 18:01
  • $\begingroup$ 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. $\endgroup$
    – pbsh
    Commented Oct 24, 2016 at 18:17

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ this is fine. But what I was expecting was a formal procedure to arrive at the assumption. $\endgroup$
    – pbsh
    Commented Oct 25, 2016 at 6:42
  • $\begingroup$ @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. $\endgroup$
    – dxiv
    Commented Oct 25, 2016 at 6:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .