Questions on recurrence relations

Question 1

Solve u_n+1 = 4u_n − 3 with u₁ = 2.

Accepted Answer

Complementary function: A4ⁿ. For the constant, try u_n = c, so c = 4c − 3 and c = 1. Then u_n = A4ⁿ + 1, and u₁ = 2 gives 4A + 1 = 2, so A = 1/4. Hence u_n = 4ⁿ⁻¹ + 1. B1 for the complementary function, M1 for a constant particular solution, A1 for c = 1, A1 for the final formula. The first four terms are 2, 5, 17, 65 either way.

Question 2

Solve u_n+1 = 2u_n + n with u₁ = 1.

Accepted Answer

The right-hand side is linear in n, so try a particular solution an + b, so a(n + 1) + b = 2(an + b) + n. Comparing coefficients of n gives a = 2a + 1, so a = −1; the constants give a + b = 2b, so b = −1. With the complementary function A2ⁿ, u₁ = 1 gives 2A − 2 = 1, so A = 3/2 and u_n = 3(2ⁿ⁻¹) − n − 1. M1 for trying an + b, A1 for a = −1, A1 for b = −1, M1 for using the initial condition, A1 for the final formula. Checking n = 3: 12 − 4 = 8, and the recurrence gives 8 too.

Question 3

A sequence is given by u_n+1 = 3u_n − 2 with u₁ = 4. Write down the first four terms.

Accepted Answer

Each term is three times the one before it, less 2. u₂ = 3(4) − 2 = 10, u₃ = 3(10) − 2 = 28 and u₄ = 3(28) − 2 = 82, so the terms are 4, 10, 28, 82. M1 for using the relation at least twice, A1 for all four terms. Each new term feeds back into the relation, so an error in one term travels through every term after it; the closed form u_n = 3ⁿ + 1 gives the same list without that risk.

Question 4

Write down the auxiliary equation of u_n+2 = 4u_n+1 − 4u_n, solve it, and write down the general solution of the recurrence relation.

Accepted Answer

Rearranged, the relation is u_n+2 − 4u_n+1 + 4u_n = 0, so the auxiliary equation is m² − 4m + 4 = 0. B1. It factorises as (m − 2)² = 0, so m = 2 is a repeated root. M1 for solving with the repetition named. A repeated root gives a general solution with an extra factor of n: u_n = (A + Bn)2ⁿ. A1. Writing A2ⁿ + B2ⁿ instead would collapse to a single arbitrary constant and could not meet two initial conditions.

Question 5

Solve u_n+2 = 5u_n+1 − 6u_n with u₁ = 1 and u₂ = 4.

Accepted Answer

Auxiliary equation m² − 5m + 6 = 0, so m = 2 or m = 3 and u_n = A2ⁿ + B3ⁿ. The conditions give 2A + 3B = 1 and 4A + 9B = 4, so B = 2/3 and A = −1/2. Tidying, u_n = 2(3ⁿ⁻¹) − 2ⁿ⁻¹. M1 for the auxiliary equation, A1 for the two roots, B1 for the general solution, M1 for using both conditions, A1 for A and B, A1 for the final formula. Checking n = 3: 18 − 4 = 14, and 5(4) − 6(1) = 14.

Question 6

Solve u_n+2 = 6u_n+1 − 9u_n with u₁ = 3 and u₂ = 18.

Accepted Answer

Auxiliary equation m² − 6m + 9 = 0 has the repeated root m = 3, so the general solution needs the extra factor of n and reads u_n = (A + Bn)3ⁿ. The conditions give 3(A + B) = 3 and 9(A + 2B) = 18, so A + B = 1 and A + 2B = 2, giving B = 1 and A = 0. Hence u_n = n3ⁿ. M1 for the auxiliary equation, A1 for the repeated root, B1 for the general solution with its factor of n, M1 for the two conditions, A1 for A and B, A1 for the final formula. Checking n = 3: 81, and 6(18) − 9(3) = 81.

Question 7

Prove by induction that u_n = 4ⁿ⁻¹ + 1 satisfies u_n+1 = 4u_n − 3 with u₁ = 2.

Accepted Answer

Base case: 4⁰ + 1 = 2, as given. Assume u_k = 4^k−1 + 1. Then u_k+1 = 4(4^k−1 + 1) − 3 = 4^k + 4 − 3 = 4^k + 1, which is the formula at n = k + 1. B1 for the base case, M1 for substituting the hypothesis into the recurrence, A1 for 4^k + 1, A1 for the conclusion. True at n = 1 and inherited at each step, so true for all positive integers n.

Question 8

A conservation herd numbers 500 animals. Each year the herd grows by 8%, and 20 animals are then moved to another reserve. (a) Explain why a model in whole animals is u_n+1 = INT(1.08u_n) − 20 with u₀ = 500, and use it to find the herd after three years. (b) Solve the smooth model u_n+1 = 1.08u_n − 20 with u₀ = 500, and compare its prediction at three years with the truncated model's.

