Welcome to our community

Be a part of something great, join today!

Find a_n

  • Thread starter
  • Admin
  • #1

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,685
Let $a_0=2$, $a_1=3$, $a_2=6$, and for $n \ge 3$, $a_n=(n+4)a_{n-1}-4na_{n-2}+(4n-8)a_{n-3}$.

The first few terms are $2,\;\;3,\;\;6,\;\;14, \;\;40, \;\;152, \;\;784, \;\;5168,\;\; 40576, \;\;363392$.

Find with proof a formula for $a_n$ of the form $a_n=c_n+d_n$, where $c_n$ and $d_n$ are well-known sequences.
 
Last edited:

mente oscura

Well-known member
Nov 29, 2013
172
Let $a_0=2$, $a_1=3$, $a_2=6$, and for $n \ge 3$, $a_n=(n+4)a_{n-1}-4na_{n-2}+(4n-8)a_{n-3}$.

The first few terms are $2,\;\;3,\;\;6,\;\;14, \;\;40, \;\;152, \;\;784, \;\;5168,\;\; 40576, \;\;363392$.

Find with proof a formula for $a_n$ of the form $a_n=c_n+d_n$, where $c_n$ and $d_n$ are well-known sequences.
Hello.

I guessed the sequences, because I have not been able to prove it.I thought that it could be a factor involved, and, then, by differences I found with another string.:eek:

[tex]a_n=2^n+n![/tex]


Regards.
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Here is my solution:

Let's rewrite the recurrence as:

\(\displaystyle a_{n}-na_{n-1}=4\left(a_{n-1}-(n-1)a_{n-2} \right)-4\left(a_{n-2}-(n-2)a_{n-3} \right)\)

Now, if we define:

\(\displaystyle b_{n}=a_{n}-na_{n-1}\)

We may write the original recursion as:

\(\displaystyle b_{n}=4b_{n-1}-4b_{n-2}\)

This is a linear homogenous recursion with the repeated characteristic root $r=2$. Hence the closed form for $b_n$ is:

\(\displaystyle b_{n}=(A+Bn)2^n\)

Using the given initial values, we find:

\(\displaystyle b_1=a_1-a_0=3-2=1=(A+B)2\)

\(\displaystyle b_2=a_2-2a_1=6-6=0=(A+2B)4\)

From this 2X2 linear system, we find:

\(\displaystyle A=1,\,B=-\frac{1}{2}\)

Hence:

\(\displaystyle b_{n}=2^n-n2^{n-1}=a_{n}-na_{n-1}\)

Now, we may arrange this as:

\(\displaystyle a_{n}-2^{n}=n\left(a_{n-1}-2^{n-1} \right)\)

This implies one solution is \(\displaystyle c_n=2^n\)

If we define:

\(\displaystyle d_n=a_{n}-2^{n}\)

we then have:

\(\displaystyle d_{n}=nd_{n-1}\implies d_n=Cn!\)

And so by superposition we have the general form:

\(\displaystyle a_n=2^n+Cn!\)

Using the initial value we obtain:

\(\displaystyle a_0=2=2^0+C0!=1+C\implies C=1\)

Hence:

\(\displaystyle a_n=2^n+n!\)
 
  • Thread starter
  • Admin
  • #4

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,685
Hello.

I guessed the sequences, because I have not been able to prove it.I thought that it could be a factor involved, and, then, by differences I found with another string.:eek:

[tex]a_n=2^n+n![/tex]


Regards.
Well, even though you didn't provide any proof, your answer is correct and since you've been actively engaged with our site for quite some time and solving many challenge problems in the Challenge Questions and Puzzles sub-forum, I would give allowance to you and hence I would declare it here that you got full mark for that!:eek:

Thanks for participating, mente!

Here is my solution:

Let's rewrite the recurrence as:

\(\displaystyle a_{n}-na_{n-1}=4\left(a_{n-1}-(n-1)a_{n-2} \right)-4\left(a_{n-2}-(n-2)a_{n-3} \right)\)

Now, if we define:

\(\displaystyle b_{n}=a_{n}-na_{n-1}\)

We may write the original recursion as:

\(\displaystyle b_{n}=4b_{n-1}-4b_{n-2}\)

This is a linear homogenous recursion with the repeated characteristic root $r=2$. Hence the closed form for $b_n$ is:

\(\displaystyle b_{n}=(A+Bn)2^n\)

Using the given initial values, we find:

\(\displaystyle b_1=a_1-a_0=3-2=1=(A+B)2\)

\(\displaystyle b_2=a_2-2a_1=6-6=0=(A+2B)4\)

From this 2X2 linear system, we find:

\(\displaystyle A=1,\,B=-\frac{1}{2}\)

Hence:

\(\displaystyle b_{n}=2^n-n2^{n-1}=a_{n}-na_{n-1}\)

Now, we may arrange this as:

\(\displaystyle a_{n}-2^{n}=n\left(a_{n-1}-2^{n-1} \right)\)

This implies one solution is \(\displaystyle c_n=2^n\)

If we define:

\(\displaystyle d_n=a_{n}-2^{n}\)

we then have:

\(\displaystyle d_{n}=nd_{n-1}\implies d_n=Cn!\)

And so by superposition we have the general form:

\(\displaystyle a_n=2^n+Cn!\)

Using the initial value we obtain:

\(\displaystyle a_0=2=2^0+C0!=1+C\implies C=1\)

Hence:

\(\displaystyle a_n=2^n+n!\)
Well done, MarkFL! I just love to read your solution posts because they are always so nicely written and well explained! Bravo, my sweetest global moderator!(Sun)