1

I have the two following exercises that I have a very hard time solving.

(1) $a_n=3a_{n−1}+ 3^n,a_0= 1$

(2) $a_n= 2a_{n−1}+ 4a_{n−2}−8a_{n−3}+ 1,a_0=a_1=a_2=0$

Both are non-homogeneous with constant coefficients and the general solution should then be the homogeneous solution and a particular solution.

(1) The solution should be $a_n=a^{part}_n+a^{hom}_n$

It is easy to find $a^{hom}_n$. The homogeneous solution should be of the form $a_n=A*3^n$, solving for $a_0=1$ we get $a_n=3^n$.

Then for $a^{part}_n$ I am not sure. The litterature I'm reading says we should guess the form and then put that into the recurrance. I guess it is of the form $a^{part}_n=A*3^n$. Plugging this into the recurrance we get:

$A*3^n=3*A*3^{n-1}+3^n$

I divide all of it by $3^{n-1}$ which then cancels out all the A's. So now I don't know how to proceed. In the text it says that "However, if such expressions are already solutions to the homogeneous recursion, one must multiply the expression by a polynomial in $n$." How do I do this? Should then the particular solution be of the form $a^{part}_n=An3^n$? As you notice I am confused, this part of math has always bothered me but I really want to understand how to solve simple recurrance relations!

(2) This one is very similar in how I approach it. I figure out the homogeneous solution, which doesn't work because all the constants become zero.

$t^3-2t-4t+8=0$

$(t-2)^2(t+2)=0$

Then $a^{hom}_n=(An+B)2^n+C(-2)^n$

But using the starting values they all go to zero. There is some crucial important thing about recurrance relations (when $f(n)$ is not zero) that I do not understand... Help would be much appreciated!

The solutions are:

(1) $a_n= (n+ 1)3^n$

(2) $a_n= (\frac{n}{8}−\frac{5}{16})2^n−\frac{1}{48}(−2)^n+\frac{1}{3}$

Don_twice
  • 91
  • It suffices to check. If $a_n=n3^n$, then $a_n-3a_{n-1}=3^n$. –  Oct 18 '21 at 12:12
  • It ends up being $An^k \lambda^n$ where $k$ is the multiplicity of the zero of $\lambda$ in the characteristic polynomial. So indeed $An3^n$ works out. Of course you don't need to know this general thing to do a particular case. – Ian Oct 18 '21 at 12:18
  • As for the second one, you don't apply the initial conditions to the homogeneous solution directly, you adjoin the particular solution first. Here to get the particular solution you view $1$ as $1^n$, so you apply the same procedure: the particular solution is $A n^k 1^n$ where $k$ is the multiplicity of $1$ as a root of the characteristic polynomial (which is $0$ since it isn't one). – Ian Oct 18 '21 at 12:19
  • Ok so I first find the form of the homogeneous solution and then adjoin it with the particular? After that I use the starting values to find the values of the constants? – Don_twice Oct 18 '21 at 13:27
  • The order of steps isn't quite as rigid as all that but yes that's right. – Ian Oct 18 '21 at 14:00
  • Sadly I do not follow the reasoning. I do not understand how to combine the particular and homogeneous to one solution. What dictates the form of them. I'll try to read the litterature further. – Don_twice Oct 18 '21 at 15:36
  • I solved both of them, I'll put up my solutions and answer my own question in a moment. Feedback on them would be appreciated! – Don_twice Oct 18 '21 at 16:34
  • Recurrence has no a – J. W. Tanner Oct 18 '21 at 20:34
  • Don't understand what you mean. – Don_twice Oct 18 '21 at 20:49
  • @Don_twice: I mean that you spelled the word recurrence incorrectly – J. W. Tanner Oct 19 '21 at 16:51

1 Answers1

1

The order of computation is as follows for linear non-homogeneous recurrance relations.

  1. Given $a_n=a^{part}_n+a^{hom}_n$, determine both the forms of the particular and homogeneous solutions.

(1) $a^{hom}_n=B*3^n$

$a^{part}_n$ we guess of the same form as the homogeneous, but because it already exists we multiply the guess by n. Guessing $a^{part}_n=An3^n$. Putting this into the original recurrance we get that $A=1$. As such the general solution to the recurrance becomes $a_n=a^{part}_n+a^{hom}_n=B3^n+n3^n$, solving for the initial value we get $a_n=3^n+n3^n=(n+1)3^n$.

  1. We do the same order of computation here. $a^{hom}_n=(An+B)2^n+C(-2)^n$. We guess that the particular solution should be of the form $c1^n$ (why? I'm not sure please if someone could answer this!). Substituting this into the original recurrance and solving for c we get that $c=\frac{1}{3}$. Now we have the whole form for the general solution, using our initial values we get the desiered result!
Don_twice
  • 91