Discrete Math: Linear Inhomogeneous Recurrence

[stanyeo1984]

How do I solve this

1. (a) Solve the recurrence relation
a_n =6a_n−2 +8a_n−3 +3a_n−4 +64·3^{^n−4}, n􏰀>=4
where a₀ =0,a₁ =1,a₂ =4 and a₃ =33.
(b) Write down a closed form of the generating function of the sequence a_n.

 

[MarkFL]

Hello, stanyeo1984! :D

I have given your thread a title briefly describing the problem. A title like "Discrete Math" posts in the "Discrete Mathematics, Set Theory, and Logic" forum adds no further information. This was, our members can see the nature of the problem at a glance when viewing the thread listing.

What does the following mean:

n􏰀>=4 ?

For part a) can you identify:

i) The characteristic roots.

ii) The form of the particular solution?

 

[stanyeo1984]

Hello, stanyeo1984! :D

I have given your thread a title briefly describing the problem. A title like "Discrete Math" posts in the "Discrete Mathematics, Set Theory, and Logic" forum adds no further information. This was, our members can see the nature of the problem at a glance when viewing the thread listing.

What does the following mean:

n􏰀>=4 ?

For part a) can you identify:

i) The characteristic roots.

ii) The form of the particular solution?

hello, n>=4 just means greater than or equal to 4,

I think i got the characteristic roots as (x-3)(x+1)³

But I got stuck after that

 

[MarkFL]

hello, n>=4 just means greater than or equal to 4,

I think i got the characteristic roots as (x-3)(x+1)³

But I got stuck after that

Yes, I understand n >= 4, I just had trouble with n􏰀>=4.

Yes, the characteristic equation is:

\(\displaystyle r^3-6r^2 -8r-3=(r-3)(r+1)^3=0\)

So, you have the root $r=3$ and the root $r=-1$ of multiplicity 3...what's the general form of the homogeneous solution then?

 

[stanyeo1984]

Yes, I understand n >= 4, I just had trouble with n􏰀>=4.

Yes, the characteristic equation is:

\(\displaystyle r^3-6r^2 -8r-3=(r-3)(r+1)^3=0\)

So, you have the root $r=3$ and the root $r=-1$ of multiplicity 3...what's the general form of the homogeneous solution then?

Is the general form C₁3ⁿ+C₂(-1)ⁿ+C₂(-1)ⁿ+C₂(-1)ⁿ

Otherwise, I don't know how to deduce the general solution:/

 

[MarkFL]

Is the general form C₁3ⁿ+C₂(-1)ⁿ+C₂(-1)ⁿ+C₂(-1)ⁿ

Otherwise, I don't know how to deduce the general solution:/

No, we require each term to be linearly independent of one another, and so the homogeneous solution would be:

\(\displaystyle h_n=c_1(3)^n+c_2(-1)^n+c_3n(-1)^n+c_4n^2(-1)^n\)

Now, bearing in mind all of the terms of the homogeneous solution, what must the form for the particular solution $p_n$ be?

 

[stanyeo1984]

No, repeated roots require each term to be linearly independent of one another, and so the homogeneous solution would be:

\(\displaystyle h_n=c_1(3)^n+c_2(-1)^n+c_3n(-1)^n+c_4n^2(-1)^n\)

Now, bearing in mind all of the terms of the homogeneous solution, what must the form for the particular solution $p_n$ be?

I'm thinking that the particular solution p_n would be 64.C₅3^n-4

 

[MarkFL]

I'm thinking that the particular solution p_n would be 64.C₅3^n-4

No, that's a constant time $3^n$, which we already have as a term in the homogenous solution...so we need to add a factor as we did to two of the terms in the homogeneous solution because we had a repeated characteristic root. We don't need to use the constant $64\cdot3^{-4}$ in the particular solution...so I would state:

\(\displaystyle p_n=An3^n\)

Now, can you use the method of undetermined coefficients to find $A$?

 

[stanyeo1984]

No, that's a constant time $3^n$, which we already have as a term in the homogenous solution...so we need to add a factor as we did to two of the terms in the homogeneous solution because we had a repeated characteristic root. We don't need to use the constant $64\cdot3^{-4}$ in the particular solution...so I would state:

\(\displaystyle p_n=An3^n\)

Now, can you use the method of undetermined coefficients to find $A$?

I'm only familiar for the method of undetermined coefficients for DE not so much for this, is it possible for you to explain?

 

[MarkFL]

I'm only familiar for the method of undetermined coefficients for DE not so much for this, is it possible for you to explain?

It's very similar, except that there is no differentiation involved which actually makes it simpler. I would begin by arranging the difference equation as follows:

\(\displaystyle a_{n}-6a_{n−2}-8a_{n−3}-3a_{n−4}=64\cdot3^{n-4}\)

Now, it we assume that $a_n=An3^n$, then by substitution, we obtain:

