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

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

コメント

タイトルとURLをコピーしました