Ten recurrence patterns and how their solutions connect

A recurrence relates the terms of a sequence

A recurrence such as $a_{n+1}=a_n$ specifies a relationship between terms. Together with suitable initial values and domain conditions, it may define a sequence uniquely. Finding a general term means expressing $a_n$ directly in terms of $n$.

The following ten patterns are a useful study map, not a classification of every possible recurrence. Many transformations aim at the same destination: a geometric sequence. Before applying one, check that reciprocals, logarithms, divisions, and implicit root choices are justified.

| Pattern | Useful transformation | | --- | --- | | Affine first order | Subtract a fixed point | | Reciprocal | Replace $a_n$ by $1/a_n$ | | Powers or roots | Take logarithms of positive terms | | Exponential forcing | Divide by the forcing exponential | | Constant-coefficient second order | Factor with characteristic roots | | Polynomial forcing | Subtract a polynomial particular solution | | Variable coefficients | Normalize by a suitable sequence | | Coupled recurrences | Find geometric linear combinations | | Partial sums | Subtract consecutive sum equations | | An unfamiliar implicit recurrence | Calculate, conjecture, then prove |

This table replaces the Japanese flowchart in the source article. The first few patterns connect through affine recurrences; coupled and second-order systems connect through geometric combinations; partial sums often reduce to one of these after subtraction.

1. Affine first-order recurrences

For

$$a_{n+1}=pa_n+q,$$

if $p\ne1$, solve $L=pL+q$, giving $L=q/(1-p)$. Subtract this identity:

$$a_{n+1}-L=p(a_n-L),$$

so

$$\boxed{a_n=L+p^{n-1}(a_1-L).}$$

If $p=1$, use the arithmetic-sequence formula $a_n=a_1+(n-1)q$ instead. If $p=0$, the recurrence simply sets every term after the first equal to $q$; interpret that case directly without relying on an ambiguous $0^0$ notation.

Example

Let $a_1=3$ and $a_{n+1}=2a_n-1$. The fixed point is one, so $a_{n+1}-1=2(a_n-1)$ and

$$\boxed{a_n=2^n+1.}$$

For the separate arithmetic example $a_1=3$, $a_{n+1}=a_n+2$, the answer is $a_n=2n+1$.

2. A reciprocal transformation

Let

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

First show the recurrence is defined and nonzero. The initial term is positive; whenever $a_n>0$, the denominator is positive and $a_{n+1}>0$. Induction proves positivity at every step.

Set $b_n=1/a_n$. Then

$$b_{n+1}=\frac12b_n+\frac32, \qquad b_1=\frac13.$$

Its fixed point is three. Hence

$$b_n=3+\left(\frac12\right)^{n-1}\left(\frac13-3\right) =3-\frac8{3\cdot2^{n-1}}.$$

Taking the reciprocal,

$$\boxed{a_n=\frac{3\cdot2^{n-1}}{9\cdot2^{n-1}-8}.}$$

For $n\ge1$ its denominator is positive, agreeing with the domain check. A nonzero numerator alone would not justify ignoring a potentially zero recurrence denominator.

3. Powers and logarithms

Let $a_1=2$ and $a_{n+1}=3a_n^2$. Induction gives $a_n>0$, so set $b_n=\log_3a_n$. The logarithm has a valid positive base different from one, and positive arguments. Then

$$b_{n+1}=1+2b_n, \qquad b_{n+1}+1=2(b_n+1).$$

Thus

$$b_n=2^{n-1}(\log_32+1)-1,$$

and

$$\boxed{a_n=\frac{6^{\,2^{n-1}}}{3}.}$$

Logarithms turn a power relationship into a linear one. They are unavailable for a zero or negative real term unless the problem is reformulated appropriately.

4. Exponential forcing

For $a_{n+1}=pa_n+cr^n$ with $r\ne0$, divide by $r^{n+1}$ and set $b_n=a_n/r^n$:

$$b_{n+1}=\frac prb_n+\frac cr.$$

