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

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

1 Answer 1


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .