A multiplicative property in a linear recurrence

Probability Level 5

Define a sequence of integers u n ( n ≥ 0 ) u_n \, (n \ge 0) with the recurrence relation u 0 = 1 , u 1 = 5 , u n + 1 = 2 u n − 4 u n − 1 . u_0 = 1, \quad u_1 = 5, \quad u_{n+1} = 2u_n - 4u_{n-1}.

As n → ∞ n \to \infty , if we pick i , j i, j uniformly on { 0 , 1 , 2 , … , n } \{0, 1, 2, \ldots, n\} and independantly of each other, what is the limiting probability that u i × u j = u k u_i \times u_j = u_k for some nonnegative integer k k ?

The probability can be expressed as a b \frac{a}{b} where a a and b b are non-negative coprime integers, find a + b a+b


The answer is 14.

Julian Poon by Julian Poon , 20, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Mark Hennings
Jul 5, 2017

It is easy to solve this recurrence relation by induction to see that u 3 n + j = { ( − 8 ) n j = 0 5 × ( − 8 ) n j = 1 6 × ( − 8 ) n j = 2 u_{3n+j} \; = \; \left\{ \begin{array}{lll} (-8)^n & \hspace{1cm} & j = 0 \\ 5\times(-8)^n & & j = 1 \\ 6\times(-8)^n & & j = 2 \end{array}\right. for all n ≥ 0 n \ge 0 .

It is now clear that u i × u j u_i \times u_j is equal to another sequence element u k u_k exactly when either i i or j j is divisible by 3 3 .

If n = 3 m − 1 n = 3m-1 then P [ i = 0 ] = P [ i = 1 ] = P [ i = 2 ] = m 3 m = 1 3 \mathbb{P}[i=0] = \mathbb{P}[i =1] = \mathbb{P}[ i = 2] = \tfrac{m}{3m} = \tfrac13 and so the desired probability is p n = 5 9 p_n = \tfrac59 .

If n = 3 m n = 3m then P [ i = 0 ] = m + 1 3 m + 1 P [ i = 1 ] = P [ i = 2 ] = m 3 m + 1 \mathbb{P}[i=0] = \tfrac{m+1}{3m+1} \hspace{1cm} \mathbb{P}[i =1] = \mathbb{P}[ i = 2] = \tfrac{m}{3m+1} and so the desired probability is p n = ( m + 1 ) 2 + 4 m ( m + 1 ) ( 3 m + 1 ) 2 = ( m + 1 ) ( 5 m + 1 ) ( 3 m + 1 ) 2 p_n \;= \; \frac{(m+1)^2 + 4m(m+1)}{(3m+1)^2} \; = \; \frac{(m+1)(5m+1)}{(3m+1)^2}

If n = 3 m + 1 n = 3m+1 then P [ i = 0 ] = P [ i = 1 ] = m + 1 3 m + 2 P [ i = 2 ] = m 3 m + 2 \mathbb{P}[i=0] = \mathbb{P}[i =1] = \tfrac{m+1}{3m+2} \hspace{1cm} \mathbb{P}[ i = 2] = \tfrac{m}{3m+2} and so the desired probability is p n = 3 ( m + 1 ) 2 + 2 m ( m + 1 ) ( 3 m + 2 ) 2 = ( m + 1 ) ( 5 m + 3 ) ( 3 m + 2 ) 2 p_n \; = \; \frac{3(m+1)^2 + 2m(m+1)}{(3m+2)^2} \; = \; \frac{(m+1)(5m+3)}{(3m+2)^2}

Looking at these three cases, is clear that lim ⁡ n → ∞ p n = 5 9 \lim_{n \to \infty} p_n = \tfrac59 , making the answer 5 + 9 = 14 5+9=\boxed{14} .

4 Helpful 0 Interesting 0 Brilliant 0 Confused

What is the approach for solving the sequence ?

Kushal Bose - 3 years, 11 months ago

Log in to reply

The indicial equation for this recurrence relation is λ 2 − 2 λ + 4 = 0 \lambda^2 - 2\lambda + 4 = 0 , which has roots − 2 ω -2\omega and − 2 ω 2 -2\omega^2 . Thus we have u n = α ( − 2 ω ) n + β ( − 2 ω 2 ) n u_n \; = \; \alpha(-2\omega)^n + \beta(-2\omega^2)^n for some α , β \alpha,\beta .

Rather than find the forms of α , β \alpha,\beta , we note easily that u n + 3 = − 8 u n u_{n+3} = -8u_n , and all we then need are u 0 = 1 u_0=1 , u 1 = 5 u_1=5 , u 2 = 6 u_2=6 to finish off.

Mark Hennings - 3 years, 11 months ago

In other words, given i i and j j , such a k k exists if and only if i i or j j is divisible by 3. It quickly follows that the probability is 5 9 \frac{5}{9} .

Jon Haussmann - 3 years, 10 months ago

Log in to reply

It is easy that the probability is exactly p n = 5 9 p_n = \tfrac59 when n ≡ 2 ( m o d 3 ) n \equiv 2 \pmod{3} , but it is slightly more fiddly, and the limit needs to be taken, in other cases.

Mark Hennings - 3 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...