AlgebraDifficulty 15-70564 tagged problems

Sequences and Recursion

Sequences and Recursion is the habit of understanding terms defined by patterns or previous terms through recurrence and closed forms. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$a_n = r\,a_{n-1} + d \;\implies\; a_n = r^{\,n}\!\left(a_0 - \frac{d}{1-r}\right) + \frac{d}{1-r}\quad (r \ne 1).$$

A sequence defined by each term from the previous one can often be solved into a closed form, letting you jump straight to any term without iterating.

Why It Works

1
For a first-order linear recurrence $a_n = r\,a_{n-1} + d$, look for the fixed point $L$ with $L = rL + d$, giving $L = \frac{d}{1 - r}$.
2
Define $b_n = a_n - L$; then $b_n = r\,a_{n-1} + d - L = r(a_{n-1} - L) = r\,b_{n-1}$, a pure geometric sequence.
3
So $b_n = r^{\,n} b_0 = r^{\,n}(a_0 - L)$.
4
Add $L$ back: $a_n = r^{\,n}(a_0 - L) + L$ with $L = \frac{d}{1-r}$ — the closed form.

Worked Examples

Example 1

A sequence satisfies $a_0 = 5$ and $a_n = 2a_{n-1} - 3$. Find $a_4$.

1
Find the fixed point: $L = 2L - 3 \Rightarrow L = 3$.
2
Then $a_n - 3 = 2(a_{n-1} - 3)$, so $a_n - 3 = 2^n(a_0 - 3) = 2^n(5 - 3) = 2 \cdot 2^n = 2^{n+1}$.
3
Thus $a_n = 2^{n+1} + 3$; for $n = 4$, $a_4 = 2^5 + 3 = 32 + 3 = 35$.

Answer:

$a_4 = 35$.

Warm-up

An arithmetic sequence has $a_1 = 3$ and $a_n = a_{n-1} + 4$. Find $a_{20}$.

1
This is the special case $r = 1$, $d = 4$: each term adds the common difference $4$, so $a_n = a_1 + (n - 1)d$.
2
Substitute: $a_n = 3 + 4(n - 1)$.
3
At $n = 20$: $a_{20} = 3 + 4(19) = 3 + 76 = 79$.

Answer:

$a_{20} = 79$.

Contest level

A sequence has $a_0 = 1$ and $a_n = 3a_{n-1} + 2$. Find a closed form and compute $a_4$.

1
Find the fixed point: $L = 3L + 2 \Rightarrow L = -1$.
2
Shift by $L$: $a_n - (-1) = 3\big(a_{n-1} - (-1)\big)$, so $a_n + 1 = 3^n(a_0 + 1) = 3^n \cdot 2$.
3
Hence $a_n = 2\cdot 3^n - 1$; at $n = 4$, $a_4 = 2\cdot 81 - 1 = 161$.

Answer:

$a_n = 2\cdot 3^n - 1$, so $a_4 = 161$.

Olympiad / Challenge

Let $a_0 = 0$, $a_1 = 1$, and $a_n = 5a_{n-1} - 6a_{n-2}$ for $n \ge 2$. Find a closed form and compute $a_5$.

1
For a second-order linear recurrence, solve the characteristic equation $x^2 = 5x - 6$, i.e. $x^2 - 5x + 6 = (x - 2)(x - 3) = 0$, with roots $2$ and $3$.
2
The general solution is $a_n = A\cdot 2^n + B\cdot 3^n$. Use the initial values: $a_0 = A + B = 0$ and $a_1 = 2A + 3B = 1$, giving $A = -1$, $B = 1$.
3
So $a_n = 3^n - 2^n$. (Check: $a_2 = 9 - 4 = 5 = 5(1) - 6(0)$.) Then $a_5 = 3^5 - 2^5 = 243 - 32 = 211$.

Answer:

$a_n = 3^n - 2^n$, so $a_5 = 211$.

Going Deeper

Generalization: a homogeneous linear recurrence $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$ is solved by its characteristic polynomial — distinct roots $\lambda_i$ give $a_n = \sum A_i \lambda_i^n$, and a repeated root $\lambda$ of multiplicity $m$ contributes $(A_0 + A_1 n + \cdots + A_{m-1}n^{m-1})\lambda^n$.
Where it appears: AIME closed-form and periodicity problems, Fibonacci/Lucas identities, and counting recurrences (tilings, lattice paths) where you set up the recurrence then solve it.
Pitfall: the fixed-point shift in the first-order formula requires $r \ne 1$ (division by $1 - r$); the case $r = 1$ is arithmetic and must be summed directly. For repeated characteristic roots, forgetting the polynomial-in-$n$ factor gives too few free constants to fit the initial conditions.

Spot the Signal

Look for problems where the key step is understanding terms defined by patterns or previous terms through recurrence and closed forms.
You can describe the hard part as understanding terms defined by patterns or previous terms through recurrence and closed forms, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the expression or equation that calls for sequences and recursion, then rewrite the givens around it.
Name the relation that makes Sequences and Recursion legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Sequences and Recursion just because the surface looks familiar; verify the required condition first.
Applying Sequences and Recursion because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let sequences and recursion reveal the algebraic structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is understanding terms defined by patterns or previous terms through recurrence and closed forms.

