I'm solving non-homogeneous linear recurrences for my combinatorics class and my teacher skipped a bunch of steps in his notes, so I am trying to make sense of a particular "step" he took.

We were given based operations on sequences where $a_n$ is a sequence $a_0,a_1,a_2,\cdots $ and $E$ is the operator that shifts a sequence, e.g. $E(a_n)=a_{n+1}$:$$c(a_n)=(c\cdot a_n)$$$$(A+B)(a_n)=A(a_n)+B(a_n)$$$$(AB)(a_n)=A(B(A-n))$$So, for example:$$(E+2)(a_n)=(a_{n+1})+(2a_n)$$$$E^3(a_n)=E^2(a_{n+1})=E(a_{n+2})=a_{n+3}$$So I am given the non-homogeneous recurrence relation that I need to solve:$$F_n=2a_{n-1}+1$$The first step is to express the recurrence of the homogeneous part of the recurrence using sequence operators, but immediately there is where he loses me. In my notes it says $(E-2)(a_n)$, but I do not understand where he gets this from, because according to the sequence operations, he is claiming:$$2a_{n-1}\rightarrow (E-2)(a_n)=E(a_n)-2(a_n)=a_{n+1}-2a_n$$And unless I am doing my math incorrectly,$$2a_{n-1}\neq a_{n+1}-2a_n$$So where exactly does he get $(E-2)(a_n)$ from?

  • $\begingroup$ what ? this is exactly your recurrence relation (your hypothesis) $\endgroup$ – reuns Apr 18 '16 at 2:50
  • 1
    $\begingroup$ I imagine you are trying to solve $a_n=2a_{n-1}+1$, that is, $a_n-2a_{n-1}=1$. This can almost be written as $(E-2)(a_n)=1$, except that yields $a_{n+1}-2a_n=1$. Same recurrence, different name for the index. $\endgroup$ – André Nicolas Apr 18 '16 at 2:51
  • $\begingroup$ and someone on the forum adviced for solving finite difference equations to search for solutions of the form "for every $n$ : $a_n = x^n$" for some $x$. which is equivalent to factorizing the characteristic polynomial $\endgroup$ – reuns Apr 18 '16 at 2:53
  • $\begingroup$ Fixed it up a little bit so that "homogeneous part of the recurrence" is less ambiguous $\endgroup$ – Jodo1992 Apr 18 '16 at 2:56
  • $\begingroup$ you fixed nothing since we don't understand what equation you want to solve... and go read another course , or search on the forum, if you don't understand yours. $\endgroup$ – reuns Apr 18 '16 at 2:58

My mistake was in not understanding that he switched the inital relation from $$a_n=2a_{n-1}+1$$To:$$a_n-2a_{n-1}=1$$So he is not claiming that $2a_{n-1}=(E-2)(a_n)$ but instead claiming that$$a_n-2a_{n-1}\rightarrow (E-2)(a_n)=E(a_n)-2(a_n)=a_{n+1}-2a_n$$Which is true.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.