Accepted Answer

(a) Animals come in whole units, so the fractional part of the 8% growth is discarded before the 20 leave, which is what INT does; the truncation sits inside the relation, so the model must be iterated. The terms run 500, then INT(540) − 20 = 520, then INT(561.6) − 20 = 541, then INT(584.28) − 20 = 564. B1 for the explanation of INT applied before the removal, M1 for iterating with the truncation at each step, A1 for 564.
(b) Complementary function A(1.08)ⁿ; trying a constant c gives c = 1.08c − 20, so c = 250. Then u₀ = 500 gives A = 250, so u_n = 250(1.08)ⁿ + 250, and at n = 3 the smooth model reads 564.928. M1 for the particular solution c = 250, A1 for the closed form. B1 for the comparison: the smooth model reads about one animal high after three years, because each truncation discards under one animal and the discards then compound, so the gap only widens. Both models grow without limit, since 1.08 exceeds 1 and the herd starts above the steady state of 250.

Question 9

Solve u_n+1 = 0.5u_n + 6 with u₁ = 20, and describe how the sequence behaves as n increases.

Accepted Answer

The complementary function is A(0.5)ⁿ. For the constant 6, try u_n = c, giving c = 0.5c + 6 and c = 12. Then u_n = A(0.5)ⁿ + 12, and u₁ = 20 gives 0.5A + 12 = 20, so A = 16 and u_n = 2⁴⁻ⁿ + 12. M1 for a constant particular solution, A1 for c = 12, M1 for the initial condition, A1 for the closed form.
The terms are 20, 16, 14, 13, 12.5, …: each one is smaller than the last, so the sequence is decreasing, and 2⁴⁻ⁿ → 0, so it converges to 12 without ever reaching it. B1 for decreasing and convergent to 12, both stated. The root of the auxiliary equation is 0.5, and it is the fact that |0.5| < 1 that makes the sequence converge; the fact that it is positive is what keeps the approach on one side.

Question 10

A recurrence relation u_n+1 = ku_n + c, with c a non-zero constant and k ≠ 1, has closed form u_n = Akⁿ⁻¹ + L, where L = c/(1 − k) and A depends on the first term. Describe how the sequence behaves in each of the cases k = 0.9, k = −0.9, k = 1.5 and k = −1, taking A to be non-zero in each case.

Accepted Answer

Everything is decided by kⁿ⁻¹, since L never changes.
k = 0.9: |k| < 1 and k is positive, so kⁿ⁻¹ shrinks to 0 through positive values. The sequence is monotonic and convergent, approaching L from whichever side it starts. B1.
k = −0.9: |k| < 1 but k is negative, so kⁿ⁻¹ shrinks while changing sign each step. The sequence is convergent to L but oscillates either side of it. B1.
k = 1.5: |k| > 1, so kⁿ⁻¹ grows without limit and the sequence is divergent, moving steadily away from L. B1.
k = −1: |k| = 1, so kⁿ⁻¹ alternates between 1 and −1 for ever. The sequence is periodic, of period 2, taking two values in turn and neither settling nor growing. B1.

Question 11

Solve u_n+2 = u_n+1 + 6u_n with u₁ = 1 and u₂ = 8, and state whether the sequence converges.

Accepted Answer

The auxiliary equation is m² − m − 6 = 0, which factorises as (m − 3)(m + 2) = 0, so m = 3 or m = −2 and u_n = A3ⁿ + B(−2)ⁿ. M1 for the auxiliary equation, A1 for the two roots.
The conditions give 3A − 2B = 1 and 9A + 4B = 8. Doubling the first and adding, 15A = 10, so A = 2/3 and then B = 1/2. Hence u_n = 2(3ⁿ⁻¹) + (−1)ⁿ2ⁿ⁻¹. M1 for using both conditions, A1 for A and B, A1 for the closed form.
Checking n = 3: 18 − 4 = 14, and the relation gives 8 + 6 = 14. The sequence does not converge: the root 3 has modulus greater than 1, so the terms grow without limit. B1 for the conclusion with the modulus of the root as its reason. The root of larger modulus decides the growth: at n = 7 the term 2(3ⁿ⁻¹) is 1458 against a total of 1394, already within 5%, and the alternating (−2)ⁿ part is a correction whose share keeps shrinking.

Question 12

Solve u_n+2 + u_n+1 − 6u_n = 12 with u₁ = −4 and u₂ = 10.

Accepted Answer

Auxiliary equation m² + m − 6 = 0 gives m = 2 or m = −3. For the constant 12, try u_n = k, giving k + k − 6k = −4k = 12, so k = −3. Then u_n = A2ⁿ + B(−3)ⁿ − 3, and the conditions give 2A − 3B = −1 and 4A + 9B = 13, so A = 1 and B = 1. Hence u_n = 2ⁿ + (−3)ⁿ − 3. M1 for the auxiliary equation, A1 for the two roots, M1 for a constant particular solution, A1 for k = −3, M1 for the two conditions, A1 for A and B, A1 for the final formula. Checking n = 3: 8 − 27 − 3 = −22, and 12 − 10 + 6(−4) = −22.

