Special Types Recurrence Equations

Special types of Recurrence Equations

Seems this is one of the most difficult topics in EJU math

If you want to know 3 basic recurrence equations,

please read above first

$$Type:\ \ a_{n+1}=p a_n + q $$

Method: Use characteristic equation to transform the original equation into a geometric progression


$$a_1=3,\ a_{n+1}=2a_n – 1$$

Use Charasteric Equation (put \(\alpha\) into \(a_n\) and \(a_{n+1}\))

$$\alpha=2 \alpha -1$$

$$\alpha = 1$$

Subtract the characteristic equation from the original one

& a_{n+1} &= & 2a_n – 1
\\ -)& \alpha &= &2\alpha – 1
\\\hline & a_{n+1} -\alpha &= & 2(a_n – \alpha)

Since \(\alpha = 1\)

$$a_{n+1}-1 = 2(a_n -1)$$

If you set \(b_{n+1} = a_{n+1}-1 \) and \(b_n= a_n-1\)

$$b_{n+1}=2 b_n$$

This is the recurrence equation of the geometric progression

Use the formula of geometric progression

$$a_n=a_1 r^{n-1}$$

$$b_n=b_1 2^{n-1}$$


Arrange it


$$Type:\ \ a_{n+1}=\frac{a_n}{p a_n +q} $$

When you see

$$a_{n+1}=\frac{a_n}{p a_n +q}$$

It’s called Fractional type

Method: We need to arrange and change it to \(a_{n+1}=p a_n + q \ Type\)


$$a_1=3,\ a_{n+1}=\frac{2 a_n}{3 a_{n+1}}$$

Get reciprocal fraction of it

Also make sure if \(a_n ≠0\)

$$(a_{n+1})^{-1}=\bigg(\frac{2 a_n}{3 a_{n+1}}\bigg)^{-1} $$

$$\frac{1}{a_{n+1} }=\frac{3a_{n+1}}{2a_n}$$

$$=\frac{3}{2}+\frac{1}{2} \frac{1}{a_n}$$

If you set \(b_{n+1}=\frac{1}{a_{n+1}},\ b_n=\frac{1}{a_n}\) as a new sequence


Remember it is

$$Type:\ \ a_{n+1}=p a_n + q$$

Solve the characteristic equation

$$\alpha = \frac{1}{2}\alpha + \frac{3}{2}$$


$$b_{n+1}- \alpha = p(b_n- \alpha)$$

$$\frac{1}{a_{n+1}}-3= \frac{1}{2}\bigg(\frac{1}{a_n}-3\bigg)$$

This is a geometric progression

If you set \(c_{n+1}=
\frac{1}{a_{n+1}}-3 \ c_n=
\frac{1}{a_n}-3 \)


Use the formula of a geometric progression, then



$$\frac{1}{a_n}-3=\bigg(\frac{1}{2}\bigg)^{n-1} \bigg(\frac{1}{a_1}-3\bigg)$$

Since \(a_1=3\) is given

$$\frac{1}{a_n}-3 =\bigg(\frac{1}{2}\bigg)^{n-1} \bigg(\frac{1}{3}-3\bigg) $$

If you solve for \(a_n\)


$$Type:\ \ (a_n)^m,\ \ (a_{n+1})^n$$

Let’s call this exponent type

Method: Use logarithm to transform it into \(a_{n+1}=pa_n+q\), then deal with a geometric progression


$$a_1=4,\ \ a_{n+1}=2a_{n}^2$$

We need to use logarithm

Our goal is to get the form \(a_{n+1}=pa_n+q\) by arranging the original equation

Let’s take log for both sides of \(a_{n+1}=2a_{n}^2 \)


$$=1+2\log_2 a_n$$

if we set \(b_n=\log_2 a_n\)

$$b_{n+1}=2b_n +1$$

Solve the characteristic equation

$$\alpha = 2\alpha +1$$

$$\alpha = -1$$

Set \(b_{n+1}+1=2(b_n+1)\)

If you consider that \(c_{n+1}=b_{n+1}+1,\ \ c_n=b_n+1\)

$$c_{n+1}=2 c_n$$

is a geometric progression

Use the formula for geometric progression

$$c_n=c_1 ・2^{n-1}$$



$$=\log_2 a_1+1$$

$$=\log_2 4 +1$$



$$c_n=c_1 ・2^{n-1}$$




$$\log_2 a_n =3・2^{n-1}-1 $$


$$Type:\ \ a_{n+1}=pa_n + r^n$$

Method: Divide by \(r^{n+1}\) for both sides, and convert it to \(Type:\ \ a_{n+1}=pa_n + q\)


$$a_1=3,\ \ a_{n+1}=2a_n -3^n$$

We do not want to have \(n\) on the shoulder of \(3\)

So, let’s divide by \(3^{n+1}\)



If you consider that \(\frac{a_{n+1}}{3^{n+1}}\) & \(\frac{a_n}{3^n}\) as a new sequence, then we can have a characteristic equation

$$\alpha = \frac{2}{3}\ \alpha \ – \frac{1}{3}$$

If we solve for \(\alpha\),

$$\alpha = -1$$

Use \(a_{n+1}-\alpha=p(a_n-\alpha) \)


If we set \(b_n = \frac{a_n}{3^n}+1\),


Since this is a geometric progression,

$$b_n=b_1 r^{n-1}$$

Since \(b_1=\frac{a_1}{3}+1=2\)




End of the day

$$a_n=2^n・3^{-n+2} – 3$$

$$Type: \ \ a_{n+2}=p a_{n+1}+ q a_n$$

If you see \(a_{n+2}\) in the relation, we need to use ANOTHER type pf characteristic equation.


$$a_1=2,\ \ a_2=3,\ \ a_{n+2}=2a_{n+1}+3a_n$$

First of all, we have to set the followings to make a characteristic equation with \(t\)

$$t^2=a_{n+2},\ \ t=a_{n+1}, \ \ 1= a_n$$

Now we have


This is new type of characteristic equation for 3 terms recurrence equation.

If we solve for \(t\),


$$t=-1,\ \ 3$$


$$\alpha=-1, \ \ \beta=3$$

*it does not matter which letter you use for \(-1\).

Transform the original equation to

$$a_{n+2}-\alpha a_{n+1}= \beta (a_{n+1}-\alpha a_n)$$

Then we get


If you set

$$b_{n+1}=a_{n+2}+a_{n+1},\ \ b_n=a_{n+1}+a_n $$

we can have

$$b_{n+1}=3 b_n$$

Since this is a geometric progression,

$$b_n=b_1 3^{n-1}$$


$$a_{n+1}+a_n=3^{n-1} ・5$$


Remember that it is Type \(a_{n+1}=pa_n + r^n\)

Therefore we should divide by \(r^{n+1}\) for both sides to transform it into Type\(a_{n+1}=p a_n + q\)

$$\frac{a_{n+1}}{3^{n+1}}= -\frac{a_n}{3^{n+1}}+\frac{5・3^{n-1}}{3^{n+1}}$$

$$\frac{a_{n+1}}{3^{n+1}}= -\frac{1}{3}・\frac{a_n}{3^{n}}+\frac{5}{9} $$

Solve the characteristic equation



Set \(a_{n+1}-\alpha=p(a_n-\alpha) \)


$$b_{n+1}=r b_n$$

$$b_{n+1}=-\frac{1}{3} b_n$$

$$b_n=b_1 r^{n-1}$$