Question

Technique I'm trying to work out for finding the general term for recurrence relations of a special form.

Answer 1

\[a_{n+1}+p_n a_n = q_n\]
You're given \(p_n\) and \(q_n\) as functions of n, they could be like \(n^3\) for instance. And we're also given the terms to do recurrence, \(a_0\) and \(a_1\).

So what's \(a_n\)?

Answer 2

Here's my idea, to solve it like a differential equation, I'l make up my own series of terms, and call them \(\mu_n\) and multiply it by this recurrence relation:

\[a_{n+1}+p_n a_n = q_n\]
Multiply through by \(\mu_{n+1}\)
\[\mu_{n+1}a_{n+1}+\mu_{n+1}p_n a_n = \mu_{n+1}q_n\]
Since \(\mu_n\) are arbitrarily made up by me, I will say it satisfies this relationship:
\[\mu_{n+1} p_n = -\mu_n\]
Plug it in:
\[\mu_{n+1}a_{n+1}-\mu_n a_n = \mu_{n+1}q_n\]
So now \(\mu_{n+1}q_n\) is the difference between two consecutive terms of \(\mu_na_n\) so if we add up both sides by a bunch of consecutive terms we'll have something like this:

\[\sum \mu_{n+1}a_{n+1}-\mu_n a_n =\sum \mu_{n+1}q_n\]

So the left will end up collapsing as a telescoping series:

\[\mu_n a_n = \sum \mu_{n+1}q_n\]
Rearrange to get:
\[ a_n = \frac{1}{\mu_n}\sum \mu_{n+1}q_n\]
So now it looks like we have the nth term but we still have to solve for \[\mu_{n+1} p_n = -\mu_n\] and we could also plug this into that sum to make it look a little different but still the same answer:


\[ a_n = \frac{-1}{\mu_n}\sum \frac{q_n}{p_n} \mu_n\]

So I don't know if this is exactly the same thing as solved, but this looks pretty useful.

Answer 3

Yeah I'll admit some of the reasoning is kinda weird, not too sure about this telescoping series part, but anyways I guess it's simple enough to just sorta try to test it out maybe?

Answer 4

