nor's blog

[Tutorial] An elementary way of solving recurrences
By nor, 10 months ago, In English

https://nor-blog.codeberg.page/posts/2024-01-07-recurrence-trick/

  • Vote: I like it
  • +131
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +8 Vote: I do not like it

nor is back with the fire blogs. orz

→ Reply
»
10 months ago, # |
  Vote: I like it +8 Vote: I do not like it

One simple way to explain why it symbolically corresponds to the factorization of characteristic polynomial is via shift operators.

Let $$$\Delta$$$ act on sequences of real numbers, so that $$$\Delta x_k = x_{k-1}$$$. Then, $$$x_k = a x_{k-1} + b x_{k-2}$$$ rewrites as

$$$ x_k = (a\Delta + b \Delta^2) x_k, $$$

while $$$y_k = x_k - d x_{k-1}$$$ rewrites as $$$y_k = (1 - d \Delta) x_k$$$ and $$$y_k = e y_{k-1}$$$ rewrites as $$$y_k = e \Delta y_k$$$, or $$$(1-e\Delta) y_k = 0$$$.

Now, moving everything to the left side in the identity for $$$x_k$$$, we get

$$$ (1-a \Delta - b \Delta^2) x_k = 0, $$$

while for $$$y_k$$$ we get

$$$ (1-e\Delta) y_k = (1-e\Delta)(1-d\Delta) x_k = 0. $$$

So, after substituting $$$\Delta \to x$$$, we get an equation

$$$ (1 - a x - bx^2) = (1-ex)(1-dx). $$$

After this, we also need to explain the recovery of $$$x_k$$$ step. The solution to $$$(1-e \Delta) y_k = 0$$$ is $$$y_k = e^k y_0$$$, so

$$$ (1-d \Delta) x_k = e^k y_0. $$$

To solve this, we may notice $$$(1-d\Delta)(1+d\Delta + d^2 \Delta^2 + \dots) = 1$$$, so if $$$e \neq d$$$ we get

$$$ x_k = (1+d\Delta + d^2 \Delta^2 + \dots) e^k y_0 = y_0 \sum\limits_{i=0}^k e^{k-i} d^i = y_0 \frac{e^{k+1} - d^{k+1}}{e-d}, $$$

and if $$$e=d$$$ we get

