Why, intuitively, does the solution to a general linear recurrence relation make sense?

Question

I reasoned through the solution to a differential equation, and $e^{\alpha x}$, for better or worse, seems to make sense. Each derivative sending the function to itself seems to suggest $e^{\alpha x}$. Why does the solution to recurrence relations, $ar_1^n$ make sense?

Edit: To try to fix the misguided question, regardless of the poor analogy I gave to differential equations, my question is Why do we guess the solution that we do for recurrence relations. I know it can be shown to work, but what is the intuition?

Answer 1

If $f(z)=\sum_{n=0}^\infty \frac{a_n}{n!}z^n$ is a solution to the differential equation, then $a_i$ is a solution to the related recurrence relation, and visa versa. You can just do the arithmetic.

So if $b_n=a_1r_1^n+a_2r_2^n$ then $$f(z)=\sum_{n=0}^\infty \frac{b_n}{n!}z^n = a_1e^{r_1z} + a_2e^{r_2z}$$

Answer 2

The solution $y = ar^n$ is the solution to $y_{n + 1} = r y_n$, and not $\Delta y_n = r y_n$. In discrete calculus, $\Delta$ is the analogue (or at least one analogue) of $\text D \equiv \dfrac{d}{dx}$. But $y_{n + 1} = \text{E}\,y_n$, where $\text{E}$ is the shift operator, and that is not analogous to $\text D$.

You are asking why we guess this solution. Why do we guess $y = e^{ax}$ for $\text D\, y = ay$? Because we have observed that $\text D\, e^{ax} = ae^{ax}$. Similarly, when playing around with discrete differences, we observe that for $y_n = r^n$, $y_{n + 1} = r^{n + 1} = r \times r^n = ry_n$. So obviously, this is a solution to the difference equation $y_{n + 1} = ry_n$.

But the solutions are not all that different, after all, because $r^n$ is an exponential function too. You may even write it as $e^{n\log r}$, if you wish.

Answer 3

An alternative of trying to 'guess' a solution is to derive it using the "generating function" approach. (To continue the ODE comparison, it's the equivalent of solving via Laplace transforms.)

Suppose we start with the simple recurrence relation $a_{n}=ra_{n-1}$. Consider the formal power series in $x$ defined by $A(x)=\sum_{n=0} a_n x^n$. (By formal, I mean that I won't worry about issues of convergence and the like.) Then $$A(x) = \sum_{n=0}^\infty a_n x^n = a_0+\sum_{n=1}^\infty a_{n}x^n =a_0+\sum_{n=1}^\infty r a_{n-1}x^n = a_0+rx A(x)\\ \implies A(x)=\frac{a_0}{1-r x}=\sum_{n=0}^\infty a_0 r^n x^n\implies a_n = a_0 r^n$$ So the solution need not be found by 'guess and check' but can instead be algebraically derived.