Kuzee
Sequences

The Type aₙ₊₁ = aₙ + f(n)

This type of recurrence relation is solved by the accumulation method (the summation method), making it a flexible type.

The Recurrence Relation

Accumulation-type recurrence relation
an+1=an+f(n)a_{n+1} = a_n + f(n)

Characteristic: each time a function f(n)f(n) of nn is added.

Solution Method: The Accumulation Method

Starting from the recurrence relation, write out several equations:

a2−a1=f(1)a3−a2=f(2)a4−a3=f(3)⋮an−an−1=f(n−1)\begin{aligned} a_2 - a_1 &= f(1) \\ a_3 - a_2 &= f(2) \\ a_4 - a_3 &= f(3) \\ &\vdots \\ a_n - a_{n-1} &= f(n-1) \end{aligned}

Add all the equations together (adding the left sides and the right sides):

(a2−a1)+(a3−a2)+⋯+(an−an−1)=f(1)+f(2)+⋯+f(n−1)(a_2 - a_1) + (a_3 - a_2) + \cdots + (a_n - a_{n-1}) = f(1) + f(2) + \cdots + f(n-1)

Most terms on the left side cancel out, leaving only:

an−a1=∑k=1n−1f(k)a_n - a_1 = \sum_{k=1}^{n-1} f(k)

The general term formula
an=a1+∑k=1n−1f(k)a_n = a_1 + \sum_{k=1}^{n-1} f(k)

Worked Examples

Example 1: f(n)=nf(n) = n

The sequence {an}\{a_n\} satisfies a1=1a_1 = 1 and an+1=an+na_{n+1} = a_n + n. Find the general term formula.

Solution:

an=a1+∑k=1n−1k=1+(n−1)n2=1+n2−n2=n2−n+22\begin{aligned} a_n &= a_1 + \sum_{k=1}^{n-1} k \\ &= 1 + \frac{(n-1)n}{2} \\ &= 1 + \frac{n^2 - n}{2} \\ &= \frac{n^2 - n + 2}{2} \end{aligned}

Example 2: f(n)=2nf(n) = 2^n

The sequence {an}\{a_n\} satisfies a1=1a_1 = 1 and an+1=an+2na_{n+1} = a_n + 2^n. Find the general term formula.

Solution:

an=a1+∑k=1n−12k=1+2(2n−1−1)2−1=1+2n−2=2n−1\begin{aligned} a_n &= a_1 + \sum_{k=1}^{n-1} 2^k \\ &= 1 + \frac{2(2^{n-1} - 1)}{2 - 1} \\ &= 1 + 2^n - 2 \\ &= 2^n - 1 \end{aligned}

Example 3: f(n)=1n(n+1)f(n) = \frac{1}{n(n+1)}

The sequence {an}\{a_n\} satisfies a1=0a_1 = 0 and an+1=an+1n(n+1)a_{n+1} = a_n + \frac{1}{n(n+1)}. Find the general term formula.

Solution:

Use partial fraction decomposition: 1n(n+1)=1n−1n+1\frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1}

an=0+∑k=1n−11k(k+1)=∑k=1n−1(1k−1k+1)=(11−12)+(12−13)+⋯+(1n−1−1n)=1−1n=n−1n\begin{aligned} a_n &= 0 + \sum_{k=1}^{n-1} \frac{1}{k(k+1)} \\ &= \sum_{k=1}^{n-1} \left(\frac{1}{k} - \frac{1}{k+1}\right) \\ &= \left(\frac{1}{1} - \frac{1}{2}\right) + \left(\frac{1}{2} - \frac{1}{3}\right) + \cdots + \left(\frac{1}{n-1} - \frac{1}{n}\right) \\ &= 1 - \frac{1}{n} \\ &= \frac{n-1}{n} \end{aligned}

Practice Problems

Exercise 1

The sequence {an}\{a_n\} satisfies a1=2a_1 = 2 and an+1=an+2na_{n+1} = a_n + 2n. Find the general term formula.