This is affine. When $p=r$, it is arithmetic instead of requiring a fixed-point subtraction.

Example

If $a_1=3$ and $a_{n+1}=2a_n-3^n$, then

$$b_{n+1}=\frac23b_n-\frac13, \qquad b_1=1.$$

Subtracting the fixed point $-1$ gives $b_n+1=2(2/3)^{n-1}$. Therefore

$$\boxed{a_n=3\cdot2^n-3^n.}$$

For the resonant variation $a_{n+1}=3a_n-3^n$ with the same initial value, $b_{n+1}=b_n-1/3$. Hence

$$\boxed{a_n=(4-n)3^{n-1}.}$$

The term $cr^n$ need not have coefficient one: its constant multiplier remains in the normalized recurrence.

5. Second-order constant-coefficient recurrences

For

$$a_{n+2}=pa_{n+1}+qa_n,$$

solve the characteristic equation $t^2-pt-q=0$. If its roots are $\alpha,\beta$, then $\alpha+\beta=p$ and $\alpha\beta=-q$, giving

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

Thus $a_{n+1}-\alpha a_n$ is geometric. Solve that recurrence first, then solve the resulting first-order equation for $a_n$. This approach also adapts to a repeated characteristic root.

Example

Let $a_1=2$, $a_2=3$, and $a_{n+2}=2a_{n+1}+3a_n$. The characteristic roots are $3$ and $-1$. We obtain

$$a_{n+1}+a_n=5\cdot3^{n-1}, \qquad a_{n+1}-3a_n=-3(-1)^{n-1}.$$

Subtracting the equations eliminates $a_{n+1}$:

$$\boxed{a_n=\frac54\,3^{n-1}+\frac34(-1)^{n-1}.}$$

The second geometric relation comes from $a_{n+2}-3a_{n+1}=-(a_{n+1}-3a_n)$; keeping the coefficient three is essential.

For distinct roots, using both relations can be faster. With a repeated nonzero root $r$, the usual form is $(A+B(n-1))r^{n-1}$, with $A,B$ determined by the two initial values. A repeated zero root means $p=q=0$, so $a_{n+2}=0$ and is best handled directly. Do not divide by a characteristic root before checking it is nonzero.

6. Polynomial forcing

Consider $a_{n+1}=pa_n+P(n)$, where $P$ is a polynomial. Look for a polynomial $g$ satisfying

$$g(n+1)-pg(n)=P(n).$$

Then $a_{n+1}-g(n+1)=p(a_n-g(n))$. For $p\ne1$, a polynomial of the same degree as $P$ provides a systematic coefficient-comparison approach.

Example

Take

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

The source's initial-value line is incomplete, but its calculation uses $a_1=1$, which is specified here. Set $g(n)=An^2+Bn+C$. Comparing coefficients in $g(n+1)-2g(n)=3n^2+2n+1$ gives

$$-A=3,\qquad2A-B=2,\qquad A+B-C=1.$$

Hence $g(n)=-3n^2-8n-12$. Therefore

$$a_n+3n^2+8n+12=24\cdot2^{n-1},$$

and

$$\boxed{a_n=3\cdot2^{n+2}-3n^2-8n-12.}$$

If the initial value were an unspecified $a_1=A_0$, replace the geometric coefficient $24$ by $A_0+23$.

When the coefficient is one

For $a_{n+1}=a_n+P(n)$, sum the differences:

$$a_n=a_1+\sum_{k=1}^{n-1}P(k).$$

With the empty-sum convention this is also valid at $n=1$. Otherwise derive it for $n\ge2$ and verify the first term separately. The usual power-sum formulas and telescoping often evaluate the sum.

A polynomial particular solution still exists here, generally of one higher degree; it is the same discrete-antiderivative idea, rather than a fundamental failure of polynomial methods.

7. Variable coefficients

A normalization can remove coefficients depending on $n$. For

$$a_1=1,\qquad na_{n+1}=(n+1)a_n+n^3+3n^2+2n,$$

divide by $n(n+1)>0$:

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

Set $b_n=a_n/n$. Then