Question 13

Solve u_n+2 − 3u_n+1 + 2u_n = 4 with u₁ = 1 and u₂ = 5.

Accepted Answer

Auxiliary equation m² − 3m + 2 = 0, so m = 1 or m = 2 and the complementary function is A + B2ⁿ. A constant trial for the right-hand side fails here: substituting u_n = k gives k − 3k + 2k = 0, never 4, because 1 is a root of the auxiliary equation and a constant already lives in the complementary function. Try u_n = cn instead: c(n + 2) − 3c(n + 1) + 2cn = −c = 4, so c = −4. Then u_n = A + B2ⁿ − 4n, and the conditions give A + 2B − 4 = 1 and A + 4B − 8 = 5, so A + 2B = 5 and A + 4B = 13, giving B = 4 and A = −3. Hence u_n = 2ⁿ⁺² − 4n − 3. M1 for the auxiliary equation, A1 for the roots 1 and 2, B1 for spotting the clash and trying cn, M1 for substituting cn into the relation, A1 for c = −4, M1 for using both conditions, A1 for the final formula. Checking n = 3: 32 − 12 − 3 = 17, and 3(5) − 2(1) + 4 = 17.

Question 14

The Fibonacci numbers satisfy F_n = (φⁿ − ψⁿ)/√5, where φ and ψ are the roots of m² = m + 1, so that φ + ψ = 1 and φψ = −1. Prove that F_n+1F_n−1 − F_n² = (−1)ⁿ for every n ≥ 1, and verify the identity at n = 6.

Accepted Answer

Work with 5 times each side to clear the √5. 5F_n+1F_n−1 = (φⁿ⁺¹ − ψⁿ⁺¹)(φⁿ⁻¹ − ψⁿ⁻¹) = φ²ⁿ + ψ²ⁿ − (φψ)ⁿ⁻¹(φ² + ψ²), collecting the cross terms as φⁿ⁺¹ψⁿ⁻¹ + φⁿ⁻¹ψⁿ⁺¹ = (φψ)ⁿ⁻¹(φ² + ψ²). Also 5F_n² = φ²ⁿ + ψ²ⁿ − 2(φψ)ⁿ. Subtracting, the φ²ⁿ and ψ²ⁿ terms cancel, leaving (φψ)ⁿ⁻¹[2φψ − (φ² + ψ²)]. Now φψ = −1 and φ² + ψ² = (φ + ψ)² − 2φψ = 1 + 2 = 3, so the bracket is −2 − 3 = −5 and the whole expression is (−1)ⁿ⁻¹(−5) = 5(−1)ⁿ. Dividing by 5 gives F_n+1F_n−1 − F_n² = (−1)ⁿ. At n = 6: F₇F₅ − F₆² = 13 × 5 − 64 = 1 = (−1)⁶. M1 for expanding 5F_n+1F_n−1 from the closed form, A1 for collecting the cross terms with the factor (φψ)ⁿ⁻¹, B1 for φ² + ψ² = 3 from the root sum and product, M1 for subtracting 5F_n² and cancelling, A1 for (−1)ⁿ, B1 for the numerical check at n = 6. The sign alternates because φψ = −1: consecutive Fibonacci numbers overshoot and undershoot the square in turn.

Question 15

£2000 is paid into a savings account at the start of each year, and interest of 4% is added to the whole balance at the end of each year. Let A_n be the balance at the end of year n, with A₀ = 0. Set up a recurrence relation for A_n, solve it, and find the balance at the end of the tenth year.

Accepted Answer

At the start of year n the balance is A_n−1 + 2000, and multiplying by 1.04 at the end of the year gives A_n = 1.04(A_n−1 + 2000) = 1.04A_n−1 + 2080. M1 for the order of the two events, A1 for the relation.
The complementary function is K(1.04)ⁿ. Trying a constant c gives c = 1.04c + 2080, so −0.04c = 2080 and c = −52000. M1 for a constant particular solution, A1 for c = −52000.
So A_n = K(1.04)ⁿ − 52000, and A₀ = 0 gives K = 52000, that is A_n = 52000(1.04ⁿ − 1). M1 for fitting the initial condition. At n = 10, 1.04¹⁰ = 1.480244…, so A₁₀ = 52000 × 0.480244… = £24972.70 to the nearest penny. A1.
Checking the first two years against the model: A₁ = 1.04 × 2000 = 2080 and A₂ = 1.04(2080 + 2000) = 4243.20, and the closed form gives 52000(1.04 − 1) = 2080 and 52000(1.0816 − 1) = 4243.20. The constant −52000 is not a balance the account ever holds; it is the level at which the interest would exactly cancel the payments, and it is negative because money is going in rather than out.