Reference Answer(2 个标签)
recurrence relationlinear recurrence

Solution:

an=a1+∑k=1n−12k=2+2∑k=1n−1k=2+2⋅(n−1)n2=2+n(n−1)=n2−n+2\begin{aligned} a_n &= a_1 + \sum_{k=1}^{n-1} 2k \\ &= 2 + 2\sum_{k=1}^{n-1} k \\ &= 2 + 2 \cdot \frac{(n-1)n}{2} \\ &= 2 + n(n-1) \\ &= n^2 - n + 2 \end{aligned}

Answer: an=n2−n+2a_n = n^2 - n + 2

Exercise 2

The sequence {an}\{a_n\} satisfies a1=1a_1 = 1 and an+1=an+3na_{n+1} = a_n + 3^n. Find a5a_5.

Reference Answer(2 个标签)
recurrence relationlinear recurrence

Solution:

a5=a1+∑k=143k=1+(3+9+27+81)=1+120=121\begin{aligned} a_5 &= a_1 + \sum_{k=1}^{4} 3^k \\ &= 1 + (3 + 9 + 27 + 81) \\ &= 1 + 120 \\ &= 121 \end{aligned}

Or use the geometric sequence summation formula: a5=1+3(34−1)3−1=1+3×802=121a_5 = 1 + \frac{3(3^4 - 1)}{3 - 1} = 1 + \frac{3 \times 80}{2} = 121

Answer: a5=121a_5 = 121

Exercise 3

The sequence {an}\{a_n\} satisfies a1=1a_1 = 1 and an+1=an+1(n+1)na_{n+1} = a_n + \frac{1}{(n+1)n}. Find the general term formula.

Reference Answer(2 个标签)
recurrence relationlinear recurrence

Solution:

Note that 1(n+1)n=1n−1n+1\frac{1}{(n+1)n} = \frac{1}{n} - \frac{1}{n+1}

an=1+∑k=1n−11(k+1)k=1+∑k=1n−1(1k−1k+1)=1+(1−1n)=2−1n=2n−1n\begin{aligned} a_n &= 1 + \sum_{k=1}^{n-1} \frac{1}{(k+1)k} \\ &= 1 + \sum_{k=1}^{n-1} \left(\frac{1}{k} - \frac{1}{k+1}\right) \\ &= 1 + \left(1 - \frac{1}{n}\right) \\ &= 2 - \frac{1}{n} \\ &= \frac{2n - 1}{n} \end{aligned}

Answer: an=2n−1na_n = \frac{2n - 1}{n}

Summary

Symbols Used in This Article

符号类型读音/说明在本文中的含义
an,an+1a_n, a_{n+1}数学符号a-sub-n / a-sub-n-plus-oneThe nnth and (n+1)(n+1)th terms of the sequence
a1a_1数学符号a-sub-oneThe first term of the sequence
f(n)f(n)数学符号f of nA function varying with nn
kk数学符号kThe summation variable
∑k=1n−1f(k)\sum_{k=1}^{n-1} f(k)数学符号sum of f of kThe sum from 11 to n−1n-1
⋮\vdots数学符号vertical ellipsisVertical ellipsis

中英对照

中文术语英文术语音标说明
累加法telescoping sum/ˈtelɪskəʊpɪŋ sʌm/The method of solving recurrence relations by accumulation
叠加法summation method/sʌˈmeɪʃən ˈmeθəd/Another name for the accumulation method
裂项partial fraction decomposition/ˈpɑːʃəl ˈfrækʃən ˌdiːkɒmpəˈzɪʃən/Splitting a fraction into the difference of two terms
通项公式general term formula/ˈdʒenərəl tɜːm ˈfɔːmjələ/A formula expressing the nnth term directly in terms of nn
Previous
The Type aₙ₊₁ = qaₙ + d
Next
Limits of Sequences