\[\sum \mu_{n+1}a_{n+1}-\mu_n a_n =\sum \mu_{n+1}q_n \\ \text{ wouldn't this be } \\ -\mu_o a_o=\sum \mu_{n+1} q_n\]

Answer 5

that seems weird though

Answer 6

\[\mu _n a_n-\mu_0 a_0=\sum_{k=0}^n u_{k+1} q_k\]

Answer 7

\[\sum \mu_{n+1}a_{n+1}-\mu_n a_n =\sum \mu_{n+1}q_n\]

I'll clarify this to really mean I am looking at this:

\[\sum_{k=r}^{n-1} [\mu_{k+1}a_{k+1}-\mu_k a_k] =\sum_{k=r}^{n-1} \mu_{k+1}q_k\]

This left hand side will specifically collapse down to this:

\[\sum_{k=r}^{n-1} [\mu_{k+1}a_{k+1}-\mu_k a_k] = \mu_na_n-\mu_ra_r\]

But I haven't specified what \(r\) is so I can set it to be anything, so I guess I'm assuming there's some r I can pick that will make either \(\mu_r\) or \(a_r\) equal to 0, and that will be very simple to do if I'm given \(a_0=0\) for example. So now I have:

\[a_n = \frac{1}{\mu_n}\sum_{k=r}^{n-1} \mu_{k+1}q_k\]

This sum now starts at r=0 or whatever we like, but it doesn't matter because we'll end up just having to put a constant with it, cause this is the sum of differences... Kinda confusing I think hahaha.


\[a_n = \frac{1}{\mu_n}\left( C + \sum_{k=r}^{n-1} \mu_{k+1}q_k \right)\]

If you try to go backwards with this, and undo the summation then the C term will go away. I can explain more it's sorta weird and I've been spending some time getting comfortable with this, it's sorta like realizing that in calculus when the write:

\[x^2 = \int 2x dx\]
The x on the left is not the x on the right. Really it's more like:

\[x^2 = \int_0^x 2t dt\]

So that's why I originally wrote the summation without bounds.

Answer 8

Actually the way I described that was bad, we don't have to choose r=0 or anything like that. We can still have \(\mu_r a_r \ne 0\), this thing really just amounts to being our constant of 'integration'.

Answer 9

seems interesting

Answer 10

it works almost just like solving a first order linear differential equation

Answer 11

solving that one equation in a general way might be hard though
I'm talking about the
\[\mu_n=-\mu_{n+1}p_n\]

Answer 12

Yeah, I was thinking about it, and I think I figured out a way to solve it:

\[\mu_{n+1} = \tfrac{-1}{p_n} \mu_n\]
Let's just call the first index of \(p_n\) to be \(n=0\) although it doesn't have to be I guess this make it easier to follow the argument. Then we have:

\[\mu_1 = \tfrac{-1}{p_0}\mu_0\]
\[\mu_2 = \tfrac{-1}{p_1}\mu_1= \tfrac{-1}{p_1} \tfrac{-1}{p_0}\mu_0\]
So it looks like a general form is going to be (as much as I can find without actually knowing \(p_n\):

\[\mu_n =\mu_0 \frac{(-1)^n}{\prod_{k<n} p_k}\]

And similarly to the arbitrariness of our choice of \(\mu\) in solving a differential equations, it seems we can define \(\mu_0=1\) unless there's some other choice that naturally seems to go well with the product of \(p_k\)s such as \(\mu_0=-1\) or something.

Answer 13

jenkins are whatever felma or velma or whatever her name says
that seems to work I tried it for p_n=e^n...
\[\mu_n=\mu_0 \cdot \frac{(-1)^n}{e^1 \cdot e^2 \cdot e^3 \cdots e^{n-1}}=\mu_0 \frac{(-1)^{n}}{e^{\frac{n(n-1)}{2}}}\]
and looky http://www.wolframalpha.com/input/?i=e%5En*f%28n%2B1%29%2Bf%28n%29%3D0
that is kind of awesome

Answer 14

you are brilliant

Answer 15

Also I should note, it looks like every recurrence relation of this form can be turned into a difference equation by a pretty straight forward substitution:

\[f(x+1)+p(x)f(x)=q(x)\]
substitute in:
\[p(x)=r(x)-1\]
\[f(x+1)-f(x)+r(x)f(x)=q(x)\]\[\Delta f(x) + r(x)f(x)=q(x)\]

Which is really how I thought of all this stuff to start with but it's exactly equivalent, the only difference is the shift by 1, not a big deal when talking about arbitrary functions I think but might be nice to see for fun.

Answer 16

HAhaha thanks xD also I like this I didn't even think about that that's a good idea to use that products turn expontents into addition thanks, I think I'll steal that and use that to pay around haha

Answer 17

lol

Answer 18

it would be nice if it paid too

Answer 19

hahaha right? I need a job actually xD I do too much math and not enough job searching lol

Answer 20

what about the nsa
i think they do really fun math there
not sure
never worked there

Answer 21

I just believe they do for some odd reason

Answer 22

Yeah I had heard that as well actually I don't know why but it's probably true haha

Answer 23

i think they have to kill you or employee you if they tell you

Answer 24

very top secret stuff

Answer 25

Yeah maybe I should apply there, although I don't have a phd or masters so I don't know if they'd hire me lol

Answer 26

what that's crazy
you know super fancy math
how are you not at least a master degree person

Answer 27

I have a bachelor of arts in chemistry and a minor in math, I guess not having a BS gave me more free time to do whatever I wanted haha.

Answer 28

i'm envious

Answer 29

Haha well hey at least we're doing math right now and working together, this is good!

Answer 30

well i'm pretty sure you just solved that whole thing and I just watched
I didn't do anything special

Answer 31

so you kinda worked alone

Answer 32

anyways i'm going to go hula hoop

Answer 33

cool problem

Answer 34

Well maybe to an extent but like I had already worked through most of this before I got here, I was more or less coming on here to see if other people were interested and now I basically got you up to the same level of understanding of this thing as me.

The only thing I was thinking of for that product was to use factorials which are kinda boring, throwing that exponential in like that has helped a lot, plus if you think of any ideas throw 'em at me and I'll try helping you out with some stuff!

Answer 35

Oh you know what that one thing sorta reminded me of a geometric sequence since it can be written as \[\frac{v_{n+1}}{v_n}=\frac{-1}{p_n} \\ \text{ this reminded me of separation by variables } \\ \text{ which is everyone favorite way \to solve that one part } \\ \text{ and deriving the formula for solving first order linear differential equations } \\ \text{ you know the } v'=pv \text{ thing } \\ \text{ anyways I realize that } \prod_{k=0}^{n-1} \frac{v_{n+1}}{v_n}=\frac{v_n}{v_0} \\ \text{ so we just have \to take the product of both sides } \\ \text{ once we separate } \\ \prod_{k=0}^{n-1} \frac{v_{k+1}}{v_k}=\prod_{k=0}^{n-1} \frac{-1}{p_k} \\ \frac{v_n}{v_0}= \frac{(-1)^{n-1}}{\prod_{k=0}^{n-1} p_k} \\ v_n= v_0 \frac{(-1)^{n-1}}{\prod_{k=0}^{n-1}p_k}\]

Answer 36

v was easier to write then mu
since mu requires two letters :p

Answer 37

you know instead of trying to inspect a pattern

Answer 38

Oh woah this is much cleaner I really like this a lot better than my sorta hand wavy guess the pattern method. Something I just realized is we have this really cool thing happening connecting sums and products that I think you already used earlier in the post to test out the product with that e^n thing.

\[\ln \left( \prod a_n \right) = \sum \ln(a_n)\]

Answer 39

yep. i think that is actually the way wolfram came up with that one answer in that link I posted above...
like they had for some reason put (-1)*constant instead of just constant
I was wondering why they would do that

Answer 40

and yes I totally see the law of logs in action there

Answer 41

That negative thing was bothering me so I just changed the p(x) part to be -p(x) so that we could completely remove it and it ends up being much cleaner.

\[a_{n+1}-p_n a_n = q_n\]

I sorta typed this up but it's not complete yet since I had some other idea to extend this to the more general form where instead of the left-most term being \(a_{n+1}\) I instead noticed it wouldn't be too much harder to deal with it being a variable step higher, \(a_{n+k}\) and then that would admit k different solutions from k different starting points.

https://www.overleaf.com/read/gkchtfggqqbn

Answer 42

Errr... That's actually not anything new I think it's pretty much just the same thing we already did here and nothing new I thought I had put some stuff in there but I haven't sorry

Answer 43

oh you are writing a paper ?

Answer 44

it looks pretty
did you type that using winedt?