$$b_n=1+\sum_{k=1}^{n-1}(k+2) =1+\frac{(n-1)(n+4)}2.$$

Thus

$$\boxed{a_n=\frac{n(n^2+3n-2)}2.}$$

For the homogeneous variation $na_{n+1}=(n+1)a_n$, $a_1=1$, repeated multiplication gives

$$a_n=\prod_{k=1}^{n-1}\frac{k+1}{k}=n.$$

This product argument is fully rigorous, and can be justified by induction. More generally, dividing by a nonzero solution of the homogeneous recurrence often gives a useful normalization. An inhomogeneous recurrence may then be solved by summing its normalized increments.

8. Coupled recurrences

Consider

$$a_{n+1}=a_n+2b_n,\qquad b_{n+1}=4a_n+3b_n,\qquad a_1=b_1=1.$$

Look for a combination $a_n+\lambda b_n$ that is geometric:

$$a_{n+1}+\lambda b_{n+1} =(1+4\lambda)a_n+(2+3\lambda)b_n.$$

It has the required coefficient ratio when

$$2+3\lambda=\lambda(1+4\lambda), \qquad(2\lambda+1)(\lambda-1)=0.$$

For $\lambda=1,-1/2$, respectively,

$$a_n+b_n=2\cdot5^{n-1},\qquad a_n-\frac12b_n=\frac12(-1)^{n-1}.$$

Solving gives

$$\boxed{a_n=\frac{2\cdot5^{n-1}+(-1)^{n-1}}3,\qquad b_n=\frac{4\cdot5^{n-1}-(-1)^{n-1}}3.}$$

The source switches midway to $b_1=4$; these answers consistently use the stated $b_1=1$. If $b_1=4$ were intended, the corresponding formulas would be $a_n=(5^n+2(-1)^n)/3$ and $b_n=2(5^n-(-1)^n)/3$.

For a symmetric system

$$a_{n+1}=sa_n+tb_n,\qquad b_{n+1}=ta_n+sb_n,$$

adding and subtracting directly yields geometric sequences with ratios $s+t$ and $s-t$. General coupled systems need not always have two independent real geometric combinations; repeated or complex characteristic values require the appropriate additional treatment.

9. A recurrence containing partial sums

Let $S_n=a_1+\cdots+a_n$, and suppose the terms are positive with

$$a_1=1,\qquad S_n=\frac12a_n^2+\frac12a_n.$$

For $n\ge2$, subtract the equation at $n-1$ and use $S_n-S_{n-1}=a_n$:

$$2a_n=a_n^2-a_{n-1}^2+a_n-a_{n-1},$$ $$(a_n-a_{n-1}-1)(a_n+a_{n-1})=0.$$

Positivity excludes the second factor being zero. Therefore $a_n=a_{n-1}+1$, and

$$\boxed{a_n=n.}$$

Conversely, these terms satisfy $S_n=n(n+1)/2=(a_n^2+a_n)/2$, so the original partial-sum condition is verified. Without positivity, additional branches would require consideration.

10. Conjecture a formula, then prove it

Let the positive sequence satisfy

$$a_1=1,\qquad a_{n+1}=\sqrt{a_na_{n+1}+n+1}.$$

The first few terms are $1,2,3$, suggesting $a_n=n$. A finite list is evidence for a conjecture, not its proof.

The base case is given. Assume $a_k=k$ for a positive integer $k$. Since $a_{k+1}>0$, squaring is valid and gives

$$a_{k+1}^2-ka_{k+1}-(k+1)=0,$$ $$(a_{k+1}+1)(a_{k+1}-k-1)=0.$$

The positive root is $k+1$, completing the induction. Thus

$$\boxed{a_n=n.}$$

Here the implicit equation has exactly one positive root at each step, so the branch choice also proves uniqueness. Guessing and induction are useful beyond these ten patterns, but not every unfamiliar recurrence has a conveniently guessable closed form. The induction guide develops the proof methods in detail, and probability recurrences show why these transformations matter in applications.