# Recurrence relation next step after finding root

I have the recurrence relation:

$$a_n = 4 a_{n-1} - 4 a_{n-2} + 2n$$. With the initial conditions $$a_0 = 9$$ and $$a_1 = 10$$

I have found the characteristic polynomium:

$$r^2 - 4r + 4$$ which is also $$(r-2)^2$$, which have root 2.

Now is my solution to the recurrence relation is $$\alpha_1 2^n + \alpha_2 2^n$$?

My question simply is, am I on the right track in the first place? And what to do with the $$2^n$$?

• Typically, if the characteristic polynomial has a double root, then solutions are of the form $\alpha_12^n + \alpha_2n2^n$. Mar 23, 2021 at 23:03

## 1 Answer

Your approach goes in the right general direction though, as @octave points out, the general solution looks different in the case of repeated roots. (You can't simply repeat $$2^n$$.)

The $$2n$$ term makes the recurrence non-homogeneous and here a good strategy is to find a particular solution first, ignoring the initial condition for the time being. Since $$2n$$ is a linear function of $$n$$, try $$a_n = cn + d$$: substituting in the recurrence shows that it works for $$c = 2$$ and $$d=8$$. Then the general solution to the non-homogeneous recurrence is $$a_n = 2n + 8 + b_n$$, where $$b_n$$ is the general solution to the associated homogeneous recurrence $$b_n = 4b_{n-1} - 4b_{n-2}$$. For double root 2, we have $$b_n = \alpha_1 2^n + \alpha_2 n \cdot 2^n$$, and the initial conditions $$b_0 = a_0 - 2\cdot0 - 8 = 1$$ and $$b_1 = 0$$ give $$\alpha_1 = 1$$ and $$\alpha_2 = -1$$, so $$a_n = 2n+8+2^n-n \cdot2^n$$.