Back to techniques

AlgebraDifficulty 15-70564 tagged problems

Sequences and Recursion

Practice this technique Match my level

The Key Result

$$a_n = r\,a_{n-1} + d \;\implies\; a_n = r^{\,n}\!\left(a_0 - \frac{d}{1-r}\right) + \frac{d}{1-r}\quad (r \ne 1).$$

A sequence defined by each term from the previous one can often be solved into a closed form, letting you jump straight to any term without iterating.

Why It Works

1
For a first-order linear recurrence $a_n = r\,a_{n-1} + d$, look for the fixed point $L$ with $L = rL + d$, giving $L = \frac{d}{1 - r}$.
2
Define $b_n = a_n - L$; then $b_n = r\,a_{n-1} + d - L = r(a_{n-1} - L) = r\,b_{n-1}$, a pure geometric sequence.
3
So $b_n = r^{\,n} b_0 = r^{\,n}(a_0 - L)$.
4
Add $L$ back: $a_n = r^{\,n}(a_0 - L) + L$ with $L = \frac{d}{1-r}$ — the closed form.

Worked Examples

Example 1

A sequence satisfies $a_0 = 5$ and $a_n = 2a_{n-1} - 3$. Find $a_4$.

1
Find the fixed point: $L = 2L - 3 \Rightarrow L = 3$.
2
Then $a_n - 3 = 2(a_{n-1} - 3)$, so $a_n - 3 = 2^n(a_0 - 3) = 2^n(5 - 3) = 2 \cdot 2^n = 2^{n+1}$.
3
Thus $a_n = 2^{n+1} + 3$; for $n = 4$, $a_4 = 2^5 + 3 = 32 + 3 = 35$.

Answer:

$a_4 = 35$.

Warm-up

An arithmetic sequence has $a_1 = 3$ and $a_n = a_{n-1} + 4$. Find $a_{20}$.

1
This is the special case $r = 1$, $d = 4$: each term adds the common difference $4$, so $a_n = a_1 + (n - 1)d$.
2
Substitute: $a_n = 3 + 4(n - 1)$.
3
At $n = 20$: $a_{20} = 3 + 4(19) = 3 + 76 = 79$.

Answer:

$a_{20} = 79$.

Contest level

A sequence has $a_0 = 1$ and $a_n = 3a_{n-1} + 2$. Find a closed form and compute $a_4$.

1
Find the fixed point: $L = 3L + 2 \Rightarrow L = -1$.
2
Shift by $L$: $a_n - (-1) = 3\big(a_{n-1} - (-1)\big)$, so $a_n + 1 = 3^n(a_0 + 1) = 3^n \cdot 2$.
3
Hence $a_n = 2\cdot 3^n - 1$; at $n = 4$, $a_4 = 2\cdot 81 - 1 = 161$.

Answer:

$a_n = 2\cdot 3^n - 1$, so $a_4 = 161$.

Olympiad / Challenge

Let $a_0 = 0$, $a_1 = 1$, and $a_n = 5a_{n-1} - 6a_{n-2}$ for $n \ge 2$. Find a closed form and compute $a_5$.

1
For a second-order linear recurrence, solve the characteristic equation $x^2 = 5x - 6$, i.e. $x^2 - 5x + 6 = (x - 2)(x - 3) = 0$, with roots $2$ and $3$.
2
The general solution is $a_n = A\cdot 2^n + B\cdot 3^n$. Use the initial values: $a_0 = A + B = 0$ and $a_1 = 2A + 3B = 1$, giving $A = -1$, $B = 1$.
3
So $a_n = 3^n - 2^n$. (Check: $a_2 = 9 - 4 = 5 = 5(1) - 6(0)$.) Then $a_5 = 3^5 - 2^5 = 243 - 32 = 211$.

Answer:

$a_n = 3^n - 2^n$, so $a_5 = 211$.

Going Deeper

Generalization: a homogeneous linear recurrence $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$ is solved by its characteristic polynomial — distinct roots $\lambda_i$ give $a_n = \sum A_i \lambda_i^n$, and a repeated root $\lambda$ of multiplicity $m$ contributes $(A_0 + A_1 n + \cdots + A_{m-1}n^{m-1})\lambda^n$.
Where it appears: AIME closed-form and periodicity problems, Fibonacci/Lucas identities, and counting recurrences (tilings, lattice paths) where you set up the recurrence then solve it.
Pitfall: the fixed-point shift in the first-order formula requires $r \ne 1$ (division by $1 - r$); the case $r = 1$ is arithmetic and must be summed directly. For repeated characteristic roots, forgetting the polynomial-in-$n$ factor gives too few free constants to fit the initial conditions.

Spot the Signal

Look for problems where the key step is understanding terms defined by patterns or previous terms through recurrence and closed forms.
You can describe the hard part as understanding terms defined by patterns or previous terms through recurrence and closed forms, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the expression or equation that calls for sequences and recursion, then rewrite the givens around it.
Name the relation that makes Sequences and Recursion legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Sequences and Recursion just because the surface looks familiar; verify the required condition first.
Applying Sequences and Recursion because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let sequences and recursion reveal the algebraic structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is understanding terms defined by patterns or previous terms through recurrence and closed forms.