Recursion torture

Probability Level 3

Defined is the recursive relation

a n = 3 a n − 1 + 5 , a 0 = 1 a_n=3a_{n-1}+5 \ , \ a_0=1

Demanded is a 1000 a_{1000} modulo 29 29 .


The answer is 27.

A Former Brilliant Member by A Former Brilliant Member

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

The generating function of the sequence is 1 + 4 x ( 1 − x ) ( 1 − 3 x ) \frac{1+4x}{(1-x)(1-3x)} , with gives the closed form formula for the sequence

a n = 7 × 3 n − 5 2 a_n=\frac{7\times 3^n-5}{2}

the rest is some modular arithmetic, when n = 1000 n=1000 is plugged in.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...