Solution to Solve the recurrence relation a_n-4a_n-1+5a_n-2-2a_n-3=1+2^n - Sikademy
Author Image

Archangel Macsika

Solve the recurrence relation a_n-4a_n-1+5a_n-2-2a_n-3=1+2^n

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

a_n-4a_{n-1}+5a_{n-2}-2a_{n-3}=1+2^n

a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}+(1+2^n)


Characteristic equation: r^3-4r^2+5r-2=(r-1)^2(r-2)=0, \ \ r_1=1, r_2=2

Then a^{(0)}_n=(c_1+c_2n)r_1^n+c_3r_2^n=c_1+c_2n+c_32^n is a solution of a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}


We need do find particular solution of a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}+F(n), \ \ F(n)=(1+2^n)

1 and 2 are characteristic roots of multiplicity 2 and 1 respectively.

Then particular solution has form of a^{(p)}_n=n^2(b_tn^t+b_{t-1}n_{t-1}+...+b_1n+b_0)1^n+ n(d_kn^k+d_{k-1}n_{k-1}+...+d_1n+d_0)2^n

Suppose that a^{(p)}_n=n^2 b_0\times 1^n+nd_02^n=b_0n^2+d_0n2^n and substitute it:

b_0n^2+d_0n2^n=4(b_0(n-1)^2+d_0(n-1)2^{n-1})-5(b_0(n-2)^2+d_0(n-2)2^{n-2})+2(b_0(n-3)^2+d_0(n-3)2^{n-3})+1+2^n=b_0(n^2+2)+d_0n2^n-d_02^{n-2}+1+2^n


b_0n^2+d_0n2^n=b_0(n^2+2)+d_0n2^n-d_02^{n-2}+1+2^n

(2b_0+1)+(2^n-d_02^{n-2})=0, \ \ \forall n\in\mathbb{N}

b_0=-1/2, \ \ d_0=4

Solution of the recurrence relation is sum of a^{(0)}_n and a^{(p)}_n .

We have the following solution of the recurrence relation:

a_n=c_1+c_2n+c_32^n-1/2n^2+n2^{n+2} .



Answer: a_n=c_1+c_2n+c_32^n-1/2n^2+n2^{n+2}.


The following source is used:

https://courses.ics.hawaii.edu/ReviewICS241/morea/counting/RecurrenceRelations2-QA.pdf

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3924-qpid-2623