Preparation for math olympiad UKMT junior senior intermediate maths challenge smc jmc imc 2022 2023

For learning more ideas send message to my Whatsapp number 00989395025223

[NadiehFan]

You have correctly deduced that if we have a + b = 1, a² + b² = 2 and if we define

s(n) = aⁿ + bⁿ

then s(n) satisfies the recurrence relation

s(n + 1) = s(n) + ½·s(n−1)

and this can of course be used to calculate s(11) in successive steps starting with the known values s(1) = 1 and s(2) = 2. However, you can save yourself quite a bit of work if you note that

(aᵐ + bᵐ)(aⁿ + bⁿ) = aᵐ⁺ⁿ + bᵐ⁺ⁿ + aⁿbⁿ(aᵐ⁻ⁿ + bᵐ⁻ⁿ)

so we have

s(m)·s(n) = s(m + n) + (ab)ⁿ·s(m − n)

or

s(m + n) = s(m)·s(n) − (−½)ⁿ·s(m − n)

since ab = −¹⁄₂. With m = 6, n = 5, s(6) = ¹³⁄₂, s(5) = ¹⁹⁄₄, s(1) = 1 we can therefore immediately conclude that

s(11) = ( ¹³⁄₂)·(¹⁹⁄₄) − (−¹⁄₂)⁵ = ²⁴⁷⁄₈ + ¹⁄₃₂ = ⁹⁸⁸⁄₃₂ + ¹⁄₃₂ = ⁹⁸⁹⁄₃₂

Alternatively, we could solve the recurrence relation s(n + 1) = s(n) + ½·s(n − 1) to get a generic closed form expression for s(n) for all sequences that satisfy this recurrence. To do this, let us assume that a geometric sequence defined by s(n) = λⁿ for some λ ≠ 0 satisfies this recurrence, then we must have

λⁿ⁺¹ = λⁿ + ½·λⁿ⁻¹

or

λⁿ⁻¹·(λ² − λ − ½) = 0

Clearly λ = 0 would satisfy this condition for n > 1, but then we would have s(n) = 0 for any positive integer n > 1, and then the recurrence s(n + 1) = s(n) + ½·s(n − 1) itself would imply that we also have s(1) = 0 as well as s(n) = 0 for any integer n < 1. A sequence where all terms are zero is a trivial solution of the recurrence s(n + 1) = s(n) + ½·s(n − 1), so for non-trivial solutions we must have λ ≠ 0. Consequently, for any non-trivial solution s(n) = λⁿ of this recurrence λ must satisfy

λ² − λ − ½ = 0

This is a quadratic equation in λ with the solutions λ₁ = ½ − ½√3 and λ₂ = ½ + ½√3, so both s(n) = (½ − ½√3)ⁿ and s(n) = (½ + ½√3)ⁿ are solutions of the recurrence s(n + 1) = s(n) + ½·s(n − 1). But since any linear combination of solutions is evidently also a solution, this means that

s(n) = α·(½ − ½√3)ⁿ + β·(½ + ½√3)ⁿ

is a solution of the recurrence s(n + 1) = s(n) + ½·s(n − 1) for any value of α and β. Note that this expression also gives the trivial solution s(n) = 0 for every integer n when α and β are both equal to zero.

It is easy to prove that this expression for s(n) comprises every possible sequence that satisfies the recurrence s(n + 1) = s(n) + ½·s(n − 1). This recurrence implies that s(n) is uniquely defined for any integer n if s(n) is defined for two consecutive values of n, say for n = k and n = k + 1. Accordingly, if s(n) can be expressed as α·λ₁ⁿ + β·λ₂ⁿ with λ₁ = ½ − ½√3, λ₂ = ½ + ½√3 for any integer n then we must have

α·λ₁ᵏ + β·λ₂ᵏ = s(k)
α·λ₁ᵏ⁺¹ + β·λ₂ᵏ⁺¹ = s(k + 1)

which is a linear system of equations in α and β. This system has a unique solution α and β since the determinant λ₁ᵏ·λ₂ᵏ⁺¹ − λ₂ᵏ·λ₁ᵏ⁺¹ = λ₁ᵏ·λ₂ᵏ(λ₂ − λ₁) of this system is unequal to zero since λ₁ ≠ 0, λ₂ ≠ 0 and λ₂ ≠ λ₁. So, for any possible sequence that satisfies the recurrence s(n + 1) = s(n) + ½·s(n − 1) there exists a unique pair (α, β) such that s(n) = α·(½ − ½√3)ⁿ + β·(½ + ½√3)ⁿ for any integer n.

In the present case we have s(1) = 1 and s(2) = 2 so α and β must satisfy the system

α·(½ − ½√3) + β·(½ + ½√3) = 1
α·(½ − ½√3)² + β·(½ + ½√3)² = 2

which has the solution (α, β) = (1, 1). So, for s(1) = 1, s(2) = 2, s(n + 1) = s(n) + ½·s(n − 1) we have

s(n) = (½ − ½√3)ⁿ + (½ + ½√3)ⁿ

This is admittedly not very practical to calculate e.g. s(11) by hand, but with a calculator we can easily verify that we indeed have

s(11) = (½ − ½√3)¹¹ + (½ + ½√3)¹¹ = ⁹⁸⁹⁄₃₂