MathGoldMedalist
Sign InRegister

Telescoping Approaches to Solving Recurrences

Lesson · Intermediate

Algebra: Sequences & Series

73.1

an=an−1+3n−4,n≥1 a_n=a_{n-1}+3n-4,\qquad n\ge1
a0=7 a_0=7

Write the consecutive equations:

an−an−1=3n−4an−1−an−2=3n−7an−2−an−3=3n−10⋮a2−a1=3(2)−4a1−a0=3(1)−4 \begin{aligned} a_n-a_{n-1}&=3n-4\\ a_{n-1}-a_{n-2}&=3n-7\\ a_{n-2}-a_{n-3}&=3n-10\\ &\vdots\\ a_2-a_1&=3(2)-4\\ a_1-a_0&=3(1)-4 \end{aligned}

Add these equations so that the intermediate terms telescope:

an−a0=((3(1)−4)+(3n−4))n2=(3n−5)n2 a_n-a_0 = \frac{((3(1)-4)+(3n-4))n}{2} = \frac{(3n-5)n}{2}

Therefore,

an=n(3n−5)2+a0=n(3n−5)2+7 a_n = \frac{n(3n-5)}{2}+a_0 = \boxed{\frac{n(3n-5)}{2}+7}

73.2

If the coefficient of an−1a_{n-1} is a constant different from 1:

an=2an−1+5,n≥1 a_n=2a_{n-1}+5,\qquad n\ge1
a0=9 a_0=9

Let

bn=an2n b_n=\frac{a_n}{2^n}

From

an=2an−1+5 a_n=2a_{n-1}+5

divide by 2n2^n:

an2n=an−12n−1+52n \frac{a_n}{2^n} = \frac{a_{n-1}}{2^{n-1}} + \frac{5}{2^n}

Therefore,

bn=bn−1+52n,n≥1 b_n=b_{n-1}+\frac{5}{2^n},\qquad n\ge1

and

b0=a020=9 b_0=\frac{a_0}{2^0}=9

Now write:

bn−bn−1=52nbn−1−bn−2=52n−1bn−2−bn−3=52n−2⋮b2−b1=522b1−b0=521 \begin{aligned} b_n-b_{n-1}&=\frac{5}{2^n}\\ b_{n-1}-b_{n-2}&=\frac{5}{2^{n-1}}\\ b_{n-2}-b_{n-3}&=\frac{5}{2^{n-2}}\\ &\vdots\\ b_2-b_1&=\frac{5}{2^2}\\ b_1-b_0&=\frac{5}{2^1} \end{aligned}

Adding gives

bn−b0=521+522+⋯+52n−1+52n b_n-b_0 = \frac{5}{2^1} + \frac{5}{2^2} +\cdots+ \frac{5}{2^{n-1}} + \frac{5}{2^n}

Then

bn−b0=52(1+12+⋯+12n−2+12n−1) b_n-b_0 = \frac52 \left( 1+\frac12+\cdots+\frac{1}{2^{n-2}}+\frac{1}{2^{n-1}} \right)

Using the geometric series,

bn−b0=52⋅1−12n1−12=5(1−12n) b_n-b_0 = \frac52\cdot \frac{1-\frac{1}{2^n}}{1-\frac12} = 5\left(1-\frac{1}{2^n}\right)

Thus,

bn=5(1−12n)+b0=14−52n b_n = 5\left(1-\frac{1}{2^n}\right)+b_0 = 14-\frac{5}{2^n}

Since

an=2nbn a_n=2^n b_n

we get

an=14⋅2n−5 \boxed{a_n=14\cdot2^n-5}

73.3

If the coefficient of an−1a_{n-1} is nn:

an=nan−1+(n−2)!,n≥2 a_n=na_{n-1}+(n-2)!,\qquad n\ge2
a1=5 a_1=5

Let

bn=ann! b_n=\frac{a_n}{n!}

From

an=nan−1+(n−2)! a_n=na_{n-1}+(n-2)!

divide by n!n!:

ann!=an−1(n−1)!+(n−2)!n! \frac{a_n}{n!} = \frac{a_{n-1}}{(n-1)!} + \frac{(n-2)!}{n!}

Therefore,

bn=bn−1+1n(n−1)=bn−1+1n−1−1n,n≥2 b_n = b_{n-1} + \frac{1}{n(n-1)} = b_{n-1} + \frac{1}{n-1} - \frac{1}{n}, \qquad n\ge2

Also,

b1=a11!=5 b_1=\frac{a_1}{1!}=5

Now write:

bn−bn−1=1n−1−1nbn−1−bn−2=1n−2−1n−1bn−2−bn−3=1n−3−1n−2⋮b3−b2=12−13b2−b1=1−12 \begin{aligned} b_n-b_{n-1} &= \frac{1}{n-1}-\frac{1}{n}\\ b_{n-1}-b_{n-2} &= \frac{1}{n-2}-\frac{1}{n-1}\\ b_{n-2}-b_{n-3} &= \frac{1}{n-3}-\frac{1}{n-2}\\ &\vdots\\ b_3-b_2 &= \frac12-\frac13\\ b_2-b_1 &= 1-\frac12 \end{aligned}

After telescoping,

bn−b1=1−1n b_n-b_1=1-\frac1n

Therefore,

bn=1−1n+b1=6−1n b_n = 1-\frac1n+b_1 = 6-\frac1n

Hence,

an=n!bn=6n!−(n−1)! a_n = n!b_n = 6n!-(n-1)!

So,

an=6n!−(n−1)! \boxed{a_n=6n!-(n-1)!}
Back to Toolkit