3

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?

  • You're comparing apples to oranges, partly. I don't mean at the level of discrete versus differential: the issue I see is that exponential function is the solution to a first-order ODE. The solution you give for recurrence relations is for a second-order recurrence relation. – Semiclassical Jul 24 '14 at 05:12
  • Yeah, it would be better if you were more specific. – Thomas Andrews Jul 24 '14 at 05:13
  • 2
    http://en.wikipedia.org/wiki/Umbral_calculus – Adam Hughes Jul 24 '14 at 05:14
  • I'll try to add to the question, but I'm really just looking for any intuition on why we guess the solutions we do for recurrence relations. –  Jul 24 '14 at 05:14
  • For my part, I just mean that you should consider the solution $a r^n$ instead of having two terms. That way the analogy is sensible. – Semiclassical Jul 24 '14 at 05:16
  • I will fix that. –  Jul 24 '14 at 05:16

3 Answers3

4

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}$$

Thomas Andrews
  • 177,126
1

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.

M. Vinay
  • 9,004
  • Well, okay, but then why do they look the same? –  Jul 24 '14 at 05:25
  • 1
    Here's one thing that may help. Note that the proper analogy is with $\Delta y_n=y_{n+1}-y_n=ry_n\implies y_{n+1}=(1+r)y_n$. Therefore the solutions look like $y_n=a(1+r)^n=a e^{n\ln(1+r)}\sim e^{n r}$ if $r$ is small. – Semiclassical Jul 24 '14 at 05:35
0

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.

Semiclassical
  • 15,842
  • Sure, then. But then for a second order relation, and so on, why do we get this correspondence with the characteristic polynomial? It seems so... bizarre. –  Jul 24 '14 at 05:37
  • Try carrying it out for a recurrence relation of the form $a_n=c a_{n-1}+b a_{n-2}$ and seeing how this proceeds in that case. Though, you should also keep in mind---if you have a 2nd order ODE, your solutions look like a sum of exponentials. So it's not really anymore bizarre in the second order case as the first. – Semiclassical Jul 24 '14 at 05:40
  • What I mean is why is there a correspondence with the characteristic polynomial? In the case of differential equations it makes sense because the coefficients are dropping out of the exponential with each derivative, why is there a correlation in this case? –  Jul 24 '14 at 05:43
  • You're being too quick on the ODE side: the coefficients don't just drop out if you've got a second order ODE. You get a characteristic polynomial in that case as well. – Semiclassical Jul 24 '14 at 05:44
  • Do you mean something like $f^{(2)}(x) + f^{(1)}(x) + f(x) =0$ ? Because putting in $e^{\alpha x}$, it seems like each differentiation delivers an $\alpha$ which seems to justify the polynomial for me. –  Jul 24 '14 at 05:50
  • True. I think we're going around in circles on this---and I'll admit, much of my faith in these things comes move from being able to do power series methods like those above rather than guessing anything or remembering solutions to recurrences. @Anthony – Semiclassical Jul 24 '14 at 05:53
  • So then... is there not an intuitive reason for characteristic polynomials? –  Jul 24 '14 at 05:56
  • No, there is, I'm just failing to communicate it right now. (And I'll actually have to leave off there for now.) – Semiclassical Jul 24 '14 at 06:02