\(\displaystyle An3^n-6A(n-2)3^{n-2}-8A(n-3)3^{n-3}-3A(n-4)3^{n-4}=64\cdot3^{n-4}\)

Next, let's multiply through by \(\displaystyle 3^{4-n}\ne0\) to get:

\(\displaystyle An3^4-6A(n-2)3^{2}-8A(n-3)3-3A(n-4)=64\)

Now, distribute, combine like terms and solve for $A$...what do you find?

 

[stanyeo1984]

It's very similar, except that there is no differentiation involved which actually makes it simpler. I would begin by arranging the difference equation as follows:

\(\displaystyle a_{n}-6a_{n−2}-8a_{n−3}-3a_{n−4}=64\cdot3^{n-4}\)

Now, it we assume that $a_n=An3^n$, then by substitution, we obtain:

\(\displaystyle An3^n-6A(n-2)3^{n-2}-8A(n-3)3^{n-3}-3A(n-4)3^{n-4}=64\cdot3^{n-4}\)

Next, let's multiply through by \(\displaystyle 3^{4-n}\ne0\) to get:

\(\displaystyle An3^4-6A(n-2)3^{2}-8A(n-3)3-3A(n-4)=64\)

Now, distribute, combine like terms and solve for $A$...what do you find?

I solve for A=1/3 and therefore, p_n= 1/3n3ⁿ

 

[MarkFL]

I solve for A=1/3 and therefore, p_n= 1/3n3ⁿ

Good! :D

So, using the principle of superposition, what is the general solution? And from here we can use the given initial values to determine the parameters $c_i$.

 

[stanyeo1984]

It's very similar, except that there is no differentiation involved which actually makes it simpler. I would begin by arranging the difference equation as follows:

\(\displaystyle a_{n}-6a_{n−2}-8a_{n−3}-3a_{n−4}=64\cdot3^{n-4}\)

Now, it we assume that $a_n=An3^n$, then by substitution, we obtain:

\(\displaystyle An3^n-6A(n-2)3^{n-2}-8A(n-3)3^{n-3}-3A(n-4)3^{n-4}=64\cdot3^{n-4}\)

Next, let's multiply through by \(\displaystyle 3^{4-n}\ne0\) to get:

\(\displaystyle An3^4-6A(n-2)3^{2}-8A(n-3)3-3A(n-4)=64\)

Now, distribute, combine like terms and solve for $A$...what do you find?

And now I add that to the end of the characteristic solution and solve for C₁ and the other constants?

 

[MarkFL]

And now I add that to the end of the characteristic solution and solve for C₁ and the other constants?

Yes, by the principle of superposition, we know:

\(\displaystyle a_n=h_n+p_n=c_13^n+c_2(-1)^n+c_3n(-1)^n+c_4n^2(-1)^n+\frac{1}{3}n3^n\)

We have 4 parameters to determine, and fortunately we were given the 4 initial values:

\(\displaystyle a_{0}=0,\,a_{1}=1,\,a_{2}=4,\,a_{3}=33\)

So, what we will get is a 4X4 system of linear equations we must solve. Can you set up the system?

 

[stanyeo1984]

Yes, by the principle of superposition, we know:

\(\displaystyle a_n=h_n+p_n=c_13^n+c_2(-1)^n+c_3n(-1)^n+c_4n^2(-1)^n+\frac{1}{3}n3^n\)

We have 4 parameters to determine, and fortunately we were given the 4 initial values:

\(\displaystyle a_{0}=0,\,a_{1}=1,\,a_{2}=4,\,a_{3}=33\)

So, what we will get is a 4X4 system of linear equations we must solve. Can you set up the system?

From here we get, C₁=0, C₂=0, C₃=1 and C₄=1

 

[MarkFL]

From here we get, C₁=0, C₂=0, C₃=1 and C₄=1

I get:

\(\displaystyle \left(c_1,c_2,c_3,c_4\right)=(0,0,1,-1)\)

 

[stanyeo1984]

I get:

\(\displaystyle \left(c_1,c_2,c_3,c_4\right)=(0,0,1,-1)\)

Sorry yes, missed the - sign, but if i place these in the place of the variable in the general solution, won't i get a closed formula?

And if that's correct, what do I do when the question asks me to solve?

 

[MarkFL]

This means the closed form satisfying all of the given conditions is:

\(\displaystyle a_n=n(-1)^n-n^2(-1)^n+\frac{1}{3}n3^n=n\left((-1)^n\left(1-n\right)+3^{n-1}\right)\)

 

[stanyeo1984]

This means the closed form satisfying all of the given conditions is:

\(\displaystyle a_n=n(-1)^n-n^2(-1)^n+\frac{1}{3}n3^n=n\left((-1)^n\left(1-n\right)+3^{n-1}\right)\)

Managed to work that one out:D, but what do they mean when they ask me to solve the recurrence relation?

 

