Recurrence relations

A sequence {u_n}, where n 0, satisfies the first order recurrence relation (*)

where α, β, k are non-zero constants and α k

Determine, in terms of α, β, k and n, the general solution of this recurrence relation.

Given that u₀ = L and u_T = 0, where T is a constant,

show that a particular solution of the recurrence relation is

Taylor borrows a sum of money, L, to buy a house.

Taylor arranges a loan which enables them to increase their repayment as their income grows.

The terms of the loan require Taylor’s repayments to be made once a year.

On each anniversary of the loan being taken out, 6% interest is charged on the outstanding balance and Taylor makes an annual repayment of the total loan.

Taylor’s total annual repayment of the loan will increase by 4% each year and the whole debt will be cleared in exactly 40 years.

The recurrence relation (*) can be used to model this situation.

State the value of α

State the value of k

State the relevance of β in (*)

Show that after 30 years, according to the model, the outstanding debt is larger than the original loan.

There are three lily pads on a pond. A frog hops repeatedly from one lily pad to another.

The frog starts on lily pad A, as shown in Figure 1.

In a model, the frog hops from its position on one lily pad to either of the other two lily pads with equal probability.

Let p_n be the probability that the frog is on lily pad A after n hops.

Explain, with reference to the model, why p₁ = 0

The probability p_n satisfies the recurrence relation

Prove by induction that, for n 1

Use the result in part (b) to explain why, in the long term, the probability that the

The owner of a new company models the number of customers that the company will have at the end of each month. The owner assumes that

• a constant proportion, p (where 0 p 1), of the previous month’s customers will be retained for the next month

• a constant number of new customers, k, will be added each month.

Let u_n (where n 1) represent the number of customers that the company will have at the end of n months.

The company has 5000 customers at the end of the first month.

By setting up a first order recurrence relation for u_{n+ 1} in terms of u_n, determine an expression for u_n in terms of n, p and k.

The owner believes that 95% of the previous month’s customers will be retained each month and that there will be 10 000 new customers each month.

According to the model, the company will first have at least 135 000 customers by the end of the m th month.

Using logarithms, determine the value of m.

A recurrence system is defined by

u_n+2 = 9(n + 1)² u_n − 3u_n+1 n 1

u₁ = −3, u₂ = 18

Prove by induction that, for n ,

The number of visits to a website, in any particular month, is modelled as the number of visits received in the previous month plus k times the number of visits received in the month before that, where k is a positive constant.

Given that V_n is the number of visits to the website in month n,

write down a general recurrence relation for V_{n+ 2} in terms of V_{n+ 1}, V_n and k.

For a particular website you are given that

• k

• In month 1, there were 65 visits to the website.

• In month 2, there were 71 visits to the website.

Show that

This model predicts that the number of visits to this website will exceed one million for the first time in month N.

Find the value of N.

An increasing sequence {u_n} for n is such that the difference between the nth term of {u_n} and the mean of the previous two terms of {u_n} is always 6

Show that, for n 3

Given that u₁ = 2 and u₂ = 8

find the solution of this second order recurrence relation to obtain an expression for u_n in terms of n.

Show that as n ’, u_n kn where k is a constant to be determined. You must give reasons for your answer.