# 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,

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

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

#### Example

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

$$\begin{array}{rcccccc} & a_{n+1} &= & 2a_n – 1 \\ -)& \alpha &= &2\alpha – 1 \\\hline & a_{n+1} -\alpha &= & 2(a_n – \alpha) \end{array}$$

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

$$a_n-1=2^{n-1}(a_1-1)$$

Arrange it

$$a_n=2^n+1$$

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

#### Example

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

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

Remember it is

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

Solve the characteristic equation

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

$$\alpha=3$$

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

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

Use the formula of a geometric progression, then

$$c_n=c_1\bigg(\frac{1}{2}\bigg)^{n-1}$$

So

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

$$a_n=\frac{3・2^{n-4}}{-1+9・2^{n-4}}$$

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

#### Example

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

$$\log_{2}a_{n+1}=\log_{2}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}$$

Since

$$c_{1}=b_1+1$$

$$=\log_2 a_1+1$$

$$=\log_2 4 +1$$

$$=3$$

Hence

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

$$b_n+1=3・2^{n-1}$$

$$b_n=3・2^{n-1}-1$$

Therefore

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

$$a_n=2^{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$$

#### Example

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

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

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

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

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

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

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

Since this is a geometric progression,

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

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

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

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

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

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.

#### Example

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

$$t^2=2t+3$$

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

If we solve for $$t$$,

$$t^2-2t-3=0$$

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

Set

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

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

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}(a_{1+1}+a_1)$$

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

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

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

$$\alpha=-\frac{1}{3}\alpha+\frac{5}{9}$$

$$\alpha=\frac{5}{12}$$

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

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

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

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

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

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

Eventually

$$a_n=\frac{3}{4}・(-1)^{n-1}+\frac{5}{4}・3^{n-1}$$

スポンサーリンク
シェアする
workazeをフォローする KAZELAB
タイトルとURLをコピーしました