[MarkFL]

Managed to work that one out:D, but what do they mean when they ask me to solve the recurrence relation?

Solving a recurrence relation (or difference equation) is what we just did. :D

 

[stanyeo1984]

Solving a recurrence relation (or difference equation) is what we just did. :D

Oh, so finding the constants and placing them back in the general equation constitutes as solving the equation?

- - - Updated - - -

Solving a recurrence relation (or difference equation) is what we just did. :D

Or does question b ask for something else?

 

[MarkFL]

Oh, so finding the constants and placing them back in the general equation constitutes as solving the equation?

It is the entire process:

• Find the characteristic roots, and from those determine $h_n$
• Determine the form of $p_n$ and use the method of undetermined coefficients to get $p_n$
• Use the principle of superposition to state the general solution $y_n=h_n+p_n$
• Use the initial values with the general solution $y_n$ to determine the parameters

Part b) asks for the generating function, which is related to the closed form, but I have to run now to work on a coding project. Post what progress you have made with the generating function, and perhaps someone else can help with that. :D

 

[scott1204]

hmm. So would you guys please give clear answer of the part a?
also is "an=n(−1)n−n2(−1)n+13n3n=n((−1)n(1−n)+3n−1)" the answer of the part b?

 

[MarkFL]

hmm. So would you guys please give clear answer of the part a?
also is "an=n(−1)n−n2(−1)n+13n3n=n((−1)n(1−n)+3n−1)" the answer of the part b?

For part a), I wrote:

\(\displaystyle a_n=n\left((-1)^n\left(1-n\right)+3^{n-1}\right)\)

As far as part b), I would invite anyone with a better understand of generating functions to provide help. It's been so long for me that I would have to do research as a refresher, and I simply don't have time. :D

 

[scott1204]

For part a), I wrote:

\(\displaystyle a_n=n\left((-1)^n\left(1-n\right)+3^{n-1}\right)\)

As far as part b), I would invite anyone with a better understand of generating functions to provide help. It's been so long for me that I would have to do research as a refresher, and I simply don't have time. :D

I really appreciate you for part a.
\(\displaystyle a_n=n(-1)^n-n^2(-1)^n+\frac{1}{3}n3^n=n\left((-1)^n\left(1-n\right)+3^{n-1}\right)\)[/QUOTE]
isn't it the answer of part b?

I really thankful with your prompt reply :)

 

[scott1204]

Discrete Math(recurrence relations)

1. (a) Solve the recurrence relation \(\displaystyle a_{n}=6a_{n−2}+8a_{n−3}+3a_{n−4}+64\cdot3^{n-4}\)
where a0 =0,a1 =1,a2 =4 and a3 =33.
(b) Write down a closed form of the generating function of the sequence an.

please some one note that the clear answers of (a) and (b)!
All arguments and working must be shown


it is pretty tough...!

 

[MarkFL]

This question has already been posted...and you have even posted in that thread so I know you are aware of its existence...why are you re-posting it? (Wondering)

edit: I went ahead and merged the newer duplicate with the older thread. Please note that part a) has already been answered, and be patient and wait for someone to post help with part b), OR post what progress you have made with it.

 

[scott1204]

closed form of generating function

any one can get a closed form of the generating function of the sequence \(\displaystyle a_n\)

\(\displaystyle a_n=n\left((-1)^n\left(1-n\right)+3^{n-1}\right)\)

you can refer websites Generating function - Wikipedia, the free encyclopedia
Generating Function -- from Wolfram MathWorld

it might be helpful.

 

[Evgeny.Makarov]

any one can get a closed form of the generating function of the sequence \(\displaystyle a_n\)

Is this a question/request or a statement? If the former, have you tried doing it yourself as per rule #11 http://mathhelpboards.com/rules/?

 

[scott1204]

Is this a question/request or a statement? If the former, have you tried doing it yourself as per rule #11 http://mathhelpboards.com/rules/?

I tried to solve over 4hrs but I couldn't get it...
I also tried to find how to make generating function through the online, it does not work...

 

[MarkFL]

I have again merged threads...please post questions pertaining to this problem in this thread. :D

 

[Evgeny.Makarov]

Unfortunately, I am also not very good with generating functions and have little time. I can only recommend the following formulas.
\begin{align}
(x^{n+1})'&=nx^n+x^n&&\text{to find }\sum(-1)^nnx^n\\
(x^{n+2})''&=n^2x^n+3nx^n+2x^n&&\text{to find }\sum(-1)^nn^2x^n\\
\sum n(3x)^n&=\sum n(3^nx^n)
\end{align}

 

[johng1]

The calculation of a closed form for the generating function G(z) is straight forward. This is a rational function in z. If you're really ambitious (I'm not), you can apply partial fraction decomposition to G(z), use the geometric series and it's derivatives and find the closed form solution for $a_n$.