$$$ x_k = (1+e\Delta+e^2\Delta^2+\dots)e^k y_0 = y_0 \sum\limits_{i=0}^k e^k = y_0 (k+1) e^k. $$$
→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Indeed. The way I think of it now is via formal variables (or umbral calculus) — which is the same as shift operators if you realize the equivalence due to having the same underlying structure — but I wanted to provide a presentation that doesn't involve something as advanced, and is accessible to someone who knows middle school math.

    You can investigate such problems further using the method for the examples I showed, and generalize it to get to a structure that is essentially the same as what you describe. However, I feel that rather than presenting polished theory all the time (so polished that someone might wonder "where the hell did this come from?"), we should focus on making ideas more memorable and derivable from scratch.

    As an aside, the point of the blog was the statement presented in the conclusion — the idea is much more general than the details I showed here for a few applications.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 4   Vote: I like it +8 Vote: I do not like it

      I don't think the idea of introducing a symbol $$$\Delta$$$ such that $$$\Delta x_k = x_{k-1}$$$ is, in any way, advanced?

      Well, the last paragraph using $$$1+e\Delta+e^2\Delta^2+\dots$$$ probably is advanced, but not the stuff preceding it.

      I honestly think that it is, generally, a dis-service to people to zealously stick to only the things they're familiar with, rather than giving them the proper tools that, albeit new at first, will allow to simplify low-level manipulations tremendously. To me, the first question I had after learning of the correspondence between characteristic polynomials and shift operators was along the lines of "wow, it makes it so simple, why the hell did they do all this technical stuff before, if it could have been avoided so easily and elegantly?"

      Also, if we're going to employ wishful thinking anyway, one simpler way would be to directly wish for $$$x_k = \lambda^k$$$, meaning that $$$\lambda^{k+1} = a \lambda^k + b\lambda^{k-1}$$$, which directly leads to $$$\lambda^2 = a \lambda + b$$$. Then, after finding out that there are several possible $$$\lambda$$$, we adjust the "wish" to say that we now want that $$$x_k$$$ is their weighted sum. This is also a heuristic with very little prerequisite to understand, and maybe less technical...

      I guess, I'm generally a bit annoyed that in mathematics "elementary" only implies "have no pre-requisites" rather than "simple to work with", which often means that using it may yield lines upon lines of technically moving things around with only hope that it will maybe work out in the end. It's an obvious trade-off between simplicity of introducing the tool and simplicity of actually using the tool to get some fruitful results, and the one I dislike at that.

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think adding a symbol $$$\Delta$$$ and making sure that all its properties are consistent with the "usual" operations that we like is something not a lot of people can grasp easily.

        I honestly think that it is, generally, a dis-service to people to zealously stick to only the things they're familiar with, rather than giving them the proper tools that, albeit new at first, will allow to simplify low-level manipulations tremendously...

        I agree, I've written blogs earlier that are in the same spirit. However, my aim with this blog was to not do that, but to provide a way of thinking rather than give specific tools. You can note this from the tone of the conclusion section — the blog, although being about about recurrences, also points out the main ideas that can be abstracted out in a manner (divide and conquer, lifting) different from the concrete application we use here (which can be generalized to shift operators, umbral calculus and so on).

        Also, if we're going to employ wishful thinking anyway, one simpler way would be to directly wish for...

        That method, in my opinion, assumes way too much to be reasonable. Guessing + induction/verification is an extreme of wishful thinking. All algebraic manipulations can be thought of as wishful thinking at some point, even. Assuming the form of the solution is something you can't get directly and reliably from considering special cases (ignoring the fact that you can guess the solution from solutions for lower orders, but higher orders can behave very differently — for example, look at what happens when there are complex roots of the characteristic polynomial). Since the method is something I came up with when I was a kid who didn't know so much higher math, I think it has its own value, since it has only that amount of wishful thinking that a middle school student can come up with on their own, and it involves a separate problem solving method that someone at their level can understand.

        I guess, I'm generally a bit annoyed that in mathematics "elementary" only implies "have no pre-requisites" rather than "simple to work with", which often means that using it may yield lines upon lines of technically moving things around with only hope that it will maybe work out in the end. It's an obvious trade-off between simplicity of explaining the tool and simplicity of actually using the tool to get some fruitful results, and the one I dislike at that.

        Well, so do I. But we can't force people to read math if they don't understand the beauty of abstraction. This is precisely the math version of the Blub paradox, and we can't do anything about it. By the way, there is a reason (and that is probably this same thing) why there exists a significant correlation between students that are highly successful at the IMO, and students at the IMO who know higher math.

        → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Also, speaking of making things more memorable and derivable from scratch. In your approach, the correspondence between characteristic polynomials and solutions to the recurrence appears magical and almost accidental. The only way to derive it again, if you forgot about it, is to repeat the whole process of technical manipulations from scratch. I don't think it's in any way as memorable as approaches in which factorization pops up naturally as a part of the idea, rather than as a seemingly "lucky coincidence".

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I agree that the correspondence is more memorable in the more advanced method (one could argue that it is the notation that makes is much more memorable, but I won't argue about that).

        However, the idea I was referring to in my comment was the one about trying to impose structure, and not how you actually solve the equation. It's one of those guiding ideas like "durr, we want stuff to cancel!" but explained via examples.

        → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't understand what you mean by "substituting $$$\Delta \to x$$$", isn't this basically saying you assume that $$$x_k=x_0 \cdot x^{-k}$$$ for some $$$x$$$?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I just mean it to convert the equation $$$(1-a\Delta - b \Delta^2) = (1-e\Delta)(1-d\Delta)$$$ into a more familiar notation by a symbolic substitution. If this expression is written with a symbolic $$$x$$$, then we know that $$$e$$$ and $$$d$$$ are essentially the roots of $$$x^2-ax-b$$$. So, this substitution is only used to find $$$e$$$ and $$$d$$$.

      → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm stuck on "so we have". It is not an obvious transition, yet from the text it seems that it should be immediately obvious (It should be possible to deduce from the equations on the right, but I don't get how it is done so instanteniously)

Next sentence "note how this relates to solving a quadratic", well, took me a while to understand that it is a reference to Vieta without mentioning it.

I feel like for a post claiming to be targeted at people without math background this post omits too much.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the feedback. I did assume a bit of familiarity with quadratic equations, seems like I should have been more explicit. The math background I was talking about was fairly advanced (beyond high school level), in that it takes a lot of background to start talking about generating functions or characteristic equations, and most people simply never get to that point. However, most people do get to know how to solve quadratic equations in their school math classes, so I felt it was justified assuming some familiarity with them.

    About the "so we have" — do you mean the equation where we compute $$$|d - e|$$$? If you're still stuck, you can note that $$$(d - e)^2 = d^2 - 2de + e^2 = d^2 + 2de + e^2 - 4de = (d + e)^2 - 4de$$$, and on taking square roots, we get what is claimed. By the way, this is a standard trick when you solve quadratic equations, and I think this is taught in schools. The equation itself should be quite simple though.

    About the "note how this relates to solving a quadratic" — it is a continuation of what I said about quadratic equations above. I don't really think about Vieta's relations as a separate thing in this case (they seem overkill here): if you just expand the equation $$$x^2 - ax - b = (x - d)(x - e) = x^2 - (d + e)x + de$$$ as I hinted towards by using the word factorization, it should be clear what I am talking about.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      /nevermind/

      → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      lol

      Revisiting after a few days and finally understanding what was meant and what was my problem,

      "d + e = a and de=-b), So we have |d-e|=sqrt((d + e)^2-4de)", so I tried to reconcile how from (d + e = a and de=-b) somehow obviously follows an expression for |d-e| even though it has nothing to do with it.

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah, makes sense now. I intended the "so we have" for the latter half of the equation, it could definitely have been worded better on my part.

        → Reply
»
10 months ago, # |
  Vote: I like it +6 Vote: I do not like it

good to know

→ Reply