Discrete Mathematics

Linear Recurrence Relations

Linear Recurrence Relations: Level 5 Challenges

         

Let k1,k2,, k_1, k_2, \ldots, be a sequence that is recursively defined as kn+2=kn+1+2knk_{n+2} = k_{n+1} + 2 k_{n}, for all n1n\geq 1 , with k1=k2=1k_1 = k_2 = 1. The infinite sum, S=k171+k272+k373S = \frac{k_1}{7 ^1} + \frac{k_2}{7 ^2} + \frac{k_3}{7 ^3} \ldots, is a fraction of the form ab\frac{a}{b}, where aa and bb are coprime integers. What is the value of a+ba+b?

The sequence a0,a1,a2,a_0,a_1,a_2,\dots satisfies am+n+amn=12(a2m+a2n)a_{m+n} + a_{m-n} = \frac{1}{2}(a_{2m}+a_{2n})

for all non-negative integers with mnm\geq n. If a1=1a_1 = 1, determine the value of a1995a_{1995}

Define a subset SS of the first 3030 positive integers to be uneven if, for all iSi \in S, i+2Si+2 \notin S. For example, {1,2}\{1, 2\} is an uneven subset, while {1,2,3}\{1, 2, 3\} is not. If NN represents the number of uneven subsets, find the remainder when NN is divided by 10001000.

Notes:

The empty set is considered to be an uneven subset.

You may want use a calculator at the end.

an=2an1+3bn=bn1+bn2 { \begin{aligned} a_{n} & =& 2a_{n-1} + 3 \\ b_{n} &=& b_{n-1} + b_{n-2} \\ \end{aligned} }

For a positive integer nn, consider the two recurrence relations above subjected to the conditions a1=0a_1 = 0 and b1=b2=1b_{1} = b_{2} = 1 .

If the value of the expression (ab2015+3)(ab2016+3)\big(a_{b_{2015}} + 3\big)\big(a_{b_{2016}} + 3\big) can be expressed as pbqrsp^{b_{q}} \frac{r}{s}, where bqb_{q} is one of the terms in the recurrence relations sequence above and (p,r)(p, r) and (r,s)(r, s) are pairwise coprime integers.

Find the value of (p+q+r+s)mod673(p+q+r+s) \bmod {673}.

an+2=(n+3)an+1(n+2)an \large a_{n+2} = (n + 3)a_{n+1} - (n + 2)a_{n}

For whole numbers nn, consider the recurrence relation defined as above with a1=1,a2=3a_{1} = 1, a_{2} = 3.

Find (k=12015ak)(mod100).\displaystyle\bigg( \sum_{k=1}^{2015} a_{k} \bigg)\pmod{100}.

×

Problem Loading...

Note Loading...

Set Loading...