# Solve the following recurrances. (Linear with constant coefficients)

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}$$

• It suffices to check. If $a_n=n3^n$, then $a_n-3a_{n-1}=3^n$.
– user974557
Commented Oct 18, 2021 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
Commented Oct 18, 2021 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
Commented Oct 18, 2021 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? Commented Oct 18, 2021 at 13:27
• The order of steps isn't quite as rigid as all that but yes that's right.
– Ian
Commented Oct 18, 2021 at 14:00

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!